Пример решения задачи с использованием приложения Microsoft Excel

На четыре базы В₁,В₂,В₃,В₄поступил однородный груз в количествах, соответственно равных 45, 45, 100 и 160 ед. Этот груз требу­ется перевезти в три магазина А_1, А₂, А₃, соответственно в количествах 180, 90 и 170 ед. По перевозке грузов имеются следующие ограничения: Х₁₁≥100, Х₃₂≤200. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначе­ния задана матрицей тарифов:

 

 

Пункты назначения	Пункты отправления	Потребности
А1	А2	А3
В1
В2
В3
В4
Запасы

Найдем сумму потребностей и сумму запасов:

и

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

 

Составим первый опорный план методом северо-западного угла:

Метод северо-западного угла (диагональный) - сущность способа заключается в том, что на каждом шаге заполняется левая верхняя клетка (северо-западная) оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из А_i, либо полностью удовлетворяется потребность В_j. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы а_i и не удовлетворятся все потребности b_j. В заключении проверяют, что найденные компоненты плана Х_ij удовлетворяют горизонтальным и вертикальным уравнениям.

 

Пункты назначения	Пункты отправления	Потребности
B1	B2	B3
А1
А2
А3
А4
Запасы

 

S₁=100*3+80*2+45*1+45*3+80*2=300+160+45+135+160=800(ед.),

Где S₁- это сумма перевозок;

 

 

Алгоритм решения задачи в приложении Microsoft Excel:

1. Создаем таблицу, как показано на рисунке:

 

2. В ячейку В18 записываем формулу =СУММ(В14:В17) и копируем ее в ячейки С18:Е18;

3. В ячейку Е14 записываем формулу =СУММ(В14:D14) и копируем ее в ячейки Е13:Е16;

4. В ячейку Е18 запишем формулу целевой функции =СУММПРОИЗВ(В4:D7;В14:D17);

5. Выполняем команду Сервис → Поиск решения;

 

6. В появившемся диалоговом окне устанавливаем следующие значения:

· Установить целевую ячейку $E$18,

· Равной: минимальному значению,

· Изменяя ячейки $В$14:$D$17,

· Ограничения:

$B$14:$D$17 = целое – чтобы в изменяемые ячейки помещались целые числа

$B$14:$E$17 >= 0 – чтобы значения не получились отрицательными,

$B$18:$D$18 <= $B$8:$D$8 – чтобы потребности оптимального плана брались из 1-ой таблицы.

$Е$14:$Е$17 = $Е$4:$Е$7 - чтобы запасы оптимального плана брались из 1-ой таблицы.

 

 

7. Далее нажимаем кнопку «Выполнить»;

8. Затем появится окно «Результаты поиска решения», в котором выбираем

9. «Сохранить найденное решение» и нажимаем кнопку «ОК»;

 

10. Сохраняем найденное решение.

 

11. В результате получим оптимальный план перевозок: в ячейках В14:D17 будет указанно количество груза, которое необходимо перевезти от i-го поставщика к j-ому потребителю, а в ячейке E18 (целевая ячейка) будет показана минимальная сумма перевозок S=800 ед.