ПРИКЛАДНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ

I. Для любого номера k = 1,n выполняется ∆k ≥ 0.

II.                                                                                                                                                                                                                                          Существует номер s = 1,n такой, что ∆s < 0 и λjs ≤ 0 для всех i = 1, m.

III.                                                                                                                                                                                                                                       Существует номер s = 1,n такой, что ∆s < 0 и λjs > 0 при некотором       j = 1,m.

Организация вычислений по симплекс–методу осуществляется с помощью симплекс–таблицы Т, которая представляет собой матрицу размера (m+1)*(n+1):

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

После заполнения таблицы Т проводится её анализ на основе правил симплекс–метода. Если выполняется условие I или II, то расчеты заканчиваются, если выполняется условие III, то осуществляется переход к следующей симплекс–таблице соответствующей новому базисному плану.

1.3 Теория двойственности в линейном программировании

Рассмотрим задачу линейного программирования в произвольной форме:

(1.3.1)

где k ≤ m, l ≤ n.

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

(1.3.2)

Таким образом, двойственная задача строится по следующим правилам:

1.      если прямая задача – задача на максимум, то двойственная задача суть задача на минимум;

2.      коэффициентами целевой функции w(u) двойственной задачи служат свободные члены bi ограничений прямой задачи (поэтому число переменных m в двойственной задаче равно числу ограничений прямой задачи);

3.      свободными членами cj ограничений двойственной задачи служат коэффициенты целевой функции прямой задачи (поэтому число ограничений n в двойственной задаче равно числу переменных в прямой задаче);

4.      матрицей условий двойственной задачи служит транспонированная матрица условий прямой задачи;

5.      каждому ограничению-неравенству двойственной задачи соответствует неотрицательная переменная в прямой задаче, и каждому ограничению типа равенства двойственной задачи соответствует свободная переменная (переменная, на знак которой не наложено ограничение) прямой задачи;

6.      каждой неотрицательной переменной двойственной задачи соответствует ограничение-неравенство прямой задачи, а каждой свободной переменной двойственной задачи соответствует ограничение-равенство прямой задачи.

Эти правила для каждой задачи (1.3.1) однозначно определяют двойственную задачу (1.3.2). Легко показать, что, если задачу (1.3.2) привести к виду (1.3.1), а затем найти двойственную, то получится задача (1.3.1). Это означает, что двойственная задача к двойственной есть исходная задача.
Соотношения двойственности.

Справедливы следующие утверждения:

1.      Пусть x – произвольный план задачи (1.3.1), u* – произвольный план задачи (1.3.2). Тогда z(x) ≤ w(u).

2.      Пусть план задачи (1.3.1), u* - план задачи (1.3.2) и z(x*) = w(u*). Тогда x* - оптимальный план задачи (1.3.1), u* - оптимальный план задачи (1.3.2).

3.      Если задача (1.3.1) неограничена, т.е. max z(x) = +∞, то множество планов задачи (1.3.2) пусто. И наоборот, если задача (1.3.2) неограничена, т.е. min w(u) = −∞, то множество планов задачи (1.3.1) пусто.

4.      Если множества планов обеих задач (1.3.1) и (1.3.2) не пусты, то эти задачи имеют решение.
Решение задачи (1.3.1) существует тогда и только тогда, когда существует решение задачи (1.3.2), причем, если x∗ – оптимальный план задачи (3.1), а u∗ – оптимальный план задачи (3.2), то z(x∗) = w(u∗).

Задача оптимального планирования производства.

Предположим, что предприятие выпускает n видов продукции, используя m видов сырьевых ресурсов. Пусть на изготовление единицы продукции i-го вида требуется aji единиц j-го ресурса и от ее реализации предприятие получает прибыль в размере ci рублей (i = 1, 2,...,n). На складе предприятия имеется bj единиц j-го ресурса (j = 1, 2,..., m). Задача оптимального планирования заключается в следующем: сколько надо изготовить продукции каждого вида из имеющихся запасов сырья, чтобы общая прибыль предприятия была максимально возможной? Переведем эту задачу на язык математики. Обозначим через xi количество изготовленной продукции i-го вида, а через z - прибыль предприятия от реализации всей продукции. В результате мы приходим к следующей задаче линейного программирования:

Мы получили не что иное, как задачу оптимального планирования производства. Это есть классическая интерпретация стандартной задачи линейного программирования в случае, когда ci > 0, aji > 0, bj > 0.

1.4 Транспортная задача

Предположим, что имеются m пунктов отправления Ai, A2,.., Am и в них хранится однородный груз в количестве ai ,a2,.. ,am единиц соответственно. Этот груз следует доставить в n пунктов назначения Bi,B2,..,Bn, причем в каждый из них требуется доставить соответственно bi,b2,..,bn единиц этого груза. Через cij обозначим стоимость перевозок единицы груза из пункта Ai в пункт Bj.

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

Обозначим через xij ,i = 1,m,j = 1,n, количество груза, перевозимого из i-го пункта отправления Ai в j-й пункт назначения Bj. Величины xij называются перевозками, а совокупность перевозок {xij} называется планом перевозок, или просто планом. Будем обозначать, для краткости }.

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

так как количество перевозимого груза не может быть отрицательным.

Кроме того, на перевозки xij накладываются ограничения, обусловленные количеством перевозимого груза.

Количество груза, вывозимого из i-го пункта отправления Ai во все пункты назначения, должно быть не больше запаса груза в ai единиц в этом пункте:

Количество груза, ввозимого в j-й пункт назначения Bj из всех пунктов отправления, должно быть не больше заявки на груз в bj единиц в этом пункте:

Суммарная стоимость всех перевозок определяется формулой

и должна быть минимальной, то есть f (x)→min.

Очевидно, что транспортная задача является задачей ЛП. Поэтому вся теория таких задач применима и к рассматриваемой задаче. В частности, как и в задаче ЛП, план перевозок будем называть допустимым, если он удовлетворяет ограничениям. Допустимый план перевозок называется базисным планом, если в нем отличны от нуля только базисные перевозки. План перевозок называется оптимальным, если соответствующая ему стоимость перевозок минимальна среди всех допустимых планов, то есть оптимальный план - решение задачи (4.1)-(4.5). Как и в любой ЗЛП, оптимальный план является базисным.

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

Для решения транспортной задачи составляется транспортная таблица (таблица 1.4) первая строка и столбец таблицы соответствуют пунктам назначения Bj и пунктам отправления Ai. Последняя строка и столбец -заявкам bj и запасам ai в пунктах отправления. Нижняя правая клетка таблицы содержит суммарную заявку ∑j bj и суммарный запас ∑i ai.

Таблица 1.4

В левые верхние углы внутренних клеток записываются стоимости соответствующих перевозок cij, а в их правые нижние углы заносятся значения конкретных перевозок xij, удовлетворяющие поставленным ограничениям.

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

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

Если сумма всех заявок равна сумме всех запасов, то есть
,

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

Если сумма всех заявок не равна сумме всех запасов, то есть

,

то транспортная задача называется несбалансированной или открытой.

Допустимый план сбалансированной транспортной задачи, то есть решение, удовлетворяющее ограничениям, может быть получен, если заполнить клетки транспортной таблицы перевозками xij следующим образом:

      сумма перевозок в каждой строке ∑nxij равняется запасам в ai единиц соответствующего пункта отправления;

      сумма перевозок в каждом столбце ∑mxij равняется заявке в bj единиц соответствующего пункта назначения.

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

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

Далее рассматриваем сбалансированную транспортную задачу:
, где  

Для определения начального допустимого плана сбалансированной транспортной задачи наиболее часто применяют метод северо-западного угла и метод минимального элемента.

Метод северо–западного угла подразумевает начало вычислений с элемента x11 ,стоящего в северо-западном углу транспортной таблицы.

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

В этом методе последовательно заполняются клетки с наименьшей стоимостью перевозок. Если имеется несколько клеток с наименьшей стоимостью, то из них выбирается любая.

1.5 Целочисленное линейное программирование

Во многих задачах линейного программирования, возникающих на практике, переменные могут принимать только целые значения 0,1, 2,..., так как по своей природе выражают количество физически неделимых объектов, например, количество автомобилей, станков, единиц штучной продукции и т.п. Такие задачи называются задачами целочисленного линейного программирования (ЦЛП).

Важным классом задач ЦЛП являются экстремальные комбинаторные задачи, переменные которых носят логический характер и принимают только два значения 0 и 1. Такие переменные называются булевыми.

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

Классической задачей ЦЛП является следующая «задача о рюкзаке».

Турист, собираясь в поход, должен решить, какие предметы ему взять из имеющихся n типов предметов. Введем обозначения: aj - вес одного предмета j-го типа; Cj - ценность одного предмета j-го типа; xj - число предметов j-го типа, которые турист берет с собой; b - величина, ограничивающая вес рюкзака. Туристу надо решать следующую задачу:

Как же решать задачи ЦЛП? Кажется вполне естественным решить вначале задачу, отбросив требование целочисленности, и полученное ре­шение округлить до целых значений переменных. Однако данный способ далеко не всегда приводит к цели. Во-первых, округленный вектор может оказаться недопустимым в смысле ограничений, а, во-вторых, он может сильно отличаться от точного целочисленного решения.

Таким образом, для задач ЦЛП требуются специальные методы. В настоящее время разработано много таких методов, основными среди которых являются метод Гомори и метод ветвей и границ.

Метод Гомори.

Рассмотрим следующую задачу ЦЛП

    (1.5.1)

                          (1.5.2)

                              (1.5.3)

                               (1.5.4)

Изложим сначала алгоритм метода Гомори в целом.

1.      Решаем исходную задачу (1.5.1)–(1.5.3) без условия (1.5.4) симплекс-методом. Если эта задача имеет целочисленное решение, то оно будет и решением задачи (1.5.1)– (1.5.4). В противном случае переходим к следующему пункту.

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