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

     Цикл  строится для клетки в которой  наибольшая положительная оценка А_ij max{∆_ij}. В эту клетку ставится знак “+” и она добавляется к заполненным клеткам таблицы.(т.е заполненных клеток становится m+n). Затем методом вычеркивания строится цикл.

Метод вычеркивания:

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

   Оставшиеся клетки таблицы после вычеркивания образуют цикл. В найденном цикле расставляются знаки “+;-“ , в нечетных клетках “+”; в четных “-“; начиная с уже поставленного знака “+”. По циклу перераспределяется груз величиной тетта Ɵ=min”-“ {x_ij}. При построении нового решения все вычеркнутые клетки переписываются без изменения. В клетках со знаком “+” величина перевозки увеличивается на Ɵ. Со знаком “-“ уменьшается на Ɵ, при этом одна из помеченных клеток останется пустой. 

7. Решение транспортной задачи

 

   Фирма «Союз» обеспечивает доставку видео- и аудеокассет с четырех складов, расположенных в разныхточках города в четыре магазина.

   Запас кассет , имеющихся на складах , а  также обьемы заказов магазинов  и тарифы на доставку представлены в транспортной таблице.

  Однако  имеются дополнительные условия : объем  перевозки кассет со склада №2 магазину №3 должен быть не менее 500 тыс.шт (x₂₃≥500), а со склада №4 магазину №4 – не более 500 тыс.шт (x₄₄≤500).

  Определите  оптимальный план поставок кассет в  магазины города, обеспечивающий минимальный  затраты. 
 
 
 

 

Проверяем баланс задачи:

∑_ai=1000+1500+500+1500=4500

∑_bj=500+500+1000+1500=3500

Т.к. ∑_ai>∑_bj, то вводим фиктивного потребителя b₅=4500-3500=1000 

     Требуется при решении транспортной задачи ограничить перевозки от поставщика с номером 2 и потребителю с номером 3.

     Если  x₂₃≥500, то необходимо прежде, чем решать задачу, сократить запасы 2-го поставщика и запросы 3-го потребителя на величину 500 (зарезервировать перевозку x₂₃=500). В полученном оптимальном решении следует увеличить объем перевозки x₂₃ на величину 500.

 

     Если  x₄₄≤500, то необходимо вместо 4-го потребителя с запросами b₄=1500 ввести двух других потребителей. Один из них с номером 4 должен иметь запросы b₄’ = 500, а другой с номером 6 с запросами b₆ = 1500-500=1000. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости c₄₄, которая принимается равной сколь угодно большому числу M (M<< 1). После получения оптимального решения величины грузов, перевозимых к 6-му потребителю, прибавляются к величинам перевозок 4-го потребителя. Так как c₄₄ = M – самая большая стоимость перевозки, то в оптимальном решении клетка с номером (4,4) останется пустой (x₄₄=0) и объем перевозки x₄₄ не превзойдет 500. 

     Строим  начальное решение методом минимальной  стоимости.

      С=

     Находим значение целевой функции:

     Z(x)= 2500+2000+1500+1500+500+500=8500

Для каждого  поставщика и потребителя находим  потенциал. Для этого составлем  систему уравнений U_i+V_i=C_ij для каждой заполненной решением клетки таблицы:

         U_i+V_j=C_ij;U₁=0

      Пусть U₁=0, тогда:

     U₁+V₃=5 => V₃=5

     U₁+V₆=4 => V₆=4

     U₂+V₄=3 => V₄=4

     U₂+V₆=3 => U₂= -1

     U₃+V₁=1 => V₁=3

     U₃+V₂=1 => V₂=3

     U₃+V₃=3 => U₃= -2

     U₄+V₂=1 => U₄=  -2

     U₄+V₅= 0 => V₅=2

     Для всех не заполненных решением клеток таблицы вычисляем оценку ∆_ij=U_i+V_j-C_ij .

     ∆₁₁=U₁+V₁-C₁₁=0+3-3=0 ≤0

     ∆₁₂=U₁+V₂-C₁₂=0+3-2=1 ≥0

     ∆₁₄=U₁+V₄-C₁₄=0+4-4=0 ≤0

     ∆₁₅=U₁+V₅-C₁₅=0+2-0=2 ≥0

     ∆₂₁=U₂+V₁-C₂₁=1+3-4=-2 ≤0

     ∆₂₂=U₂+V₂-C₂₂=-1+3-3=-1 ≤0

     ∆₂₃=U₂+V₃-C₂₃=-1+5-5=-1 ≤0

     ∆₂₅=U₂+V₅-C₂₅=-1+2-0=1 ≥0

     ∆₃₄=U₃+V₄-C₃₄=-2+4-2=0 ≤0

     ∆₃₅=U₃+V₅-C₃₅=-2+2-0=0 ≤0

     ∆₃₆=U₃+V₆-C₃₆=-2+4-2=0 ≤0

     ∆₄₁=U₄+V₁-C₄₁=-2+3-4=-3 ≤0

     ∆₄₃=U₄+V₃-C₄₃=-2+5-6=-3 ≤0

     ∆₄₄=U₄+V₄-C₄₄=-2+4-3=-1 ≤0

     ∆₄₆=U₄+V₆-C₄₆=-2+4-M=2-M ≤0

 Так  как ∆₂₅<0, ∆₁₂<0, ∆₁₅<0, то решение не оптимальное и его можно улучшить

 Ɵ min {500;1000;0}=0