- •Математическое программирование
- •Часть 2
- •30 Мая 2013, протокол № 10
- •Тема 2 транспортная задача линейного программирования (тз) 4
- •Закрытая и открытая модели транспортной задачи
- •2.2 Решение транспортной задачи
- •Алгоритм решения транспортной задачи
- •Нахождение начального опорного плана методом «минимального элемента»
- •Нахождение начального опорного плана методом «северо-западного угла»
- •Нахождение начального опорного плана методом Фогеля
- •Проверка на оптимальность невырожденного опорного плана методом потенциалов
- •Переход к новому опорному плану
- •Цикл пересчета
- •Тема 3 задача о назначениях
- •3.1 Математическая модель задачи о назначениях
- •Закрытая и открытая модели задачи назначениях
- •3.2 Решение задачи о назначениях
- •Алгоритм венгерского метода решения задачи о назначениях
- •Тема 4 динамическое программирование
- •4.1 Задача оптимального распределения ресурсов
- •I этап. Условная оптимизация.
- •II этап. Безусловная оптимизация.
- •4.1.11–4.1.16
- •4.2. Задача об оптимальной стратегии замены оборудования
- •I этап. Условная оптимизация.
- •II этап. Безусловная оптимизация.
- •4.2.1–4.2.10
- •Список использованной литературы
- •Математическое программирование
- •220114, Минск, ф.Скорины, 8/2
Нахождение начального опорного плана методом Фогеля
Данный метод состоит из ряда однотипных шагов (этапов), на каждом из которых:
для каждой линии (по строкам и столбцам) определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность (жирным шрифтом);
в линии с наибольшей разностью заполняется максимально возможным значением клетка, соответствующая минимальному тарифу;
исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Поставщик исключается из рассмотрения, если его запасы заканчиваются. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от него требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь затем поставщик исключается из рассмотрения. Аналогично поступают с потребителем.
Когда в процессе заполнения таблицы, на каком-то этапе незаполненными оказываются только клетки в одной линии, то их необходимо заполнить в порядке увеличения тарифов.
Данный метод позволяет построить опорный план, который достаточно близок к оптимальному, и зачастую может даже оказаться оптимальным.
Пример2.4
По данным примера 2.1 найти начальный опорный план методом Фогеля.
Решение
Воспользуемся распределительной таблицей закрытой модели ТЗ (таблица 2.3).
На первом этапе максимальная разность «4» принадлежит столбцу. Заполняем клетку с минимальным тарифом в этом столбце. Это клетка (2,4) и. Столбецисключаем, а в хранилищепри этом останется 90 – 40 = 50 т топлива.
На втором этапе максимальная разность «3» принадлежит строками. Выбираем любую из них, например, строку. Заполняем клетку с минимальным тарифом в этой строке. Это клетка (1,5) и. Столбецисключаем, а в хранилищепри этом останется 70 – 10 = 60 т топлива.
На третьем этапе максимальная разность «2» принадлежит столбцами. Выбираем любой из них, например, столбец. Заполняем клетку с минимальным тарифом в этом столбце. Это клетка (3,1) и. Исключаем по своему усмотрению либо третьего поставщика, либо первого потребителя. Пусть исключили первого потребителя. Тогда в хранилищеосталось 50 – 50 = 0 т топлива.
На четвертом этапе максимальная разность «3» принадлежит строке. Заполняем клетку с минимальным тарифом в этой строке. Это клетка (3,3) и. Строкуисключаем, а потребителюнедостает 40 – 0 = 40 т топлива.
На пятом этапе максимальная разность «2» принадлежит строкеи столбцу. Выбираем любую из этих линий, например, строку. Заполняем клетку с минимальным тарифом в этой строке. Это клетка (1,5) и. Строкуисключаем, а потребителюнедостает 70 – 50 = 20 т топлива.
Т.к. незаполненные клетки остались в одной линии (в строке клетки (1,2) и (1,3)), то заполняем их в порядке увеличения тарифов, т. е. сначала заполним клетку (1,3):, затем клетку (1,2) и.
Итак, в распределительной таблице найден невырожденный (число занятых клеток k = m + n – 1 = 3 + 5 – 1 = 7) начальный опорный план (таблица 2.6).
Таблица 2.6
|
|
|
|
|
|
|
Этапы |
| |||||||||
|
1 |
2 |
3 |
4 |
5 | ||||||||||||
|
|
5 |
|
4 |
|
3 |
|
6 |
|
0 |
70 |
3 |
3 |
1 |
1 |
1 | |
|
|
20 |
|
40 |
|
|
|
10 |
| ||||||||
|
|
4 |
|
3 |
|
5 |
|
1 |
|
0 |
90 |
1 |
3 |
1 |
2 |
2 | |
|
|
50 |
|
|
|
40 |
|
|
| ||||||||
|
|
2 |
|
4 |
|
1 |
|
5 |
|
0 |
50 |
1 |
1 |
1 |
3 |
– | |
50 |
|
|
|
0 |
|
|
|
|
| ||||||||
|
50 |
70 |
40 |
40 |
10 |
|
|
|
|
|
| ||||||
Э т а п |
1 |
2 |
1 |
2 |
4 |
0 |
|
|
|
|
|
| |||||
2 |
2 |
1 |
2 |
– |
0 |
|
|
|
|
|
| ||||||
3 |
2 |
1 |
2 |
– |
– |
|
|
|
|
|
| ||||||
4 |
– |
1 |
2 |
– |
– |
|
|
|
|
|
| ||||||
ы |
5 |
– |
1 |
2 |
– |
– |
|
|
|
|
|
|
или . Значение целевой функции на найденном начальном опорном плане (транспортные издержки для этого плана):
(усл. ден. ед.)