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

Вариант 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,..., п), где

Если  - стоимость транспортировки одного изделия из пункта производства 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) можно переписать так:

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

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

Поскольку согласно уравнению (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, то план является невырожденным, а если меньше- то вырожденным.

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

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

  Для определения опорного плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и  специфики ее ограничений (каждое неизвестное  уходит лишь в два уравнения систем (3) и (4) и коэффициенты при неизвестных  равны единице) для определения  оптимального плана транспортной задачи разработаны специальные методы: метод потенциалов и метод  дифференциальных рент.

Определение оптимального плана  транспортной задачи.

  Для определения оптимального плана  транспортной задачи разработано несколько  методов. Однако наиболее часто используются метод дифференциальных рент и метод потенциалов.

Метод дифференциальных рент.

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

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

  После того как определены избыточные и  недостаточные строки, для каждого  из столбцов находят разности между  числом в кружке и ближайшим к  нему тарифом, записанным в избыточной строке. Если число в кружке находится  в положительной строке, то разность не определяют. Среди полученных чисел  находят наименьшее. Это число  называется промежуточной рентой. После определения промежуточной ренты переходят к новой таблице. Эта таблица получается из предыдущей таблицы прибавлением к соответствующим тарифам, стоящим в отрицательных строках, промежуточной ренты. Остальные элементы остаются прежними. При этом все клетки новой таблицы считают свободными. После построения новой таблицы начинают заполнение ее клеток. Теперь уже число заполняемых клеток на одну больше, чем на предыдущем этапе. Эта дополнительная клетка находится в столбце, в котором была записана промежуточная рента. Все остальные клетки находятся по одной в каждом из столбцов и в них записаны наименьшие для данного столбца числа, заключенные в кружки. Заключены в кружки и два одинаковых числа, стоящих в столбце, в котором в предыдущей таблице была записана промежуточная рента.

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

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

  В большинстве случаев для нахождения решения конкретных транспортных задач с использованием ЭВМ применяется метод дифференциальных рент.

  Пример 5. Для транспортной задачи, исходные данные которой приведены в табл. 3, найти оптимальный план методом дифференциальных рент.

таблица 3

  Решение. Перейдем от табл. 3 к табл. 4, добавив один дополнительный столбец для указания избытка и недостатка по строкам и одну строку для записи соответствующих разностей.

таблица 4

  В каждом из столбцов табл. 4 находим минимальные тарифы и обводим их кружками. Заполняем клетки, в которых стоят указанные числа. Для этого в каждую из клеток записываем максимально допустимое число. Например, в клетку, находящуюся на пересечении строки А1и столбца В₃, записываем число 120.

  В эту  клетку нельзя поместить большее  число, поскольку в таком случае были бы превышены потребности пункта назначения В₃.

  В результате заполнения отмеченных выше клеток получен так называемый условно  оптимальный план, согласно которому полностью удовлетворяются потребности  пунктов назначения В₁, В₂, В₃ и В₄ и частично — пункта назначения В При этом полностью распределены запасы пункта отправления А₂, частично— пункта отправления А₁ и остались совсем нераспределенными запасы пункта отправления Аз.

  После получения условно оптимального плана определяем избыточные и недостаточные  строки. Здесь недостаточной является строка А₂, так как запасы пункта отправления А₂ полностью использованы, а потребности пункта назначения В₅ удовлетворены частично. Величина недостатка равна 80 ед.

Строки  А₁ и А₃ являются избыточными, поскольку запасы пунктов отправления А₁ и А₃ распределены не полностью. При этом величина избытка строки А₁ равна 60 ед., а строки А₃ - 20 ед. Общая величина избытка 60 + 20 = 80 совпадает с общей величиной недостатка, равной 80.

  После определения избыточных и недостаточных  строк по каждому из столбцов находим  разности между минимальными тарифами, записанными в избыточных строках, и тарифами, стоящими в заполненных  клетках. В данном случае эти разности соответственно равны 5, 4, 2, 1 (табл. 4). Для столбца В₃ разность не определена, так как число, записанное в кружке в данном столбце, находится в положительной строке. В столбце В₁ число, стоящее в кружке, равно 1, а в избыточных строках в клетках данного столбца наименьшим является число 6. Следовательно, разность для данного столбца равна 6 -1= Аналогично находим разности для других столбцов: для В₂ 12 — 8 = 4; для В₄ 7 — 5 = 2; для В₅ 4 — 3=1.

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

таблица 5

  В этой таблице в строках А₁ и А₃ (являющихся избыточными) переписываем соответствующие тарифы из строк А₁ и Аз табл. 4. Элементы строки А₂ (которая была недостаточной) получаются в результате прибавления к соответствующим тарифам, находящимся в строке А₂ табл. 4, промежуточной ренты, т. е. 1.

  В табл. 5 число заполняемых клеток возросло на одну. Это обусловлено тем, что число минимальных тарифов, стоящих в каждом из столбцов данной таблицы, возросло на единицу, а именно в столбце В₅ теперь имеются два минимальных элемента 4. Эти числа заключаем в кружки; клетки, в которых они стоят, следует заполнить. Необходимо заполнить и клетки, в которых стоят наименьшие для других столбцов тарифы. Это клетки табл. 5, в которых соответствующие тарифы заключены в кружки. После того как указанные клетки определены, устанавливаем последовательность их заполнения. Для этого находим столбцы (строки), в которых имеется лишь одна клетка для заполнения. Определив и заполнив некоторую клетку, исключаем из рассмотрения соответствующий столбец (строку) и переходим к заполнению следующей клетки. В данном случае заполнение клеток проводим в такой последовательности. Сначала заполняем клетки A₁B₃, А₂В₁, А₂В₂, А₂В₄, так как они являются единственными клетками для заполнения в столбцах В₁, В₂, В₃ и B₄. После заполнения указанных клеток заполняем клетку А₃В₅, поскольку она является единственной для заполнения в строке А₃. Заполнив эту клетку (табл. 5), исключаем из рассмотрения строку А₃. Тогда в столбце В₅ остается лишь одна клетка для заполнения: Это клетка А₂В₅, которую заполняем. После заполнения клеток устанавливаем избыточные и недостаточные строки (табл. 5). Как видно из табл. 2.16, еще имеется нераспределенный остаток. Следовательно, получен условно оптимальный план задачи и нужно перейти к новой таблице. Для этого по каждому из столбцов находим разности между числом, записанным в кружке данного столбца, и наименьшим по отношению к нему числом, находящимся в избыточных строках (табл. 5). Среди этих разностей наименьшая равна 1. Это и есть промежуточная рента. Переходим к новой таблице (табл. 6).

таблица 6