Лаб. 5 Документ Microsoft Word

Лабораторная работа № 5. Закрытая транспортная задача.

Цель работы. Познакомиться с математической моделью закрытой транспортной задачи

Содержание

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

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

Пример 1. В двух пунктах отправления А₁ и А₂ находится соответственно 150 и 90 тонн груза. В пункты В₁, В₂ и В₃ требуется доставить соответственно 60, 70 и 100 тонн груза. Стоимости перевозок тонны грузы из пункта А_i в пункты B_j записаны матрицей:

.

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

Запишем исходные данные в таблицу .

Bj Ai	60	70	110	ui
150	10 60	12 70 -	6 + 20	10
90	5 4	5 λ + 6	8 - 90	4
vj	0	2	4

Заполнение начнем с клетки (1; 1): , первый столбец закрыт. Переходим к клетке (1; 2): , второй столбец закрыт; далее, переходим к клетке (1; 3): . Т.к. в третьем столбце остался остаток, равный 90, то переходим к заполнению клетки (2; 3): . Опорное исходное решение построено. Этому плану соответствуют затраты в количестве:

руб.

Получив исходное решение, перейдем теперь к построению новых опорных решений, улучшающих друг друга: для этого применим метод потенциалов.

После построения опорного решения все переменные разбиты на 2 группы: x_kl – базисные и x_pq – свободные, где (p, q) – пустая клетка. Линейные функции выразятся через свободные так:

. (1)

Для нахождения коэффициентов γ_pq при свободных переменных сопоставим каждому пункту отправления A_i некоторую величину u_i, которую назовем потенциалом пункта A_i, и каждому пункту назначения B_j величину v_j – потенциал пункта B_j. Эти величины связаны равенством

, (2)

где c_kl – стоимость перевозки одной тонны груза из A_k в B_l. Доказывается, что совокупность уравнений (2), составленных для всех базисных переменных, составляет совместную систему линейных уравнений, причем значение одной из переменных можно задавать произвольно, тогда значения остальных переменных находятся из системы однозначно. Обозначим для свободных переменных сумму соответствующих потенциалов через , т.е. и назовем ее косвенной стоимостью. Тогда коэффициенты γ_pq в (1) определяются так:

.

Если все величины γ_pq неотрицательны, то исходное решение является оптимальным.

В нашем случае γ₂₂= -1. Следовательно, оптимальное решение не достигнуто. План можно улучшить, «загружая» максимально клетку (2; 2). В данную клетку поместим λ (т.). Осуществляем перераспределение груза, выбрав подходящий контур, состоящий их горизонтальных и вертикальных отрезков. Выбираем λ с таким расчетом, чтобы вместо клетки, в которую поместили λ, пустой стала ранее «загруженная» клетка, баланс груза по строкам и столбцам сохранился, поставки не были отрицательными, количество загруженных клеток не превышало m+n-1. Получается квадратный контур:

70- λ 20+ λ

λ 90- λ

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

Bj Ai	60	70	110	ui
150	10 60 -	12 3	6 + 90	0
90	5 λ + 12	5 70	8 - 20	2
vj	10	3	6

Вычисляем транспортные расходы:

руб.

Находим потенциалы и косвенные тарифы. В клетке (2; 1) отрицательная разность. Следовательно, оптимальное решение не достигнуто. План можно улучшить максимально «загружая» клетку (2; 1). Повторяя предыдущее рассуждение, получим

Bj Ai	60	70	110	ui
150	10 40	12 10	6 110	10
90	5 20 12	5 70	8 1	5
vj	0	0	-4

Вычисляем транспортные расходы:

руб.

Вычисляем потенциалы и косвенные тарифы. Т.к. все величины γ_pq неотрицательны, то оптимальный план достигнут и тем самым задача решена.

Рассмотрим решение этой транспортной задачи, используя надстройку «Поиск решения» 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

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

Задания для самостоятельной работы

Задание 1. Однородный груз сосредоточен у двух поставщиков в объемах а₁, и а₂ тонн. Данный груз необходимо доставить трем потребителям в объемах b₁, b₂, b₃ тонн. Известны стоимости перевозки единицы груза от каждого i-того поставщика каждому j-тому потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков будут вывезены полностью, запросы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.

Исходные данные транспортной задачи записаны в таблице.

1. 2.

Bj Ai	50	40	80		Bj Ai	50	100	100
70	5	3	7		100	7	8	3
100	5	4	6		150	4	9	2

3. 4.

Bj Ai	70	70	60		Bj Ai	100	50	100
120	4	6	6		150	7	5	3
80	3	7	2		100	6	2	3

5. 6.

Bj Ai	70	70	60		Bj Ai	70	100	40
80	9	8	4		140	8	4	6
120	10	2	4		70	7	3	2

7. 8.

Bj Ai	100	100	50		Bj Ai	70	80	100
170	5	6	2		160	7	2	3
80	2	4	2		90	5	4	4

9. 10.

Bj Ai	80	100	70		Bj Ai	70	80	100
160	7	4	2		90	5	7	5
90	5	3	1		160	3	6	6

11. 12.

Bj Ai	80	100	70		Bj Ai	120	80	100
90	5	4	3		200	7	5	4
160	2	3	5		100	3	4	7

13. 14.

Bj Ai	80	120	100		Bj Ai	100	80	120
200	5	7	3		200	5	4	7
100	5	6	5		100	5	1	4

15. 16.

Bj Ai	100	120	80		Bj Ai	150	40	110
200	5	4	4		120	5	2	3
100	3	5	6		180	3	2	3

17. 18.

Bj Ai	150	110	40		Bj Ai	40	110	150
120	5	2	3		120	3	4	5
180	3	2	3		180	3	2	5

19. 20.

Bj Ai	110	40	150		Bj Ai	110	150	40
120	3	4	5		120	3	4	5
180	3	2	5		180	3	2	5

21. 22.

Bj Ai	40	150	110		Bj Ai	150	40	110
120	3	4	5		180	3	4	5
180	3	2	5		120	3	2	5