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

Вариант 1.

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

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

Пример 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 и осуществляется переход к следующему массиву и т. д.

После небольшой тренировки для задач  небольшого объема эту процедуру  можно провопить устно. После  того как последней переменной присвоено  значение, суммы по всем строкам  и столбцам будут равны 0. Таким  образом получается решение

(значения переменных  находятся в левых верхних  углах клеток) с семью приводимыми ниже базисными переменными. Остальные переменные равны 0. Для общего массива из т строк и п столбцов получаем т+ п— 1 переменных в силу (1)

Полная  стоимость, соответствующая этому  решению, F = 3*1 + 12*0 + 2*5 + 8*3 +15*З +15*4 + 5*1=147 дол.

Попробуем теперь улучшить это решение, уменьшив стоимость С. Отметим, что полученные результаты для этого частного случая и метод их получения применимы и в случае общей транспортной задачи (см. соотношения (2)).

  Поскольку переменные (i=1,m; j=1,n) удовлетворяют системам линейных уравнений (3) и (4) и условию неотрицательности, обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.

Определение 1. Всякое неотрицательное решение систем линейных уравнений (3) и (4), определяемое матрицей X=( )( i=1,m; j=1,n), называется планом транспортной задачи. 

Определение 2. План , (i= 1,m; j=1,n) при котором функция (5) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывается в виде таблицы 1.

 
 

Очевидно, общее наличие груза у поставщиков  равно  , а общая потребность в грузе в пунктах назначения равно ед. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

=   (6)

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

  Теорема 1. Для разрешимости транспортной задачи необходимо, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т.е. чтобы выполнялось равенство (6).

В случае превышения запаса над потребностью, т.е. > , вводится фиктивный  (n+1)-й пункт назначения с потребностью b_n+1 = - и соответствующие тарифы равными считаются нулю: C_in+1= 0 (i= 1,m) Полученная задачами являются транспортной задачами, для которой выполняется равенство (6).

Аналогично, при < , вводится фиктивный (m+1)-й пункт отправления с запасом груза

a_m+1 = - и тарифы полагаются равными C_m+1j= 0 ( j=1,n).

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

  Число переменных x_ij в транспортной задаче с m пунктами отправления и n пунктами назначения равно m*n, а число уравнений в системах (3) и (4) равно n+m. Так как мы предполагаем, что выполняется условие (6),то число линейно независимых уравнений равно n+m-1. Следовательно, опорный план транспортной задачи может иметь не более n+m-1 отличных от нуля неизвестных.

   Если  в опорном плане число отличных от нуля компонент равно в точности n+m-1, то план является невырожденным, а если меньше- то вырожденным.

   Для определения опорного плана существует несколько методов: метод северо-западного  угла, метод минимального элемента и метод аппроксимации Фогеля.

   Как и для всякой задачи линейного  программирования, оптимальный план транспортной задачи является и опорным  планом.