Читайте также:
|
Задача открытого типа. Чтобы привести задачу к закрытой, введем фиктивного потребителя - магазин №6 с потребностью 
тонн продукции в сутки. Тарифы на поставки в этот магазин положим нулевыми.
Построим начальный опорный план методом минимального тарифа.
Минимальный тариф в таблице равен 0 (клетки 
). Заполним клетку 
. Мощность первого поставщика равна 60, потребность шестого потребителя равна 50. Проставим в клетку 50 единиц груза. Потребность шестого потребителя исчерпана, выведем его из рассмотрения. Оставшаяся мощность первого поставщика равна 60-50 =10
| 
| 
| 
| 
| 
| |||||||
| ||||||||||||
| ||||||||||||
| ||||||||||||
Минимальный тариф в таблице равен 5 (клетки 
). Заполним клетку 
. Мощность первого поставщика равна 10, потребность пятого потребителя равна 80. Проставим в клетку 10 единиц груза. Мощность первого поставщика исчерпана, выведем его из рассмотрения. Оставшаяся потребность пятого потребителя равна 80-10 =70.
Заполним клетку 
. 
проставим в клетку 50 единиц груза. Потребность третьего потребителя исчерпана, выведем его из рассмотрения. Оставшаяся мощность второго поставщика равна 100 - 50 = 50.
Заполним клетку 
. 
проставим в клетку 70 единиц груза. Потребность пятого потребителя исчерпана, выведем его из рассмотрения. Оставшаяся мощность третьего поставщика равна 160 - 70 = 90.
|
|
|
|
|
|
| |||||||
|
| ||||||||||||
|
| ||||||||||||
|
| ||||||||||||
Минимальный тариф в таблице равен 7 (клетка 
). Заполним клетку. 
проставим в клетку 50 единиц груза. Потребность второго потребителя исчерпана, выведем его из рассмотрения. Оставшаяся мощность третьего поставщика равна 90 - 50 = 40.
|
|
|
|
|
|
| |||||||
|
| ||||||||||||
|
| ||||||||||||
|
| ||||||||||||
Минимальный тариф в таблице равен 8 (клетка 
). Заполним клетку. 
проставим в клетку 30 единиц груза. Потребность первого потребителя исчерпана, выведем его из рассмотрения. Оставшаяся мощность третьего поставщика равна 40 - 30 = 10.
|
|
|
|
|
|
| |||||||
|
| ||||||||||||
|
| ||||||||||||
|
| ||||||||||||
Распределим оставшийся груз в клетки 
. Начальный опорный план:
|
|
|
|
|
|
| |||||||
|
| ||||||||||||
|
| ||||||||||||
|
| ||||||||||||
Количество строк 
столбцов 
, количество заполненных (базисных) клеток 
, начальный план невырожденный.
Стоимость перевозок составит
Проверим найденный план на оптимальность. Запишем для каждой заполненной клетки уравнение 
(8 уравнений), добавим к ним уравнение 
. Получим систему из 9 уравнений относительно 9 переменных 
(их называют потенциалами).
Решая систему, получим:
Для удобства проставим найденные потенциалы в таблицу:
|
|
|
|
|
|
| ||||||||
|
|
| ||||||||||||
|
| 
| ||||||||||||
|
| 
| ||||||||||||
| 
| 
| 
| 
| 
|
Теперь для каждой клетки определим величину
Текущий план оптимален, если для всех клеток оценки 
. Найдем оценки 
.
|
|
|
|
|
|
| ||||||||
|
| -1 | -6 |
| ||||||||||
|
|
| ||||||||||||
|
|
| ||||||||||||
|
|
|
|
|
|
|
Среди оценок есть отрицательные, текущий план неоптимален.
Выберем клетку 
, содержащую отрицательную оценку. Построим для нее цикл пересчета:
В клетках со знаком «-» содержится 10 и 10 единиц груза. Переместим по циклу 10 единиц груза, получим новый план. Чтобы этот план не был вырожденным, оставим в одной из клеток фиктивную нулевую перевозку.
|
|
|
|
|
|
| ||||||||
|
| 
| ||||||||||||
|
| 
| ||||||||||||
|
| 
| ||||||||||||
| 
| 
| 
| 
| 
|
Снова найдем потенциалы, проставляя их сразу в таблицу, и величины
|
|
|
|
|
|
| ||||||||
|
|
| ||||||||||||
|
| -5 | 
| |||||||||||
|
| -6 | 
| |||||||||||
| 
| 
| 
| 
|
|
Для клетки 
, содержащей максимальную по модулю отрицательную оценку, единственный цикл пересчета проходит через клетку с фиктивной перевозкой:
Переместим фиктивную перевозку в эту клетку.
|
|
|
|
|
|
| ||||||||
|
|
| ||||||||||||
|
|
| ||||||||||||
|
|
| ||||||||||||
|
|
|
|
|
|
|
Потенциалы и оценки:
|
|
|
|
|
|
| ||||||||
|
| -1 |
| |||||||||||
|
| -1 | -1 | -5 |
| |||||||||
|
|
| ||||||||||||
|
|
|
|
|
|
|
Для клетки 
, содержащей максимальную по модулю отрицательную оценку, построим цикл пересчета
Переместим по циклу 50 единиц груза, оставив в одной из клеток фиктивную перевозку.
|
|
|
|
|
|
| ||||||||
|
|
| ||||||||||||
|
|
| ||||||||||||
|
|
| ||||||||||||
|
|
|
|
|
|
|
Потенциалы и оценки:
|
|
|
|
|
|
| ||||||||
|
|
| ||||||||||||
|
|
| ||||||||||||
|
| 
| ||||||||||||
| 
|
|
| 
| 
|
Все оценки неотрицательны, полученный план - оптимальный. Отбросив фиктивного потребителя и фиктивные перевозки, получим оптимальный план исходной задачи:
|
|
|
|
|
| ||||||
|
| ||||||||||
|
| ||||||||||
|
| ||||||||||
Стоимость перевозок составит 
Ответ. Стоимость перевозок составит 
. Оптимальный план:
|
|
|
|
|
| ||||||
|
| ||||||||||
|
| ||||||||||
|
| ||||||||||
Дата добавления: 2015-01-07; просмотров: 61 | Поможем написать вашу работу | Нарушение авторских прав |