Транспортная задача линейного программирования задачник

4. 3 Примеры решения транспортных задач.

Условие: Студенческие отряды СО-1, СО-2 и СО-3 численностью 70, 99 и 80 человек принимают участие в сельскохозяйственных работах. Для уборки картофеля на полях П₁, П₂, П₃ и П₄ необходимо выделить соответственно 47, 59, 49 и 43 человека. Производительность труда студентов зависит от урожайности картофеля, от численности отряда и характеризуется для указанных отрядов и полей в центнерах на человека за рабочий день и представлена в матрице:

1. Распределить студентов по полям так, чтобы за рабочий день было собрано максимально возможное количество картофеля;
2. Определить, сколько центнеров картофеля будет убрано с четырех полей при оптимальном распределении студентов

1.Проверяем задачу на сбалансированность.

Составляем математическую модель прямой и двойственной задач.

Математическая модельпрямой задачи:Целевая функция (на максимум)Система ограничений:

Математическая модель двойственной задачи.

Решаем задачу по методу максимального элемента.

Составляем опорный план (табл. 2) Табл.2

BjAi		П1		П2	П3	П4		П5		Ui
		47		59	49	43		51
СО-1	70	3		597	2	11–W		+W		U1=-1
						5	0
СО-2	99	18 -W		49	32	+W6	0	U2= 0
		2	3	4
СО-3	80	29	+W	51	-W	U3 =4
			6	4	3		5		0
Vj		V1=2		V2=8	V3=4	V4=6		V5= -4		W=11

Проверяем на вырожденность. Z= m+n-1=3+5-1=7Базисных клеток 7. План не вырожден. Проверяем опорный план на оптимальность. Задаем U₂= 0и определяем значения потенциалов. Вычисляем оценки для всех незаполненных клеток (_ij) Опорное решение не является оптимальным, так как имеются отрицательные оценки. Переходим к следующему плану. Для клетки (1,5) с наименьшей оценкой (-5) строим цикл. Ставим в эту клетку коэффициент W со знаком «+» и применяя метод наибольшего элемента находим цикл, (табл. 2). Определяем из цикла W=11 Осуществляем сдвиг по циклу и строим следующий план (табл. 3) . Табл.3

BjAi		П1		П2	П3	П4	П5		Ui
		47		59	49	43	51
СО-1	70	3		597	2	11		U1=4
						5	0
СО-2	99	7 -W		49	43	+W		U2= 0
		2	3	4	6	0
СО-3	80	40	+W	40	-W	U3 =4
		6		4	3		5	0
Vj		V1=2		V2=3	V3=4	V4=6	V5= -4

Проверяем план на оптимальность методом максимального элемента, как в п.З. Задаем U₂ = 0 и определяем значения потенциалов. Вычисляем оценки для всех незаполненных клеток (_ij) Определяем из цикла W=7 Осуществляем сдвиг по циклу и строим следующий план (табл. 4). Табл. 4

BjAi		П1	П2	П3	П4	П5	Ui
		47	59	49	43	51
СО-1	70	3	597	2	11	U1=0
					5		0
СО-2	99	2	3	494	436	70	U2= 0
СО-3	80	476	4	3	5	330	U3 =0
Vj		V1=6	V2=7	V3=4	V4=6	V5= 0

Проверяем план на оптимальность методом максимального элемента, как в п.З. Задаем U₂= 0 и определяем значения потенциалов. Вычисляем оценки для всех незаполненных клеток (_ij) план табл. 4 оптимален. Определяем значение целевой функции прямой и двойственной задачи: Исходя из первой теоремы двойственности в условии нашей задачи Z_max=Z_min=1149 (Z=Z’) последний план оптимален Ответ:

1. Чтобы за рабочий день было убрано максимально возможное количество картофеля, следует распределить студентов по полям следующим образом:

– Из СО-1 выделить 59 человек для уборки картофеля на втором поле П₂, а 11 человек останутся в СО; – из СО-2 выделить 49 человек для уборки картофеля на П_З и 43 человека для уборки картофеля на П₄, а 7 человек останутся в СО; – из СО-3 выделить 47 человек для уборки картофеля на П₁, а 33 человека оставить в СО.

1. При данном оптимальном распределении студентов с четырех полей будет убрано 1149 центнеров картофеля.

Пример № 2 План перевозок:

ПоставщикиАi			Потребители Вj:
Запасы аi	Себестоимость	В1	В2	В3	В4
		350	250	150	250
А1	400	2	2	6	4	7
А2	300	3	6	2	7	1
А3	500	1	6	10	7	5

Решение: Проверяем на сбалансированность Задача не сбалансированная. Введем фиктивного потребителя В₅ с потребностью в грузе, равной 200 ед. Стоимость перевозки для фиктивного потребителя определим равной нулю. В качестве общей стоимости будем брать сумму затрат на доставку единицы продукции из соответствующего пункта и ее себестоимость в этом пункте. Математическая модель прямой задачипри условии что,

Математическая модель двойственной задачи:Экономический смысл переменных: Z – целевая функция прямой задачи (суммарные затраты); Z‘ – целевая функция двойственной задачи (суммарная потенциальная прибыль от перевозки груза); С_ij – стоимость перевозки единицы продукции из i-го пункта в j-ый; X_ij – объем перевозок от i-го поставщика j-му потребителю; U_i – условная плата перевозчику за вывоз единицы груза из i-го пункта отправления; V_j – условная плата перевозчику за доставку единицы груза в j-ый пункт назначения.

ПотребителиПоставщики		В1	В2		В3		В4	В5		Ui
		350	250		150		250	200
А1	400	3504	8		50 —W		+W		U1=-2
					6	9	0
А2	300	9	100 +W		200	-W0	U2=-6
			5	10	4
А3	500	7	150	—W	100	+W8	2506	0		U3 =0
				11
Vj		V1=6	V2=11		V3=8		V4=6	V5= 6		W=50

Проверяем на вырожденность: R=m+n-1=3+5-1=7 m= 3 – количество поставщиков; n = 5 – количество потребителей. Базисных клеток 7, план не вырожден. Проверяем план на оптимальность, используя метод потенциалов. Для базисных клеток составляем систему уравнений U_i + V_j = С_ij находим значение потенциалов так как переменных на 1 больше, чем уравнений, то переменной U₃ присваиваем значение 0 и решаем систему уравнений, получаем Проверяем выполнение неравенства в свободных: клеткахU_i + V_j ≤ С_ijболее всего не выполняется условие U_i + V_j ≤ С_ij, сюда ставим «+W», строим контур перераспределения W и находим его значение: Перераспределяем W=50по контуру. Составляем следующий план:

ПотребителиПоставщики		В1		В2		В3	В4	В5		Ui
		350		250		150	250	200
А1	400	350	—W	50 +W		U1=-6
			4	8			6	9	0
А2	300	9	150 +W		150	-W0	U2=-6
			5	10	4
А3	500	+W	100	—W	1508	2506	0		U3 =0
		7		11
Vj		V1=10		V2=11		V3=8	V4=6	V5= 6		W=100

Так как переменных наi больше, чем уравнений, то переменной U₃ присваиваем значение 0 и решаем систему уравнений, получаем проверяем выполнение неравенства в свободных клетках U_i + V_j ≤ С_ij, – более всего не выполняется условие U_i + V_j ≤ С_ij, сюда ставим «+W», строим контур перераспределения W и находим его значение: перераспределяем W=100 по контуру. Составляем следующий план:

ПотребителиПоставщики		В1	В2	В3	В4	В5	Ui
		350	250	150	250	200
А1	400	2504	8	6	9	1500	U1=-3
А2	300	9	2505	10	4	500	U2=-3
А3	500	1007	11	1508	2506	0	U3 =0
Vj		V1=7	V2=8	V3=8	V4=6	V5= 3

Проверяем выполнение неравенства U_i + V_j ≤ С_ij, в свободных клетках: Неравенство U_i + V_j ≤ С_ij,в свободных клетках выполняется, построенной план является оптимальным. Анализ решения.

1. Оптимальный план перевозки продукции:

– от поставщика А₁ перевозится 250 ед. продукции потребителю В₁; 150 ед. продукции остается у поставщика; – от поставщика А₂ перевозится 250 ед. продукции потребителю В₂; 50 ед продукции остается у поставщика; – от поставщика А₃ перевозится 100 ед.продукции потребителю В₁, 150 ед, потребителю В₃, 250 ед. потребителю В₄ . 2.Суммарные затраты на изготовление и перевозку продукции: ден. ед. Контрольные вопросы. 1.Как сформулировать постановку транспортной задачи ? 2.Какие величины в математической модели транспортной задачи постоянные и какие переменные? 3.Как составить математическую модель прямой и двойственной транспортной задачи? 4.Какая клетка в плане транспортной задачи называется «базисной» и какая «свободной»? 5.Приведите пример сбалансированной и несбалансированной транспортной задачи. Как сбалансировать исходный план транспортной задачи? 6.Поясните понятие «вырожденность» и «невырожденность» плана. Как построить «невырожденный» план? 7.Алгоритм метода наименьшего (наибольшего) элемента. 8.Метод потенциалов и его алгоритм. 9.Какой план транспортной задачи называется опорным? 10.Какой критерий оптимальности плана транспортной задачи? 11.Поясните понятие «коэффициент перераспределения груза – W» и как он определяется? 12.Как построить контур перераспределения W? 13.Анализ решения транспортной задачи.

Источник

Решение транспортных задач линейного программирования

Среди всех задач линейного программирования (ЗЛП) особняком стоят несколько типов, в частности, транспортные задачи. Конечно, и их можно решить общепринятым симплекс-методом, но вычисления получатся неоправданно сложными и объемными из-за размерности задачи (например, для самой простой задачи с 3 складами и 3 поставщиками — 9 ограничений и 9 переменных).

Поэтому для решения транспортных задач были разработаны специальные методы: для нахождения опорного/начального плана (минимального элемента, северо-западного угла, Фогеля), и для нахождения оптимального плана (метод потенциалов, дифференциальных рент, распределительный метод).

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

Примеры решений транспортных задач ЛП некоторыми из этих методов приведены в этом разделе — изучайте, ищите похожие, решайте (также вы можете перейти к примерам решения ТЗ в Excel). Если вам нужна помощь в выполнении подобных заданий, перейдите в раздел: Решение контрольных работ по линейному программированию.

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

Задача 1. Из трех холодильников A_i, i=1..3, вмещающих мороженную рыбу в количествах a_i т, необходимо последнюю доставить в пять магазинов B_j, j=1..5 в количествах b_j т. Стоимости перевозки 1т рыбы из холодильника A_i в магазин B_j заданы в виде матрицы C_ij, 3×5.
Написать математическую модель задачи и спланировать перевозки так, чтобы их общая стоимость была минимальной.

Задача 2. Построить закрытую модель транспортной задачи.

Задача 3. В таблице приведены исходные данные транспортной задачи: заданы удельные транспортные расходы на перевозку единицы груза, слева указаны возможности поставщиков, а сверху – спрос потребителей. Сформулируйте экономико-математическую модель транспортной задачи, распределительным методом найдите оптимальный план перевозок.
(таблица в файле)

Задача 4. Решить транспортную задачу
1) методом потенциалов (опорный план построить всеми известными способами);
2) методом дифференциальных рент;
3) любым методом при ограничениях: x₂₄≥4, x₃₅≤5, x₁₂=3.
(таблица в файле)

Задача 5. Выполнить решение в программе QM for Windows
Числа в скобках – коэффициенты транспортных расходов, столбец чисел справа от матрицы – запасы груза у поставщиков, строка снизу – потребности потребителей.
1. Решить и проанализировать ТЗ без ограничений.
2. Решить ТЗ с запретом перевозки по самому выгодному пути (с наименьшими затратами).
3. Решить двухэтапную ТЗ с числом поставщиков – 3, складов – 2 и потребителей – 4, взяв за c_ik первых два столбца коэффициентов исходной матрицы, а за c_kj – последние две строки этой матрицы. Мощности складов одинаковы и равны половине суммарных запасов поставщиков, округлённых до целых десятков в большую сторону.

Задача 6. Составить математическую модель транспортной задачи и решить её методом потенциалов. Завод имеет 3 цеха А, В, С и 4 склада №1,2,3,4. Цех А производит 30 тыс.штук изделий, цех В – 40 тыс. штук изделий, С – 20 тыс. штук изделий. Пропускная способность склада №1 — 20 тыс. штук изделий, №2 — 30 тыс. штук изделий, №3 – 30 тыс.штук, №4 – 10 тыс. штук. Стоимость перевозки из цеха А соответственно в склады №1,2,3,4 1 тыс. штук изделий составляет 20, 30, 3, 4 р., из цеха В 1 тыс. – соответственно 3, 20, 5, 1 р., а из цеха С – соответственно 4, 30, 2, 6 р.
Составить такой план перевозок изделий, при котором расходы на перевозку 90 тыс. изделий были бы наименьшими.

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

Задача 7. Имеется сеть железных дорог, на которой расположены 3 пункта отправления однородного груза и 9 станций его приема. Известны затраты на перевозку грузов от i-ой до j-ой станции. Заданы объемы ресурсов в каждом пункте отправления и объемы прибытия в каждый пункт назначения. Требуется составить оптимальный план перевозок, предусматривающий минимальные суммарные затраты.
1. Пункты 1, 2, 3 — пункты отправления с объемом запаса, соответственно 200, 150 и 150. Потребности пунктов назначения таковы: 4 — 40, 5 — 70, 6 — 40, 7 — 50, 8 — 45,9 — 60,10 — 70,11 — 75,12 — 50. Затраты между соответствующими вершинами заданы: 1-5 — 65, 1-7 — 75, 1-9 — 25, 2-5 — 60, 2-6 — 115, 2-9 — 25, 2-12 — 90, 3-4 — 95, 3-8 — 30, 3-10 — 45, 3-11 — 40, 4-8- 15, 4-12 — 40, 5-7 — 95, 5-9 — 35, 6-8 — 65, 6-9 — 15, 6-11 — 55,6-12 — 80,7-10 — 15,8-11 — 45,9-11 — 35,10-11-110.
2. Пункты 1, 2, 3 — пункты отправления с объемом запаса, соответственно 200,150 и 150. Потребности пунктов назначения таковы: 4 — 40, 5 — 70, 6 — 40, 7 — 50, 8-45,9-60,10-70,11 -75,12-50. Затраты между соответствующими вершинами заданы: 1-5 — 65, 1-7 — 75, 1-9 — 25, 2-5 — 60, 2-6 — 115, 2-9 — 25, 2-12 — 90, 3-4 — 95, 3-8 — 30, 3-10 — 45, 3-11 — 40, 4-8 — 15, 4-12 — 40, 5-7 — 95, 5-9 — 35, 6-8 — 65, 6-9 — 15, 6-11 — 55,6-12 — 80,7-10 — 15,8-11 — 45, 9-11 — 35,10-11 -110.
Для следующих звеньев существуют ограничения на пропускные способности. 1-7 — 40, 1-11 — 10, 2-9 — 15, 3-10 — 30.

Задача 8. Пункты производства и потребления связаны между собой транспортной сетью. В пунктах производства сосредоточено некоторое количество однородного груза, которое необходимо вывезти в пункты потребления. Стоимость перевозки единицы груза на каждом участке (равная Сs) задана. Предполагается, что на каждом участке перевозка грузов осуществляется в одном направлении. Требуется составить такой план перевозки, при котором транспортные расходы будут минимальными.

Источник