СКАЧАТЬ:  zanyatie3.zip [126,72 Kb] (cкачиваний: 71)

Решение транспортной задачи.

Одной из часто решаемых задач хозяйственного управления является задача по разработке рационального плана транспортных перевозок. Основная цель организации перевозок ­ минимизация затрат на их выполнение. В экономико-математическом моделировании эта задача получила название транспортной задачи (или задачей оптимизации прикрепления потребителей к поставщикам). Транспортные задачи нашли широкое применение при решении оптимизационных моделей регионального и межотраслевого регулирования, оптимизации размеров и размещения производств. 

 Общая постановка транспортной задачи.

В общем виде формулировка транспортной задачи осуществляется следующим образом: требуется перевезти определенное количество однородного груза из  m пунктов отправления в n пунктов назначения. Известны расходы на перевозку единицы груза из каждого пункта отправления в каждый пункт назначения.

Требуется составить такой план прикрепления потребителей к поставщикам, т.е. план перевозок, при котором весь груз от поставщиков вывозится, каждый потребитель получает требуемое количество груза, и вместе с тем, общая величина транспортных издержек минимальна.

Для составления экономико-математической модели задачи введем обозначения:

­число пунктов отправления;

  ­ число пунктов назначения;

  ­ общее количество груза в I-м пункте отправления;

  ­ общее количество груза, необходимое в j-м пункте назначения;

 ­ затраты на транспортировку единицы груза из I-го пункта

          отправления в j-й пункт назначения;

­ совокупные затраты на перевозку всего груза;

 ­ исходно неизвестное количество груза, которое перевозится из

         i-го пункта отправления в j-й пункт назначения.

Экономико-математическая модель задачи:

              (2.53)

                    (2.54)

                     (2.55)

                (2.56)

Целевая функция (2.53) минимизирует совокупные затраты на транспортировку всех партий грузов из всех пунктов отправления во все пункты назначения. Система ограничений (2.54) говорит о том, что весь груз из каждого пункта его сосредоточения должен быть вывезен. Система ограничений (2.55) говорит о том, что потребность в грузе в каждом пункте назначения должна быть удовлетворена. Система ограничений (2.56) говорит о том, что по любому маршруту некоторое количество груза либо перевозится, либо нет.

Транспортная задача является задачей линейного программирования с (n + m) ограничениями ­ уравнениями и (n*m) неизвестными.

Транспортная задача, у которой суммарное наличие груза совпадает с суммарной потребностью, т.е. выполняется равенство

                         (2.57)

называется закрытой (сбалансированной) транспортной задачей. Если условие (2.57) выполняется, то доказано, что транспортная задача имеет оптимальное допустимое решение. В случае если условие (2.57) не выполняется, то транспортная задача называется открытой. Решение транспортных задач с открытой моделью сводится к решению задач с закрытой моделью путем добавления  фиктивного поставщика или фиктивного потребителя так, чтобы выполнялось условие (2.57). Транспортная задача относится к задачам распределительного типа и решается симплексным методом. Приведем прием решения транспортной задачи с помощью средства EXCEL Поиск решения.

Условия транспортной задачи представлены в виде таблицы 2.6.                                                                                       

  Таблица 2.6

В примере однородный груз должен быть доставлен от четырех поставщиков (n=4) четырем потребителям (m=4). Мощности поставщиков () и потребность в этом грузе в каждом пункте назначения () приведены в таблице. В левых верхних углах каждой клетки рабочей таблицы, которые соответствуют всем возможным путям перевозки груза из всех пунктов отправления во все пункты назначения, указаны затраты на транспортировку единицы груза по данному маршруту (). Суммарные запасы груза (550) и потребности в грузе (550) совпадают, значит это закрытая транспортная задача. Требуется составить план перевозок, обеспечивающий минимальные затраты на транспортировку груза.

Подготовка к решению транспортной задачи в EXCEL.

Для решения задачи средством EXCEL «Поиск решения» необходимо разместить в рабочем листе исходные данные и подготовить поля для размещения условий и результатов решения задачи (выбор ячеек листа произвольный). Таким образом будет создана «Электронная модель транспортной задачи».

На рис. 2.2 приведен пример подготовки рабочего листа EXCEL для решения задачи.

                    Рис. 2.2  Пример подготовки размещения данных транспортной задачи для решения в EXCEL. 

Рекомендуется следующий порядок работы.

1)      Выделить диапазон ячеек:

           − для размещения исходной матрицы (A14:E19);

           − для размещения матрицы оптимальных перевозок (матрица для размещения результатов после решения задачи) (A4:F9), рекомендуется для наглядности в обе матрицы внести текст пояснений;

2) Матрицу исходных данных (A14:E19) заполнить данными таблицы_(значения ai, bj, cij).

В матрице  результата во все ячейки диапазона (B5:E9)  внести «1» в качестве исходных значений объемов поставок xij, после решения задачи в этих ячейках будут находиться значения поставок, обеспечивающие минимальные затраты на перевозку груза.

3) Ввести в ячейки (В10:Е10)  итог поставок по потребителям:   в ячейку В10 ввести формулу  =СУММ(В6:В9)    − итог поставок по1-му потребителю, скопировать эту формулу в ячейки (С10:Е10);

4) Ввести в ячейки (F6:F9) итоги реализации мощности каждого из поставщиков:  в ячейку F6 ввести формулу  =СУММ(В6:Е6)    − итог реализации поставок от 1-го поставщика, скопировать эту формулу в ячейки (F7:F9);

5) Выделить ячейку для ввода формулы целевой функции, например В21 и ввести формулу =СУММПРОИЗВ(В16:Е19;В6:Е9)   − суммарная стоимость перевозок по всем направлениям.

6) В окне Поиск решения указать целевую ячейку В21 равную минимальному значению, а также ввести следующие ограничения:                                                                                                   

7) Указать дополнительные условия решения задачи − условие неотрицательности переменных и линейность модели, остальные режимы работы принять по умолчанию.

После проведенной подготовительной работы можно запустить задачу на выполнение. В результате решения ячейки (В6:Е9) будут заполнены значениями объемов перевозок, которые обеспечивают минимальные суммарные затраты на транспортировку всего груза, а величина затрат выдается в ячейке В21.

Индивидуальные задания.

Вариант 1.

Вариант 2.

Вариант 3.

Вариант 4.

Вариант 5.

Вариант 6.

Вариант 7.

Вариант 8.

Вариант 9.

Вариант 10.

Вариант 11.

Вариант 12.

Вариант 13.

Вариант 14.

Вариант 15.

Вариант 16.

Вариант 17.

Вариант 18.

Вариант 19.

Вариант 20.

Вариант 21.

Вариант 22.

Вариант 23.

Вариант 24.