3.8 Модификации транспортной задачи

Существуют различные модификации транспортной задачи, которые также могут быть решены методом потенциалов. Рассмотрим некоторые из них.

Задача с частично закрепленными связями– это транспортная задача, в которой заданы некоторые обязательные объемы поставок от конкретного поставщика к конкретному потребителю. Например, требуется обязательно хотя бы 10 холодильных установок перевезти из Стокгольма в Лион.

Такая задача сводится к обычной за счет уменьшения величин запасов и потребностей на заранее заданные объемы перевозки. Например, в задаче о холодильных установках следовало бы уменьшить запасы Стокгольма и потребности Лиона на 10 установок (a₁= 120 – 10 = 110,b₂= 90 – 10 = 80). После этого задачу можно решать методом потенциалов, но после того, как оптимальный план будет получен, перевозки из Стокгольма в Лион (x₁₂) следует увеличить на эти 10 холодильных установок.

Задача с частично запрещенными связями– это транспортная задача, в которой перевозки по каким-либо направлениям запрещены. Например, нельзя везти холодильные установки из Стокгольма в Лион.

Такая задача сводится к обычной путем установления стоимости перевозок c_ijдля запрещенной связи на очень высоком уровне (в масштабах модели). Для данного примера следует приравнять стоимость перевозки одной установки из Стокгольма в Лион вместо восьми, например, к тысяче (с₁₂= 1000). Поскольку в задаче о холодильных установках цены на перевозку измеряются в единицах и десятках фунтов стерлингов, число 1000 будет очень большим в масштабах модели. Однако, если бы цены измерялись в сотнях и тысячах, следовало бы выбрать другое число (например, 100000).

3.9 Порядок выполнения работы

1. Изучить методические указания к лабораторной работе.

2. Ответить на контрольные вопросы.

3. Самостоятельно построить открытую модель транспортной задачи и решить ее методом потенциалов (начать решение с опорного плана, построенного МСЗУ). После преобразования в закрытую в модели должно быть 4 поставщика и 5 потребителей (включая дополнительных).

4. При решении задачи с помощью ППП «Система деловых задач»^*сохранить данные задачи в файле с именем, составленным из своих инициалов (в папкеQSB). По окончании занятия перенести его в свою папку.

5. Проанализировать ход решения, рассмотрев его по итерациям.

6. Построить опорный план МАФ и проанализировать результаты использования этого метода.

7. При использовании ППП «Система деловых задач» изучить возможности корректировки исходных данных – удаление и ввод пунктов отправления и назначения, изменение их мощностей (запасов и потребностей), изменение коэффициентов целевой функции. При этом должны быть рассмотрены как открытая, так и закрытая модели транспортной задачи.

4 Оформление результатов работы

Отчет по лабораторной работе должен включать:

а) формулировку условий транспортной задачи в виде текста;

б) условия открытой и закрытой моделей транспортной задачи в виде задач линейного программирования;

в) опорные планы, построенные МСЗУ и МАФ;

г) ход решения задачи методом потенциалов;

д) результаты решения задачи (ответ).

5 Контрольные вопросы

1. Как ставится транспортная задача?

2. При каких условиях разрешима транспортная задача?

3. Расскажите об открытой и закрытой моделях транспортной задачи.

4. В чем заключается особенность опорного плана транспортной задачи?

5. В чем заключается метод северо-западного угла построения опорного плана транспортной задачи?

6. В чем заключается метод наименьшей стоимости построения опорного плана транспортной задачи?

7. В чем заключается метод аппроксимации Фогеля?

8. Сформулируйте теоремы об изменении плана и о критерии оптимальности транспортной задачи.

9. В чем заключается алгоритм метода потенциалов?

10. В каком случае оптимальный план транспортной задачи будет целочисленным?