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

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

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

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

Пример. Решить транспортную задачу, исходные данные которой приведены в табл. 5.3.1, при дополнительных условиях: объем перевозки груза от l-го поставщика 2-му потребителю должен быть не менее 100 единиц (x12≥100), а от 3-го 1-му не более 200 единиц (x31≤200).

Таблица 5.3.1

bj ai
   
     
     

Р е ш е н и е. Для того чтобы в оптимальном решении объем перевозки x12 был не менее 100 единиц, при решении задачи будем предполагать, что запасы 1-го поставщика а1 и запросы 2-го потребителя b2 меньше фактических на 100 единиц. После получения оптимального решения объем перевозки x12 увеличим на 100 единиц.

Для того чтобы удовлетворить требованию x31≤200, вместо 1-го потребителя введем двух других. Один из них под прежним первым номером имеет запасы b1=200 единиц и прежние стоимости перевозок единиц груза. Другому присвоим четвертый номер. Его запросы равны b4=500-200=300 единиц и стоимости перевозок единиц груза те же, что и у 1-го потребителя за исключением с34, которую примем равной сколь угодно большому числу М, т.е. с34=М. После нахождения оптимального решения задачи объемы перевозок для 4-го потребителя необходимо прибавить к соответствующим объемам перевозок для 10го потребителя.

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

Таблица 5.3.2

bj ai
M

Далее задачу решаем обычным методом потенциалов. Проверяем выполнение необходимого и достаточного условия существования решения задачи. Находим суммарные запасы поставщиков и запросы потребителей:

а123=100+300+500=900;

b1+b2+b3+b4=200+300+300+300=1100.

Задача с неправильным балансом. Вводим фиктивного поставщика с запасами а4=1100-900=200.

Транспортная задача с ограничениями на пропускную способность - student2.ru Составляем начальное опорное решение X1 методом минимальной стоимости. Записываем матрицу стоимостей С:

Транспортная задача с ограничениями на пропускную способность - student2.ru Транспортная задача с ограничениями на пропускную способность - student2.ru Транспортная задача с ограничениями на пропускную способность - student2.ru Транспортная задача с ограничениями на пропускную способность - student2.ru Транспортная задача с ограничениями на пропускную способность - student2.ru Транспортная задача с ограничениями на пропускную способность - student2.ru Транспортная задача с ограничениями на пропускную способность - student2.ru Транспортная задача с ограничениями на пропускную способность - student2.ru Транспортная задача с ограничениями на пропускную способность - student2.ru Транспортная задача с ограничениями на пропускную способность - student2.ru Транспортная задача с ограничениями на пропускную способность - student2.ru С= Транспортная задача с ограничениями на пропускную способность - student2.ru Транспортная задача с ограничениями на пропускную способность - student2.ru

2 4 6

Кружочками в матрице С отмечены минимальные элементы, а цифрами рядом со строками и столбцами – порядок исключения из рассмотрения поставщиков и потребителей.

Транспортная задача с ограничениями на пропускную способность - student2.ru Таблица 5.3.3

X1 v1=1 v2=0 v3=1 v4=1

bj ai
    -   -  
  -   -   - +
    5 + - M -
      - + -

u1=0

u2=1

u3=7

u4 = -1

Полученное решение X1 имеет m+n-1=4+4-1=7 базисных переменных. Вычисляем значение целевой функции на этом опорном решении:

Z(X1)=100·1+100·2+200·2+300·7+200·8+100·0+100·0=4400.

Для проверки оптимальности опорного решения находим потенциалы. Записываем систему уравнений для нахождения потенциалов и решаем ее:

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

Система состоит из семи уравнений и имеет восемь переменных. Так одно число неизвестных на единицу больше числа уравнений, то одному из потенциалов можно задать значение произвольно: пусть u1=0. Остальные потенциалы однозначно находятся из системы уравнений :

u1=0;

v1=1-u=1-0=1;

u2=2-v1=2-1=1;

v4=2-u2=2-1=1;

u4=0-v4=0-1=-1;

v3=0-u4=0-(-1)=1;

u3=8-v3=8-1=7;

v3=7-u3=7-7=0.

Находим оценки для свободных клеток таблицы:

Δ12=0+0-5= -5 <0; Δ13=0+1-6= -5<0; Δ14=0+1-1=0;

Δ22=1+0-6= -5<0; Δ23=1+1-7= -5<0; Δ31=7+1-3=5>0;

Δ34=7+1-M<0; Δ41=-1+1-0=0; Δ42=-1+0-0= -1<0.

Опорное решение неоптимальное, так как имеется положительная оценка Δ31=5 для клетки (3,1). Отмечаем эту клетку знаком «+». Находим цикл для улучшения опорного решения (см. табл. 5.3.3). Определяем величину груза для перераспределения по циклу 0=min{11, 200, 100}=100. Осуществляем сдвиг по циклу на величину 0=100. Получаем второе опорное решение X2 (табл. 5.3.4)

Транспортная задача с ограничениями на пропускную способность - student2.ru Таблица 5.3.4

X2 v1=1 v2=5 v3=6 v4=1

bj ai
         
     
                   
    M -
    -   -   -

u1=0

u2=1

u3=2

u4= -6

В табл. 5.3.4 также записаны потенциалы и оценки для свободных клеток. Решение X2 оптимальное, так как все оценки неположительные. Запишем оптимальное решение исходной задачи. Для этого увеличим объем перевозки x12 на 100 единиц и объединим объемы перевозок 4-го потребителя с объемами перевозок 1-го потребителя.

Получим

X*= Транспортная задача с ограничениями на пропускную способность - student2.ru

Вычислим значение целевой функции на этом решении:

Z(X*)=100·1+100·5+300·2+100·3+300·7+100·8=4400.

Ответ: min Z(X)=4400 при X*= Транспортная задача с ограничениями на пропускную способность - student2.ru

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

Наши рекомендации