Транспортная задача с ограничениями на пропускную способность

Транспортная задача с ограничениями на пропускную способность

Правила ввода данных

Поиск

Процесс

Сообщение

Пусть требуется при решении транспортной задачи ограничить перевозки от поставщика с номером l к потребителю с номером m.
Возможны ограничения двух типов:

x_lm > а;
x_lm < b,
x_lm = k,

где а и b- постоянные величины.

1. Если x_lm > a, то необходимо прежде, чем решать задачу, сократить (уменьшить) запасы l-го поставщика и запросы m-го потребителя на величину а (зарезервировать перевозку x_lm = а). После решения задачи в оптимальном решении следует увеличить объем перевозки x_lm на величину а.

2. Если x_lm<b, то необходимо вместо m-го потребителя с запросами b_m ввести двух других потребителей. Один из них с номером m должен иметь запросы b '_m=b, а другой с номером п + 1- запросы b_п+1= b_m - b. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости c_l₍_n+1) которая принимается равной сколь угодно большому числу М (М >> 1). После получения оптимального решения величины грузов, перевозимых к (n + 1)-му потребителю, прибавляются к величинам перевозок l-го потребителя. Так как c_l(_n+1)₎ = М - самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l, n+ 1) останется пустой, x_l_{_n+1) = 0 и объем перевозки х_lm не превзойдет b.

3. Если x_lm = k, то необходимо уменьшить запасы и потребности для номеров l и m на величину k. Стоимость перевозки c_lm назначают равной М >> 1.

4. В некоторых задачах требуется запретить перевозки от отдельных поставщиков отдельным потребителям. В таких случаях либо зачеркивают соответствующую клетку таблицы транспортной задачи, либо назначают соответствующую этой клетке стоимость перевозки единицы груза сколь угодно большой, равной М >> 1. В остальном задача решается обычным способом.

Инструкция. Для получения онлайн решения транспортной задачи выберите размерность матрицы тарифов.

Найти решение транспортной задачи, если из А₂ в В₄ перевозки запрещены, из А₁ в В₃ должно быть доставлено не менее n единиц груза, а из А₃ в В₁ не более m единиц груза.

Скачать пример оформления

Пример. В трех хранилищах горючего ежедневно хранится 175, 125 и 140 т бензина. Этот бензин ежедневно получают четыре заправочные станции в количествах, равных соответственно 180, 110, 90 и 40 т. Тарифы перевозок 1 т бензина с хранилищ к заправочным станциям задаются матрицей .
Составит такой план перевозок бензина, при котором общая стоимость перевозок является минимальной.

Рассмотрим первый вариант ограничения. Пусть требуется ограничить перевозки от поставщика с номером 2 к потребителю с номером 3 в размере не менее 40. Сокращаем запасы 2-го поставщика и запросы 3-го потребителя на величину а = 40. Решаем задачу с использованием калькулятора.

	1	2	3	4	Запасы
1	9	7	5	3	175
2	1	2	4	6	85
3	8	10	12	1	40
Потребности	180	110	50	40

В результате получим оптимальный план.

	1	2	3	4	Запасы
1	15	110	50		175
2	85				85
3				40	40
4	80				80
Потребности	180	110	50	40

Далее в оптимальном решении следует увеличить объем перевозки x₂₃ на величину а = 40.

	1	2	3	4	Запасы
1	15	110	50		175
2	85		40		125
3				40	40
4	80				80
Потребности	180	110	90	40

Рассмотрим второй вариант ограничения. Пусть требуется ограничить перевозки от поставщика с номером 2 к потребителю с номером 3 в размере не более 30. Вместо 3-го потребителя с запросами 90 вводим двух других потребителей. Один из них с номером 3 должен иметь запросы b'₃=30, а другой с номером 4 + 1 - запросы b₅ = 90 - 30 = 60. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости c₂₅ которая принимается равной сколь угодно большому числу М (М >> 1).

В результате получим опорный план.

	1	2	3	4	5	Запасы
1	9	7[85]	5[30]	3	5[60]	175
2	1[100]	2[25]	4	6	36	125
3	8[80]	10	12	1[40]	12	140
Потребности	180	110	30	40	60

После получения оптимального решения величины грузов, перевозимых к 5-му потребителю, прибавляются к величинам перевозок 2-го потребителя. Так как c₂₅ = М - самая большая стоимость перевозки, то в оптимальном решении клетка с номером (2, 5) останется пустой, x₂₅ = 0 и объем перевозки х₂₃ не превзойдет b = 30.

	1	2	3	4	Запасы
1		85	30+60		175
2	100	25	0 < 30		125
3	80			40	140
Потребности	180	110	90	40

Рассмотрим третий вариант ограничения. x₂₃ = 20. Модифицируем исходную матрицу:

	1	2	3	4	Запасы
1	9	7	5	3	175
2	1	2	`M`	6	85-20=65
3	8	10	12	1	40
Потребности	180	110	50-20=30	40

Решая методом потенциалов, получаем следующий оптимальный план:

	1	2	3	4	Запасы
1	9[35]	7[110]	5[30]	3	175
2	1[65]	2	36	6	65
3	8[0]	10	12	1[40]	40
4	0[80]	0	0	0	80
Потребности	180	110	30	40

Восстанавливаем исходную матрицу:

	1	2	3	4	Запасы
1	35	110	30		175
2	65		20		85=65+20
3				40	40
4	80	0	0	0	80
Потребности	180	110	50=30+20	40

Пример №1. Транспортная задача с дополнительными ограничениями.
Скачать решение

Пример №2. Найти оптимальный план транспортной задачи, описываемой соответствующей таблицей, удовлетворяющим указанным условиям.

Потребности пунктов B₁ и B₃ удовлетворяются полностью.
Остаток груза в пункте A₁ не менее 10 ед., но не более 13 ед.
Суммарная вывозка из пунrта А₁ не менее 45 ед.
Суммарная поставка в пункт В₁ не более 70
Суммарная поставка в пункт В₂ не менее 100
В пункт В₂ должно быть завезено не менее 25 ед.
От второго поставщика должно быть вывезено не менее 50 ед.
x₁₂ ≤ 15
Суммарная вывозка из всех пунктов равна 75 ед.
Должен быть вывезен весь груз из пунктов А₃ и А₂.
Суммарная поставка в пункт В2 не превосходит 50 ед., груза, но не менее 35 ед.
Из пункта А₁ нужно вывезти не менее 160 ед. груза, а в пункт В₁ завезти не менее 70 ед. груза из пункта А₂.
x₁₁ + x₂₁ ≤ 35

Потребности