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

I этап. Постановка задачи

Описание задачи

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

В двух пунктах отправления А₁ и А₂ находится соответственно 150 и 90 т горючего. В пункты В₁, В₂, В₃ требуется доставить соответственно 60, 70 и 110 т горючего. Стоимости перевозки тонны горючего из пункта А₁ в пункты В₁, В₂ ,В₃ составляют соответственно 6, 10 и 4 денежные единицы, а из пункта А₂ – 12, 2 и 8 денежных единиц. Составить оптимальный план перевозок горючего так, чтобы общая сумма транспортных расходов была наименьшей.

Цель моделирования

Автоматизировать расчет объемов перевозок. Для этого необходимо составить таблицу-шаблон, позволяющую быстро рассчитать объемы перевозок и затраты на перевозку так, чтобы затраты на перевозку были минимальными.

Анализ объекта

В данной задаче рассматриваются объекты “затраты” и “объемы” перевозок, которые формируются на основе отдельных элементов, входящих в стоимость перевозок: тарифов на перевозку и объемов перевозок. Каждый объем перевозок задается объемом заказа и объемом запаса. Параметром плана перевозок являются затраты на перевозку.

Информационная модель

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

Обозначим искомые объемы перевозок от поставщиков к потребителям следующим образом:

а₁₁ – объем перевозки от поставщика А₁ к потребителю В₁;

а₁₂ – объем перевозки от поставщика А₁ к потребителю В₂;

а₁₃ – объем перевозки от поставщика А₁ к потребителю В₃;

а₂₁ – объем перевозки от поставщика А₂ к потребителю В₁;

а₂₂ – объем перевозки от поставщика А₂ к потребителю В₂;

а₂₃ – объем перевозки от поставщика А₂ к потребителю В₃;

Составляем ограничения на запасы

для поставщика А₁:

а₁₁+а₁₂+а₁₃=150

для поставщика А₂:

а₂₁+а₂₂+а₂₃=90

Составляем ограничения на заказы

для потребителя В₁:

а₁₁+а₂₁=60

для потребителя В₂:

а₁₂+а₂₂=70

для потребителя В₃:

а₁₃+а₂₃=110

Затраты на перевозку составят:

Z=6•а₁₁+10•а₁₂+4•а₁₃+12•а₂₁+2•а₂₂+8•а₂₃

Изменять значения а₁₁, а₁₂, а₁₃, а₂₁, а₂₂, а₂₃ так, чтобы удовлетворить всем ограничениям и получить минимальные затраты на перевозку продукции.

Компьютерная модель

Для моделирования будем использовать среду электронной таблицы.

1. Составляем таблицу исходных данных



рис. 1. Таблица с исходными данными

2. Вводим формулы в ячейки

В ячейку Е11 формулу =СУММ(B11:D11) . Объемы перевозимого горючего от поставщика А₁.

В ячейку Е12 формулу =СУММ(B12:D12) . Объемы перевозимого горючего от поставщика А₂.

В ячейку В13 формулу =СУММ(B11:В12) . Объемы перевозимого горючего к потребителю В₁.

В ячейку С13 формулу =СУММ(С11:С12) . Объемы перевозимого горючего к потребителю В₂.

В ячейку D13 формулу =СУММ(D11:D12) . Объемы перевозимого горючего к потребителю В₃

В ячейку В14 формулу =СУММПРОИЗВ(B5:D6;B11:D12). Затраты на перевозимое горючее от поставщиков к потребителям. Именно эта величина должна минимальной при перевозке горючего. Сами искомые объемы перевозок находятся в ячейках В11:D12. Начальные значения объемов перевозок вводим равные нулю. При выполнении поиска решения в этих ячейках будут оптимальные значения объемов перевозок. После ввода формул и начальных значений таблица примет вид:



рис. 2. Таблица с введенными формулами

3. В ячейке В14 находится формула вычисления затрат на перевозку горючего. Затраты на перевозку должны быть минимальными. Эта ячейка в терминологии Excel будет являться целевой. Для осуществления поиска решения необходимо задать ограничения и условия поиска. Выполняем действия Сервис| Поиск решения. На экране появится диалоговое окно Поиска решения.

рис. 3. Диалоговое окно поиска решения

В этой форме необходимо установить целевую ячейку $B$14 минимальному значению. Изменяя ячейки $B$11:$D$12. Для того, чтобы ввести адреса ячеек, нужно щелкнуть на значке справа от поля ввода, и затем в таблице выделить область (группу ячеек). Для того, чтобы задать ограничения, необходимо щелкнуть на кнопке Добавить. После этого появится форма для ввода ограничений.

рис. 4. Диалоговое окно ввода ограничений

В этой форме также для ввода адреса ячейки щелкнуть на значке справа от поля ввода. Знак отношений выбирается из списка, щелкнув на треугольнике справа от поля ввода. Для нашей задачи потребуются следующие ограничения:

$Е$11=$Е$5

$Е$12=$Е$6

$В$13=$В$7

$С$13=$С$7

$D$13=$D$7

Так как при поиске решения может оказаться нецелое число, то добавим в ограничения следующие записи:

$B$11= целое

$C$11= целое

$D$11= целое

$B$12= целое

$C$12= целое

$D$12= целое

После ввода условий поиска и ограничений диалоговое окно примет вид:

рис. 5. Диалоговое окно с введенными ограничениями

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

рис. 6. Окно задания параметров поиска решения

Затем щелкнуть на кнопке Выполнить. После этого на экране появятся результаты поиска. Щелкнуть на кнопке ОК.

рис. 7. Таблица с полученным решением

В ячейках B11:D12 будут находится значения, определяющие оптимальный план перевозок горючего. В нашей задаче затраты на перевозку составят 1020 условных денежных единиц.

III этап. Компьютерный эксперимент

1. Провести тестовый расчет компьютерной модели по данным, приведенным в таблице.
2. Провести расчет объемов перевозок со своими объемами заказов и объемами запасов продукции.
3. Изменить стоимости перевозок от поставщиков к потребителем и при исходных данных получить решение задачи.
4. Добавить поставщиков и дополнить модель расчетом по новым данным.
5. Добавить потребителей и дополнить модель расчетом по новым данным.

IV этап. Анализ результатов моделирования

Полученная модель позволяет автоматически пересчитывать объемы перевозок в зависимости от объемов заказов, объемов запасов и тарифов на перевозку единицы продукции.

Задание

Составить модель решения задачи.

В резерве трёх железнодорожных станций А, В и С находятся соответственно 60, 80 и 100 вагонов. Составить оптимальный план перегона этих вагонов к четырем пунктам погрузки хлеба, если пункту №1 необходимо 40 вагонов, №2 – 60 вагонов, №3 – 80 вагонов и №4 – 60 вагонов. Стоимость перегонов одного вагона со станции А в указанные пункты соответственно равны 1, 2, 3, 4 денежные единицы, со станции В – 4, 3, 2, 0 денежных единиц и со станции С – 0, 2, 2, 1 денежная единица.