Открытая транспортная задача

 

Может оказаться, что сумма поставок не равна сумме потребностей, в этом случае имеем открытую модель транспортной задачи. Рассмотрим решение открытой транспортной задачи на примере.

Пример 2. Минимизировать транспортные расходы по доставке грузов от поставщиков А₁, А₂, А₃ к потребителям В₁, В₂, В₃, если заданы объем поставок и потребностей, а также тарифы по доставке единицы груза от каждого поставщика до каждого потребителя (в д.е.).

 

 

В А	7	17	23
8	2	4	10
20	5	11	7
24	3	6	5

 

 

Сумма поставок 8+20+24=52, сумма потребностей 7+17+23=47. Сумма поставок не равна сумме потребностей, поэтому мы имеем открытую модель транспортной задачи. Введем фиктивного потребителя с потребностью, равной 52-47=5 (ед. товара).

 

 

В А	7	17	23	5
8	2   7----	4 ----1	10   0	0      -5	-5
20	5 + ----- 9      4	11 --- 16	7   4	0   2   2	2
24	3   7      4	6   9	5 19	0 5	0

       7       9       5            0

 

Дочертим еще один столбец в таблице. Основные тарифы в этом столбце возьмем равные нулю. Далее решаем задачу как закрытую модель.

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

Число загруженных клеток должно равно m+ n-1=3+4-

-1=6 – невырожденный план. Улучшаем план по методу потенциалов.

В двух клетках получается одинаковая разность (косвенный тариф минус основной), она составляет 4 единицы. Если построить циклы с обеими этими клетками, то оба цикла дадут перемещение одинаковой стоимости, поэтому можно брать любой из них. Построим цикл с загружаемой клеткой (2;1).

По циклу перемещаем наименьшую отрицательную поставку 7.

 

 

В А	7	17	23	5
8	2   -2	4 8	10   0	0      -5	-7
20	5   7	11 9-----	7 ---- 4	0   2   2	0
24	3   3	6   + ----- 9      3	5 -----19	0 5	-2

                   5      11       7            2

 

 

По циклу перемещаем поставку 9.

 

В А	7	17	23	5
8	2   1	4 8	10   3	0      -4	-2
20	5   7	11       8	7 13---	-- +0  2  2	2
24	3   3	6 9	5 10---	0 ----5	0

                   3      6         5            0

 

По циклу перемещаем поставку 5.

 

В А	7	17	23	5
8	2   1	4 8	10   3	0      -4	-4
20	5   7	11       8	7   8	0 5	0
24	3   3	6 9	5 15	0       -2	2

              5      8         7            0

 

Последний план перевозок оптимален, так как все косвенные тарифы £ основных тарифов.

Посчитаем минимальную стоимость перевозок товаров (д.е.).

 

Пример решения транспортной задачи средствами Excel

 

Рассмотрим решение транспортной задачи заданной таблицей

 

Bj Ai	60	70	110
150	10	12	6
90	5	5	8

 

используя надстройку «Поиск решения» Excel.

 

  На рабочем листе Excel вводим исходные данные в виде таблицы

 

 

	A	B	C	D	E
1	10	12	6
2	5	5	8
3
4				0	150
5				0	90
6	0	0	0	0
7	60	70	110

 

 

Здесь в ячейках  введены стоимости перевозок. Ячейки  отведены под неизвестные значения объемов перевозок. В ячейках  введены объемы поставок, а в ячейках  объемы потребностей.

В ячейку , вводится формула для целевой функции =СУММПРОИЗВ(A1:C2;A4:C5).

В ячейки  вводятся формулы: =СУММ(A4:A5); =СУММ(B4:B5): =СУММ(C4:C5) определяющие объемы потребностей.

В ячейки  введены формулы: =СУММ(A4:C4); =СУММ(A5:C5) характеризующие объемы поставок

Запускаем команду «Поиск решения» и заполняем появившееся окно Поиск решения следующим образом. В поле «Оптимизировать целевую функцию» вводим ячейку . Выбираем оптимизации значения целевой ячейки «Минимум».

 В поле «Изменяя ячейки переменных» вводим изменяемые ячейки . В поле «В соответствии с ограничениями» вводим заданные ограничения с помощью кнопки «Добавить». $A$6:$C$6=$A$7:$C$7 $D$4:$D$5<=$E$4:$E$5.

Ставим флажок в поле «Сделать переменные без ограничений неотрицательными». Выбрать метод решения «Поиск решения линейных задач симплекс-методом». 

Нажатием кнопки «Найти решение» запускается процесс решения задачи. В итоге появляется диалоговое окно «Результаты поиска решения» и исходная таблица с заполненными ячейками для значений переменных и оптимальным значением целевой функции.

 

	A	B	C	D	E
1	10	12	6
2	5	5	8
3
4	40	0	110	150	150
5	20	70	0	90	90
6	60	70	110	1510
7	60	70	110

 

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

Лекция 4. Сетевое планирование