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

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

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

2. если , то необходимо вместо k-го потребителя с запросами ввести двух других потребителей. Один из них с номером k должен иметь запросы = , а другой с номером n+1 – запросы . Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости , которая принимается равной сколь угодно большему числу М(М>>1). После получения оптимального решения величины грузов, перевозимых к (n+1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как =М – самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l, n+1) останется пустой, =0 и объем перевозки не превзойдет .

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