- •И.Н. Слинкина
- •Оглавление
- •Вопросы к блокам по курсу «Исследование операций» Блок 1
- •Блок 1.
- •1.1. Предмет и задачи исследования операций
- •1.2. Основные понятия и принципы исследования операций
- •1.3. Математические модели операций
- •1.4. Понятие линейного программирования
- •1.5. Примеры экономических задач линейного программирования. Задача о наилучшем использовании ресурсов
- •1.6. Примеры экономических задач линейного программирования. Задача о выборе оптимальных технологий
- •1.7. Примеры экономических задач линейного программирования. Задача о смесях
- •1.8. Примеры экономических задач линейного программирования. Транспортная задача
- •1.9. Основные виды записи задач линейного программирования
- •1.10. Способы преобразования
- •1.11. Переход к канонической форме
- •1.12. Переход к симметричной форме записи
- •Блок 2.
- •2.1. Геометрическая интерпретация задачи линейного программирования
- •2.2. Решение задач линейного программирования графическим методом
- •2.3. Свойства решений задачи линейного программирования
- •2.4. Общая идея симплексного метода
- •2.5. Построение начального опорного плана при решении задач линейного программирования симплексным методом
- •2.6. Признак оптимальности опорного плана. Симплексные таблицы
- •2.7. Переход к нехудшему опорному плану.
- •2.8. Симплексные преобразования
- •2.9. Альтернативный оптимум (признак бесконечности множества опорных планов)
- •2.10. Признак неограниченности целевой функции
- •2.11. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание
- •2.12. Понятие двойственности для симметричных задач линейного программирования
- •3.1. Несимметричные двойственные задачи
- •3.2. Открытая и закрытая модели транспортной задачи
- •3.3. Построение начального опорного плана. Правило "Северо-западного угла"
- •3.4. Построение начального опорного плана. Правило минимального элемент
- •3.5. Построение начального опорного плана. Метод Фогеля
- •3.6. Метод потенциалов
- •3.7. Решение транспортных задач с ограничениями по пропускной способности
- •3.8. Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении
- •3.9. Сущность методов дискретной оптимизации
- •3.10. Задача выпуклого программирования
- •3.11. Метод множителей Лагранжа
- •3.12. Градиентные методы
- •4.1. Методы штрафных и барьерных функций
- •4.2. Динамическое программирование. Основные понятия. Сущность методов решения
- •4.3. Стохастическое программирование. Основные понятия
- •4.4. Матричные игры с нулевой суммой
- •4.5. Чистые и смешанные стратегии и их свойства
- •4.6. Свойства чистых и смешанных стратегий
- •4.7. Приведение матричной игры к злп
- •4.8. Задачи теории массового обслуживания. Классификация систем массового обслуживания
- •4.9. Потоки событий
- •4.10. Схема гибели и размножения
- •4.11. Формула Литтла
- •4.12. Простейшие системы массового обслуживания
- •2. Одноканальная система массового обслуживания с неограниченной очередью.
- •Список рекомендуемой литературы
3.4. Построение начального опорного плана. Правило минимального элемент
Сущность: рассматриваются тарифы в распределительной таблице и в первую очередь заполняется клетка с минимальным значением тарифа. При этом в клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую поставщику запасы которого полностью израсходованы, или столбец соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом. Процесс распределения заканчивается когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. Опорный план получаемый в результате данных содержащих m+n-1 загруженных клеток, но в процессе заполнения таблицы могут быть одновременно исключены строка и столбец. Поэтому в свободные клетки нужно записать число 0, условно считая такую клетку занятой.
|
B1 |
B2 |
B3 |
|
A1 |
3 800 |
5 v |
6 v |
800 |
A2 |
7 v |
2 600 |
4 100 |
700 |
A3 |
4 200 |
3 v |
5 800 |
1000 |
A4 |
6 v |
1 500 |
7 v |
500 |
|
1000 |
1100 |
900 |
3000 3000 |
Z=3*800+2*600+4*100+4*200+5*800+1*500=9300
3.5. Построение начального опорного плана. Метод Фогеля
В распределительной таблице по строкам и столбцам определяется разность между двумя наименьшими тарифами. Далее в строке (столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки (столбцы) с нулевым остатком груза в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка. Распределение груза производится как и в предыдущих двух методах.
|
B1 |
B2 |
B3 |
|
1 |
2 |
3 |
4 |
5 |
A1 |
3 800 |
5 v |
6 v |
800 |
2 |
2 |
3 |
– |
– |
A2 |
7 v |
2 600 |
4 100 |
700 |
2 |
2 |
3 |
3 |
– |
A3 |
4 200 |
3 v |
5 800 |
1000 |
1 |
1 |
1 |
1 |
1 |
A4 |
6 v |
1 500 |
7 v |
500 |
5 |
– |
– |
– |
– |
|
1000 |
1100 |
900 |
3000 3000 |
|
|
|
|
|
1 |
1 |
1 |
1 |
|
|
|
|
|
|
2 |
1 |
1 |
1 |
|
|
|
|
|
|
3 |
1 |
– |
1 |
|
|
|
|
|
|
4 |
3 |
– |
1 |
|
|
|
|
|
|
5 |
4 |
– |
5 |
|
|
|
|
|
|
Заполненных ячеек 6.
Z=3*800+2*600+4*100+4*200+5*800+1*100=8900
3.6. Метод потенциалов
Для проверки оптимальности опорного плана используют следующую теорему:
Теорема: Если план транспортной задачи является оптимальным, то ему соответствует система из m+n чисел ,, удовлетворяющих условиям:
- для заполненных ячеек;
- для свободных ячеек.
Эти, ,называются потенциалами.
Таким образом, для того чтобы определить является ли начальный опорный план оптимальным, необходимо рассчитать и, затем проверить второе неравенство для свободных ячеек.
Пусть дан начальный опорный план для некоторой транспортной задачи, записанный в распределительной таблице. посчитаем и.
Заполненых ячеек в распределительной таблице m+n-1. Если составлять уравнения , получим m+n-1 уравнение с m+n неизвестными. n+m-1<n+m. Следовательно, система имеет бесконечно много решений. Нас устроит любое из них. Поэтому принято одну из илипринимать равной 0.
Замечание: Чаще всего за ноль принимают ту из переменных или, для которой в соответствующей строке или столбце больше заполненных ячеек.
После того, как инайдены, необходимо оценить оставшиеся ячейки. Для этого считают так называемые оценки свободных ячеек. Они равны:
Для того, чтобы план был оптимален необходимо, чтобы все для свободных ячеек были неотрицательными.
Пример: Рассчитать потенциалы для примера в 3.4, 3.5, 3.6
|
B1 |
B2 |
B3 |
| |
A1 |
3 800 |
5 v |
6 v |
800 |
0 |
A2 |
7 v |
2 600 |
4 100 |
700 |
0 |
A3 |
4 200 |
3 v |
5 800 |
1000 |
1 |
A4 |
6 v |
1 500 |
7 v |
500 |
-1 |
|
1000 |
1100 |
900 |
3000 3000 |
|
3 |
2 |
4 |
|
|
Вычислим оценки:
=5-(0+2)=3>0 =3-(1+2)=0=0 |
=6-(0+4)=2>0 =6-(3-1)=4>0 |
=7-(0+3)=4>0 =7-(4+1)=2>0 |
Все полученные оценки неотрицательны, следовательно, опорный план оптимален, транспортная задача решена.
Ответ: Z=8900.
Ситуация, когда все оценки сразу получились неотрицательными, достаточна редка. Чаще всего план получается не оптимальным (особенно, если начальный опорный план составлять по правилу северо-западного угла.
Предположим, что. решая транспортную задачу и рассчитав оценки свободных ячеек, мы получили несколько отрицательных оценок. Выберем из них наименьшую. Пусть это будет . Тогда говорят, что ячейка с номером (k,p) потенциальна, т.е. ее необходимо заполнить.
Для того, чтобы заполнить потенциальную ячейку, строят цикл.
Правила построения цикла:
Начальная вершина цикла – потенциальная ячейка.
Остальные вершины, находятся только в заполненных ячейках.
Ребра в вершинах образуют прямой угол.
Ребра могут пересекаться. Однако, точка пересечения ребер не считается вершиной.
Построенный цикл для потенциальной ячейки – единственный. Далее необходимо перераспределить груз в ячейках в рамках цикла. При этом нельзя забывать, что количество заполненных ячеек не должно изменяться. Для этого маркируют вершины цикла знаками "+" и "–". Вершина цикла, находящаяся в потенциальной ячейке, всегда имеет знак "+". В остальных вершинах знаки чередуются ("–", "+", "–", "+", …). Из "отрицательных" ячеек выбираем ту, в которой минимальная загрузка. Эту ячейку и будем освобождать от груза. Маркируем ее как пустую ячейку. Далее, к загрузке в "положительных" ячейках прибавляем значение выбранной минимальной загрузки, в "отрицательных" – вычитаем это же значение. После данной процедуры получается новый опорный план, который необходимо проверить на оптимальность.
Алгоритм решения транспортной задачи:
Составляем начальный опорный план (по любому правилу и методу, лучше – методом минимального элемента).
Считаем потенциалы и.
Рассчитываем оценки свободных ячеек ().
Если все оценки- неотрицательны, то план оптимален. Задача решена. СчитаемZ.
В противном случае, выбираем наименьшее отрицательное значение . Соответствующая ячейка будет называться потенциальной.
Строим цикл.
Маркируем вершины цикла знаками "+" и "–".
Выбираем наименьшую загрузку в "отрицательных" вершинах.
Выбранную ячейку считаем свободной.
Найденную минимальную загрузку прибавляем к загрузке "положительных" ячеек цикла и вычитаем из "отрицательных".
Получен новый опорный план. Переходим к пункту 2.
Пример: Решить транспортную задачу:
290 290 |
20 |
80 |
90 |
60 |
40 | |||
40 |
7 v |
3 v |
5 v |
4 v |
2 40 |
-2 | ||
150 |
6 10 |
2 80 |
3
+ v
– |
1 60 |
7 v |
3 | ||
1
+ |
3
– 10 |
5 v |
2 90 |
6 v |
4 0 |
0 | ||
3 |
-1 |
2 |
-2 |
4 |
| |||
=7-(3-2)=6>0 =3-(3+2)=-2<0 =5-(0-1)=6>0 |
=3-(-1-2)=6>0 =7-(4+3)=0=0 =6-(0-2)=4>0 |
=5-(-2-2)=9>0 =2-(4-2)=0=0 |
Потенциальная ячейка – (2,3). Построим цикл. Промаркировав его, получаем две "отрицательные" ячейки: (2,1) и (3,3). Минимальная загрузка в них равна 10. Прибавляя к загрузке в "положительных" ячейках и вычитая в "отрицательных", получим новую распределительную таблицу:
|
20 |
80 |
90 |
60 |
40 | |
40 |
7 v |
3 v |
5 v |
4 v |
2 40 |
-3 |
150 |
6 v |
2 80 |
3 10 |
1 60 |
7 v |
0 |
100 |
3 20 |
5 v |
2 80 |
6 v |
4 0 |
-1 |
4 |
2 |
3 |
1 |
5 |
|
=7-(-3+4)=6>0 =6-(4+0)=2>0 =5-(2-1)=4>0 |
=3-(-3+2)=4>0 =7-(5+0)=2>0 =6-(1-1)=6>0 |
=5-(3-3)=5>0 =2-(5-3)=0=0 |
Полученный план оптимален.
Ответ: Z=2*40+2*80+3*10+1*60+3*20+2*80+0*4=550