Классификация задач линейного программирования

     симплексной таблицы, содержащей оптимальное решение,

     (7.5)

     Далее введем понятие целой и дробной  частей чисел а_r0 и а

     _rj, для чего запишем эти числа в виде:

     Здесь [а_r0] и [a_rj] - целые части, a q_t, q_r] - дробные части чисел а_rj и a_rj.

     Например,  ³⁷/₃ =12 +1/3,  так как [³⁷

     /₃] = 12, a   -^s/, = -3 + 1/3„ так как [-8/3] = -3.

     Из  уравнения (7.5) найдем х_r

          x_r=а_r0-  

     Теперь  числа а_ю и а_rj  заменим суммами целых и дробных частей:

     x_r =

     Предположим, что все x_j - целые числа. Тогда разность

     является  целым числом.

     Чтобы оказалось целым числом и х_r, необходима целочисленность разности

     Но  О<q_г<1,     0<g_rj<1,     a

     (7.6)

     Если  допустить, что разность (7.6) больше нуля, то

     Однако  в этом случае разность (7.6) не может  быть целым числом.

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

     неравенством

                                                                                (7.7)

     Условие (7.7) и является добавочным ограничением в задаче линейного

     программирования. Для использования его в симплексном  методе требуется ввести

     дополнительную  переменную х_п+≥0 , после чего неравенство

     превращается  в уравнение

     Обычно  это ограничение записывают в  следующем виде:

     (7.8)

     Последовательно добавляя новые ограничения к  решению очередных задач,

     получаем  целочисленные координаты оптимального плана задачи (7.1)—(7.4), если

     только  не выясняется в какой-либо момент, что текущая задача не имеет

     решения. Это означало бы отсутствие целочисленного решения задачи

     (7.1)—(7.4).

     Пример 1. Найти оптимальный целочисленный  план задачи Z(X) = х₁ - Зх

     ₂ + 5х₃ + 2х₄ -max

     при условия

     x₁+x₂+x₃     =15

     2x₁+   3x₃+x₄=8,

     х_j, > 0,     х_j — целые числа,  j = 1, 2, 3, 4.

     Решение. Пошаговое решение задачи приведено  в табл. 7.1

     Таблица 7.1

         

 

         

 

     Оптимальный    план    задачи    без    условия    целочисленности

     X = (0, 37/3, 8/3, 0)- для дальнейшего решения  задачи к таблице оптимального

     плана добавлено условие

     -2/3x₁-1/3x₄≤-2/3.

     Номер индекса г выбран из условия большей  дробной части компоненты а_i0

     . Имеем г = 2; j = 0: [8/3] = 2,     2 – 8/3 = -²/₃; j=1:

     [²/₃1 = О,     О - ²/₃ ⁼

     -²/₃;     j = 2:    [0] = 0, 0 - 0 = 0; j = 3:    [0]= 0,

     0 - 0 = 0; j ⁼ 4:    [1/₃] = 0, 0 — 1/₃ = -1/

     ₃. Сделав один шаг (в общем случае для получения целочисленного решения

     одной итерации, конечно, недостаточно) метода последовательного уточнения

     оценок,  получили оптимальный план целочисленной  задачи Х*= (О, 13, 2, 2)

     Трудоемкость  решения целочисленной задачи обусловлена  вводом новых добавочных

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

     следующего  правила, позволяющего при определенных условиях сокращать текущие

     таблицы. Дополнительная переменная х_п+1 вводится в процессе решения

     с добавочным ограничением как базисная переменная очередного псевдоплана  и

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

     дальнейших итерациях, согласно правилу преобразования таблицы, переменная х

     _п+1 снова окажется базисной, ее значение станет несущественным для

     основных  переменных задачи, так что строка и столбец текущей таблицы,

     отвечающие  х_п+_] вычеркиваются. Правило сокращения таблиц

     ограничивает их размеры: не более n строк и не более (2n -m) столбцов.

     Рассматриваемый алгоритм целочисленного программирования сводится к методу

     последовательного уточнения оценок с дополнительными  правилами расширения и

     сокращения  текущей таблицы решения задачи.

     Пример 2. Получить целочисленный оптимальный  план задачи

     Z(X) = x₁— 4х₂ — 2х₃ + Зх₄ —> max при условиях

     3x₁+x₂+8x₃+x₄=35

     x₁        +x₃+x₄≤6

     x_j≥ 0,     х_j — целые числа,    j = 1, 2, 3, 4.

     Решение. Пошаговое решение задачи приведено  в табл. 7.2.

     Таблица 7.2

         

 

     На  шаге 2 решения задачи без ограничения  целочисленности получаем

     оптимальный нецелочисленный план

     X = (0, 0, 29/7, 13/7).

     Поскольку обе базисные координаты X нецелочисленны, выбираем любую — первую

     или вторую — строку таблицы на шаге 2, а именно вторую, и строим добавочное

     ограничение

     -5/7x₁-6/7x₂-1/7x₅+x₆=-6/7.

     Вводя ограничение добавочной строкой  на шаге 2, находим направляющий элемент

     в этой строке:

     Осуществляя преобразование табл. 7.2 с направляющим элементом (-5/7),

     получаем  на шаге 3 оптимальный план новой  задачи, снова нецелочисленный. На

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

     Поскольку на шаге 3                         достигается

     в столбце А₆, то х₆ становится базисной переменной на шаге

     4. В соответствии с правилом сокращения таблицы на шаге 4 вычеркиваем строку

     и столбец, соответствующие х₆, добавляем новую строку, а на шаге 5

     получаем  псевдоплан X = (4, 0, 3, -1). Методом последовательного уточнения

     оценок  на шаге 6 получаем план, но нецелочисленный. Оптимальный целочисленный

     план  получаем лишь на шаге 7:               X* = (О, 1, 4, 2), max Z(X) = -6.

                           

     1.3. Метод ветвей и границ                         

     Одним из широко распространенных методов  решения целочисленных задач

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

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

     программирования. Рассмотрим идею метода ветвей и границ на примере общей

     задачи  дискретного программирования

     f(X) -> max,

     (7.9)

     Х€D

     (7.10)

     где D — конечное множество.

     Сначала найдем оценку £(D) (границу) функции f(X), X е D:    f(X) ≤

     £(D) для V X е D. Если для некоторого плана  Х° задачи (7.9)-(7.10)

     справедливо равенствоf(X⁰) = £(D), то Х° = X^*

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

     разбиение (ветвление) множества D на конечное число  непересекающихся

     подмножеств D¹_i:  ỤD¹_i. = D,

     ∩D¹_i = Ө, и вычисление оценки £(D¹

     _i) (границ), 1≤i≤m (рис 7.1)

         

     Рис. 7.1

         

 

     Если  для некоторого плана X¹_i е Di¹,   1

     ≤ / ≤ m выполняется условие f(X_k^l)= £(D

     ¹_k)≥ £(D¹_i),

     1≤i≤m  то X_k¹=X^* является

     оптимальным планом (решением) задачи (7.9)-(7.10).

     Если  такого плана нет, то выбирается подмножество D_k^l с

     наибольшей оценкой £(D¹_i):

     и разбивается на конечное число непересекающихся подмножеств

     D²_kj: UD²_kj=D¹_k, 

     ∩D²_kj=Ө. Для каждого подмножества находится

     оценка  £(D²_kj), 1≤j≤n  (рис 7.2)

     (рис. 7.2).

         

     Если  при этом найдется план X²_j е D²_kJ

     , 1 ≤j ≤n, такой, что f(X²_r)= £(D²

     _kr)≥ £(D²_kj), 1≤j≤n, то X

     ²_r= X* является решением задачи (7.9)-(7.10). Если такого плана

     нет, то процедуру ветвления осуществляют для множества D²_kj

     с наибольшей оценкой £(D²_kj) , 1≤j≤n .

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

     Рассмотрим  задачу, которую можно свести к  задаче целочисленного линейного

     программирования.

     Пример.

     Контейнер объемом 5 м³ помещен на контейнеровоз грузоподъемностью 12

     т. Контейнер требуется заполнить  грузом двух наименований. Масса единицы груза

     m_j (в тоннах), объем единицы груза V_j (в м³),

     стоимости Cj (в условных денежных единицах) приведены  в табл. 7.3.

     Таблица 7.3

         

 

     Требуется загрузить контейнер таким образом, чтобы стоимость перевозимого

     груза была максимальной.