Системное програмирование

таблица 8

 

числу 10, стоящему в плюсовой клетке табл. 8, добавим 10 и вычтем 10 из числа 20, находящегося в минусовой  клетке табл. 8. Клетка на пересечении строки А₂ и столбца В₄ становится свободной.

  После этих преобразований получаем новый опорный план (табл. 9).

таблица 9

  Этот  план проверяем на оптимальность.  Снова находим потенциалы пунктов  отправления и назначения. Для  этого составляем следующую систему  уравнений:

b₁ - a₁ = 1,  b₂ - a₁ = 2,  b₄ - a₁ = 1,

b₂- a₂ = 3,  b₃ - a₂ = 1,  b₄ - a₃ = 4,

Полагаем a₁ =0, получаем b₁ = b₄ = l, b₂ = 2, a₂=-1, b₃= 0, a₃= -3. Для каждой свободной клетки вычисляем число a_ij ; имеем, a₁₃= -2, a₂₁ = 0, a₂₄ = -3, a₃₂= 3, a ₃₁= 1, a₃₃ = -1.

  Таким образом, видим, что данный план перевозок  не является оптимальным. Поэтому переходим  к новому опорному плану (табл. 10). 

  таблица 10

  Сравнивая разности b_j - a_i новых потенциалов, отвечающих свободным клеткам табл. 2.10, с соответствующими числами с_ij, видим, что указанные разности потенциалов для всех свободных клеток не превосходят соответствующих чисел с_ij . Следовательно, полученный план

является  оптимальным. При данном плане стоимость  перевозок S = 1*30 + 2*0+1*20 + 3*20+1*10 + 2*10 = 140.  
 
 

Вариант 2.

Постановка  транспортной задачи. Нахождение опорного плана транспортной задачи.

Постановка  задачи и ее решение

Пример 1

Фирма должна отправить некоторое количество кроватей с трех складов в пять магазинов. На складах имеется соответственно 15, 25, 20 кроватей, а для пяти магазинов  требуется соответственно 20, 12, 5, 8 и 15 кроватей. Стоимость перевозки одной кровати (в долларах) со склада в магазин приведена в таблице. 

Как следует  спланировать перевозку кроватей для  минимизации стоимости? Пусть  — количество кроватей, отправляемых со склада I в магазин j. Ясно, что , и в силу ограничений на возможности поставки со складов (предложение) и спрос в магазинах они удовлетворяют следующим условиям:

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅ = 15,

+ x₂₁ +x₂₂ +x₂₃ +x₂₄ +x₂₅                                     = 25,

    + x₃₁ +x₃₂ +x₃₃ +x₃₄ + x₃₅                                                                        = 20

(для  предложения);

x₁₁ + x₂₁ + x₃₁ = 20,

x₁₂ +x₂₂ + x₃₂ = 12,

x₁₃ + x₂₃ + x₃₃ =  5,

х₁₄ + x₂₄ + x₃₄ = 8,

x₁₅ + x₂₅ + x₃₅ = 15

(для спроса). Стоимость, равная

F = х₁₁ + 0x₁₂ + 3х₁₃ + 4х₁₄ + 2x₁₅ + 5х₂₁ + ... + 4х₃₄+ 3х₃₅,

должна быть минимизирована при этих ограничениях.

  Эта задача является задачей линейного  программирования, но специального вида. В частности, коэффициенты в ограничениях принимают значения 0 или 1, а каждая переменная входит только в два ограничения. На первый взгляд может показаться, что ограничения в виде равенств, определяющих предложение, должны быть заменены на ограничения в виде неравенств со знаком £, а ограничения в виде равенств, определяющих спрос на ограничения в виде неравенств, со знаком ³. Однако, поскольку суммарный спрос равен сумме поставок, во всех случаях должно выполняться равенство. Заметим также, что сумма по первым трем ограничениям дает тот же результат, что и сумма по последним пяти ограничениям. Поскольку независимых ограничений только 7, а не 8, следовательно, базисное допустимое решение и оптимальное решение будет содержать 7 ненулевых значений .

Эти результаты обобщаются на транспортную задачу с  т пунктами производства и объемами производства (i = 1, 2, . . . , т ), и п пунктами потребления и объемами потребления (j =1,..., п), где

(1)

Если  - стоимость транспортировки одного изделия из пункта производства i в пункт потребления j, то задача заключается в нахождении , удовлетворяющих соотношениям  
 

x₁₁+x₁₂+ …+x_1n = a₁,

                          x₂₁ +…+ x_2n                                     = a₂,

…………………………………………………………………………………..

                   x_m1 +…                  + x_mn    = a_m,  (2)

x₁₁ +x₂₁ + x_m1 = b₁,

   x₁₂ + x₂₂ + x_m2 = b₂,

………………………………………………………………………………………………

x_1n + x_2n + x_mn = b_n 

и минимизирующих функцию

F=С₁₁Х₁₁ + С₁₂Х₁₂ +...+С_тnХ_тп.

Короче, соотношения  (2) можно переписать так:

найти такие  , для которых справедливы неравенства

   (i=1,…,m), (3)

(j=1,…,n) (4)

и которые минимизируют функцию

 (5)

Поскольку согласно уравнению (1), имеется всего т + п - 1 независимых ограничений и, следовательно, т + п — 1 базисных переменных в базисном допустимом решении.

 Удобнее не рассматривать ограничения, а  работать с массивом транспортных данных в виде, приведенном ниже. Следует  разместить неотрицательные переменные в клетках таким образом, чтобы  суммы по строкам и столбцам совпадали  с указанными правыми частями  ограничений в виде равенств примера 1 и чтобы сумма произведений этих переменных на стоимости (указанные в правом нижнем углу каждой клетки) была минимальна. Приведенный на рисунке массив соответствует данным примера 1:

Переход к общему случаю очевиден.

  Представляя данные в таком виде, легко построить  первое базисное допустимое решение  задачи. Это можно сделать по правилу "самая дешевая продукция реализуется  первой". Поскольку задача состоит  в минимизации общей стоимости, находим наименьшую стоимость во всех клетках: 0 в строке 1, столбце  2 и присваиваем переменной х₁₂ значение 12 (наименьшая из сумм по строке и по столбцу). Теперь столбец 2 можно удалить, уменьшив сумму по строке на 12, т. е. заменив ее на 3. Потом та же процедура применяется к полученному массиву.

Затем переменной х₁₁ присваивается значение 3 (или переменной х₃₃ — значение 5), удаляется строка 1, сумма по столбцу 1 заменяется на 17 и осуществляется переход к следующему массиву и т. д.