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

Пусть требуется при решении транспортной задачи ограничить перевозки от поставщика с номером l к потребителю с номером m.
Возможны ограничения двух типов:
  1. xlm > а;
  2. xlm < b,
  3. xlm = k,
где а и b- постоянные величины.

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

2. Если xlm<b, то необходимо вместо m-го потребителя с запросами bm ввести двух других потребителей. Один из них с номером m должен иметь запросы b 'm=b, а другой с номером п + 1- запросы bп+1= bm - b. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости cl(n+1) которая принимается равной сколь угодно большому числу М (М >> 1). После получения оптимального решения величины грузов, перевозимых к (n + 1)-му потребителю, прибавляются к величинам перевозок l-го потребителя. Так как cl(n+1)) = М - самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l, n+ 1) останется пустой, xl{n+1) = 0 и объем перевозки хlm не превзойдет b.

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

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

Инструкция. Для получения онлайн решения транспортной задачи выберите размерность матрицы тарифов.
Количество столбцов (магазины)
Количество строк (поставщики)
Найти решение транспортной задачи, если из А2 в В4 перевозки запрещены, из А1 в В3 должно быть доставлено не менее n единиц груза, а из А3 в В1 не более 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 Запасы
11511050
175
285

85
3


40 40
4 80


80
Потребности 180 110 50 40

Далее в оптимальном решении следует увеличить объем перевозки x23 на величину а = 40.
1 2 3 4 Запасы
11511050
175
285 40

125
3


40 40
4 80


80
Потребности 180 11090 40

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

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

В результате получим опорный план.
  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-го потребителя. Так как c25 = М - самая большая стоимость перевозки, то в оптимальном решении клетка с номером (2, 5) останется пустой, x25 = 0 и объем перевозки х23 не превзойдет 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  

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

1234Запасы
19753175
212M685-20=65
381012140
Потребности18011050-20=3040

Решая методом потенциалов, получаем следующий оптимальный план:
1234Запасы
19[35]7[110]5[30]3175
21[65]236665
38[0]10121[40]40
40[80]00080
Потребности1801103040

Восстанавливаем исходную матрицу:
1234Запасы
13511030 175
265 20 85=65+20
3 4040
48000080
Потребности18011050=30+2040

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

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

  1. Потребности пунктов B1 и B3 удовлетворяются полностью.
  2. Остаток груза в пункте A1 не менее 10 ед., но не более 13 ед.
  3. Суммарная вывозка из пунrта А1 не менее 45 ед.
  4. Суммарная поставка в пункт В1 не более 70
  5. Суммарная поставка в пункт В2 не менее 100
  6. В пункт В2 должно быть завезено не менее 25 ед.
  7. От второго поставщика должно быть вывезено не менее 50 ед.
  8. x12 ≤ 15
  9. Суммарная вывозка из всех пунктов равна 75 ед.
  10. Должен быть вывезен весь груз из пунктов А3 и А2.
  11. Суммарная поставка в пункт В2 не превосходит 50 ед., груза, но не менее 35 ед.
  12. Из пункта А1 нужно вывезти не менее 160 ед. груза, а в пункт В1 завезти  не менее 70 ед. груза из пункта А2.
  13. x11 + x21 ≤ 35
загрузка...