Открытые модели ТЗ и усложнения в ее постановке
Транспортная задача, в которой суммарные запасы и потребности совпадают, т. е. выполняется условие называется закрытой моделью; в противном случае – открытой. Для открытой модели может быть два случая:
а) суммарные запасы превышают суммарные потребности: ;
б) суммарные потребности превышают суммарные запасы: .
Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.
Открытая модель ТЗ решается приведением к закрытой модели. В случае (а), когда суммарные запасы превышают суммарные потребности, т.е. , вводится фиктивный потребитель (столбец ), потребности которого . В случае (б), когда суммарные потребности превышают суммарные запасы, т.е. , вводится фиктивный поставщик (строка ), запасы которого .
Стоимость перевозки единицы груза, как до фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.
После преобразований задача принимает вид закрытой модели и решается обычным способом. При равных стоимостях перевозки единицы груза, от поставщиков к фиктивному потребителю, затраты на перевозку груза реальным потребителям минимальны, а фиктивному потребителю будет направлен груз от наименее выгодных поставщиков. То же самое получаем и в отношении фиктивного поставщика.
Замечание 1. Прежде чем решать какую-нибудь транспортную задачу, необходимо сначала проверять, к какой модели она принадлежит, и только после этого непосредственно составлять распределительную таблицу.
|
|
Замечание 2.При составлении первоначального опорного плана методом минимальной стоимости или двойного предпочтения необходимо наименьшую стоимость выбирать только среди стоимостей реальных поставщиков и потребителей, а запасы фиктивного поставщика (потребности фиктивного потребителя) распределять в последнюю очередь. Это позволит получить план, более близкий к оптимальному.
Отмеченное во втором замечании используют также при введении фиктивно запятых клеток.
Пример 1
Составить план перевозок грузов с наименьшей общей стоимостью от четырех поставщиков ), соответственно, в количествах . К пяти потребителям соответственно, в количествах .. Стоимости перевозок единицы груза из каждого пункта отправления в каждый пункт назначения являются известными величинами и задаются матрицей
Решение Вычислим суммарные запасы и потребности. Соответственно: . Потребности превышают запасы на . Необходимо ввести фиктивного поставщика (строка ), запасы которого составят Получим закрытую модель ТЗ. Заполняем распределительную таблицу (табл. 2.13) методом минимальной стоимости.
|
|
Таблица 2.13
Bj Аi | B1 | B2 | B3 | B4 | B5 | Запасы ai |
А1 | 50 1 | 6 | 50 8 | 12 | 16 | 100 |
А2 | 16 | 10 | 0 8 | 200 6 | 200 15 | 400 |
А3 | 190 4 | 100 1 | 9 | 11 | 13 | 100 |
А4 | 3 | 0 2 | 100 7 | 7 | 15 | 100 |
А5 | 0 | 0 | 0 | 0 | 50 0 | 50 |
Потребности bj | 50 | 100 | 150 | 200 | 250 | 750 |
Получаем опорный план
проверяем его на оптимальность, для чего составляем систему уравнений потенциалов:
, | , | Полагая ,, найдём: | |
, | , | ||
, | |||
, | |||
, | |||
Проверив свободные клетки, находим, что получен оптимальный план.
Анализируя оптимальный план задачи, можно сделать следующие выводы. Потребитель , получает . груза от фиктивного поставщика, следовательно, его потребности будут не удовлетворены на это же количество единиц.
Дата добавления: 2018-04-05; просмотров: 406; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!