Транспортная задача

Лабораторная работа 2

Тема “Транспортная задача”

Порядок работы

1.  Выбрать задачу в соответствии со своим номером.

2.  Написать математическую модель прямой и двойственной задачи, указав экономический смысл всех переменных.

3.  Подготовить данные в Exell и провести расчет  задачи.

4.  Проанализировать полученный результат.

Образец

1. Задача. Заводы фирмы расположены в городах Кандалакше, Ковдоре и Мурманск; они доставляют товары на склады городов Пол.Зори, Оленегорск и Ловозеро. Расстояния между этими городами приведены в таблице (расстояния округлены до десятков км).

Завод в городе Кандалакше выпускает в год 500 т товаров, в Ковдоре 200, а в Мурманске –500 т. Пол.Зоринский склад вмещает 400 т, Оленегорский - 600 т, а Ловозерский – 300 т, Ковдорский – 100 т. Как следует транспортировать товары для минимизации цен на перевозки?

2. Математическая модель задачи.

В данной задаче поставщики имеют 1200 т, а склады могут вместить 1400 т., т.е. не все склады могут быть загружены полностью. Для того, чтобы сделать задачу согласованной, введем фиктивный завод с объемом выпуска равным 200 т. Расстояние от фиктивного завода до поставщиков примем равным 0. Таким образом, число переменных в задаче равно 16 (n*m), число независимых условий равно 7 (r = n + m – 1).

Математическая модель прямой задачи:

Математическая модель двойственной задачи:

- расстояние между пунктами.

3. Заполним расчетные таблицы в Excel.

Подготовим таблицу расчета транспортной задачи для 8 поставщиков и 8 потребителей. В ячейки C4:J4 будут заноситься данные о потребителях, в ячейки  B5:B12 о поставщиках.

В ячейку K4 вводим формулу =СУММ(С4:J4), а в ячейку B13 -  =СУММ(B5:B12). Чтобы автоматическивидеть несогласованность данных, введем в ячейки K3 и A13 формулы =ЕСЛИ(B13>K4;B13-K4;0), =ЕСЛИ(K4>B13;K4-B13;0) соответственно. Теперь, если в ячейке K3 будет положительное число, следует ввести фиктивного потребителя с объемом равным K3. И, наоборот, если в ячейке A13 будет положительное число, следует ввести фиктивного поставщика с объемом равным А13.

В ячейки C5:J12 вводятся коэффициенты целевой функции, расстояния или стоимости перевозки. Нулевые значения можно не вводить. Ячейки C15:J22 отводятся для решения задачи. В ячейку В15 вводим формулу =СУММ(C15:J15), которую скопируем в ячейки B16:B22. В ячейку С23 вводим формулу =СУММ(C15:C22), которую скопируем в ячейки D23:J23. Если число потребителей менее 8, можно некоторые колонки скрыть. Ячейка В23 будет содержать значение целевой функции, для чего введем в эту ячейку следует ввести формулу: =СУММПРОИЗВ(C5:J12;C15:J22).

Переходим к поиску решения задачи. Поставив курсор в ячейку B23, выберем пункт меню СЕРВИС-ПОИСК РЕШЕНИЯ. Заполняем входные данные

целевая функция В23

минимум

изменяемые ячейки C15:J22

ограничения C15:J22  >= 0   

B15:B22  =  B5:B12

C23:J23 = C4:J4

Параметры  Линейность   OK     Выполнить

Если все сделано правильно, появится сообщение о том, что найдено оптимальное решение, после этого выбираем тип отчета    Устойчивость    OK.

Переходим на лист “Устойчивость”, копируем ячейки Е77:Е92, возвращаемся в текущий лист и вставляем скопированные ячейки в L5:L20. После этого возвращаемся и удаляем лист “Устойчивость”. В результате расчет получим таблицу, представленную ниже.

Замечания: а)Для удобства в ячейках С23:J23 (переменные задачи) определено условное форматирование, если значение равно нулю, цвет ячейки определен белым, т.е. невидимым. б)двойственные оценки поставщиков скопированы из ячеек L13:L20 в ячейки С24: J24.

4. Результаты расчета

Из Кандалакши везем 400 т в Полярные Зори и 100 т в Ловозеро, из Мурманска – 500 т в Оленегорск, Из Ковдора – 100 т в Оленегорск и 100 т остается в Ковдоре. Дефицит груза оказался в Ловозере в объеме 200 т. Общий объем перевозок – 106000ткм.

Двойственные оценки поставщиков и потребителей говорят, что для уменьшения затрат на перевозки следует увеличивать потребности 3 потребителя.