Задача 3. Транспортная задача с неправильным балансом.

На нескольких пунктах отправления А_i сосредоточено соответственно а_i единиц некоторого однородного груза. Этот груз необходимо доставить по нескольким пунктам назначения В_j, причем каждый из пунктов назначения может принять соответственно b_j единиц груза. Стоимость перевозки единицы груза из пункта отправления А_i в пункт назначения В_j равна c_ij ден. ед.

Пункты отправления Аi	Пункты назначения Вj		Запасы груза ai
	В1	В2
А1	с11 = 4,6	с12 = 3,3	67
А2	с21 = 1,8	с22 = 5,1	53
Потребности в грузе bj	78	39

Сформулировать математическую модель задачи как ТЗ. Определить оптимальный план перевозок, при котором общая стоимость перевозок была бы наименьшей.

Решение:

Поскольку данная модель несбалансирована (суммарный объем запасов груза не равен суммарному объему потребностей в нём), то в этой модели надо учитывать издержки, связанные как со складированием, так и с недопоставками продукции.

Так как сумма запасов (67+53=120) больше потребности в грузе (78+39=117), введем в модель фиктивный пункт назначения, стоимость перевозки единицы груза полагаются равными нулю, так как груз не перевозится, а объемы перевозок объемам складирования излишков продукции на пунктах отправления.

Пункты отправления Аi	Пункты назначения Вj			Запасы груза ai
	В1	В2	В3
А1	с11 = 4,6	с12 = 3,3	с13 = 0	67
А2	с21 = 1,8	с22 = 5,1	с23 = 0	53
Потребности в грузе bj	78	39	3

Для решения данной задачи построим ее математическую модель:

Неизвестными в данной задаче являются объемы перевозок. Пусть x_ij – объем перевозок с i-того пункта отправления в j-й пункт назначения. Функция цели – это суммарные транспортные расходы, т. е. где с_ij – стоимость перевозки единицы продукции с с i-того пункта отправления в j-й пункт назначения. Неизвестные в данной задаче должны удовлетворять следующим ограничениям:

1. Объемы перевозок не могут быть отрицательными.

2. Так как модель несбалансирована, то вся продукция должна быть вывезена с фабрик, а потребности всех центров распределения должны быть полностью удовлетворены.

В результате имеем следующую модель:

– минимизировать при ограничениях:

;

;

где a_ij – запас на i-том пункте отправления, b_j – потребность в j-м пункте назначения

Решение задачи с помощью MS Excel

1. Вводим данные, как показано на рис. 4.1.

Рис. 4.1. Исходные данные транспортной задачи

В ячейки А1:С3 введены стоимости перевозок. Ячейки А4:С3 отведены под значения неизвестных (объемы перевозок). В ячейки Е4:Е5 введены объемы запасов в пунктах отправления, а в ячейки А7:С7 введена потребность в пунктах назначения. В ячейку D6 введена целевая функция =СУММПРОИЗВ(А1:C3; А4:C5).

В ячейки А5:C5 введены формулы

=СУММ(А4:А5)

=СУММ(В4:В5)

=СУММ(С4:С5), определяющие объем продукции, ввозимой в пункты назначения.

В ячейки D4:D5 введены формулы

=СУММ(А4:С4)

=СУММ(А5:С5), вычисляющие объем продукции, вывозимой из пунктов отправления.

2. Выбраем команду Сервис/Поиск решения и заполняем открывшееся диалоговое окно Поиск решения как показано на рис. 4.1. В диалоговом окне Параметры поиска решения установливаем флажок Линейная модель.

Рис. 3.2. Диалоговое окно Поиск решения для транспортной задачи

3. Нажимаем кнопку Выполнить и средство поиска решений находит оптимальный план отгрузки продукции и соответствующие ему транспортные расходы (рис. 3.3).

Рис. 3.3. Оптимальное решение транспортной задачи