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

     Решение. Математическая модель задачи имеет  вид

     Z(X) = 10x₁+12x₂→max,

     (7.11)

     3x₁+x₂≤12,

     x₁+2x₂≤5

     x₁≥0

     (7.12)

     x₂≥0

     x₁, x₂- целые числа                                                     (7.13)

     где x₁, x₂  - число единиц  соответственно первого и второго груза.

     Множество планов этой задачи обозначим через D - это множество целых точек

     многогранника ОАВС (рис. 7.3).

         

     Рис. 7.3

     Сначала решаем задачу (7.11)—(7.13) без условия  целочисленности, получим оценку

     множества D - значение функции Z(X) на оптимальном плане Х° = (¹⁹/

     ₅, ³/₅):

     ТочкаXнеявляется оптимальным планом задачи (7.1 1)— (7.13). Поэтому в

     соответствии  с методом ветвей и границ требуется  разбить множество D  на

     непересекающиеся  подмножества. Выберем первую нецелочисленную  переменную x

     ₁=19/5=34/5 и разобьем множество D на два непересекающихся подмножества D

     ¹₁ и D²₂. Линии x₁=3 (L₃

     ) и x₄= (L₃) являются линиями разбиения.

         

 

         

 

          Рис. 7.4

     Найдем  оценки £(D¹₁) и £(D¹₂), для чего решим задачи линейного программирования

     Z(X)=10x₁+12x₂→max,

     3x₁+x₂≤12

     x₁+2x₂≤5

     x₁≤3

     x₁≥0, x₂ – целые числа

     Z(X)=10x₁+12x₂→max,

     3x₁+ x₂≤12

     x₁+2x₂≤5

     x_1≥4

     x₁≥0, x₂ – целые числа

     Например, графическим методом:

     X¹₁eD¹₁→X⁰₁= (3,1); £(D¹₁)=42; X¹₂eD¹₂→X⁰₂= (4,0);  £(D¹₂)=40.

     Результат ветвления приведен на рис. 7.5

         

 

         

 

     План  X⁰₁ удовлетворяет условиям задачи

     (7.11)-(7.13), и для него выполняется условие: Z(X¹₁)=

     £(D¹₁)=42 >

     £(/)/) = 42 >£(D¹₂) = 40. Следовательно,

     план X°₁= (3, 1) является решением задачи (7.11)-(7.13),

     т.е. надо взять три единицы первого  груза и одну единицу второго  груза.

     Алгоритм  метода ветвей и границ

         

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

      

               1.4/ ЦИКЛИЧЕСКИЙ АЛГОРИТМ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ          

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

     Максимизировать

     X₀=a₀₀-a₀₁x₁-a₀₂x₂-....-a_0nx_n,

     при условии

     x_n+1=a_n+1,0-a_n+1,1x₁-a_n+1,2x₂-...-a_n+1,nx_n,

          _.

          _.

     x_n+m=a_n+m,0- a_n+m,1x₁-a_n+m,2x₂-...-a_n+m,nx_n,

     x_j≥0         (j=1,...,n+1,...,n+m).

     Заметим, что x_n+1,  . ., х_n+m  —

     слабые  переменные, a x₁ ... ., х_n  — исходные

     переменные  задачи (1). Если наряду с ограничениями (1) потребовать, чтобы все

     х_j , (j'=1, . . ., т) были целыми, то задача будет

     называться  задачей целочисленного программирования. Существует большое

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

     задачи  целочисленного программирования.

     Ограничения (1) определяют выпуклую область OABCD в n-мерном

     пространстве, как показано на рис. 13.1. Узлы целочисленной  решетки на рис.

     13.1 изображены точками. Такие точки,  расположенные внутри области OABCD,

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

     Оптимальные решения задачи линейного программирования всегда располагаются на

     границе области решений. В данном случае граничные точки не являются даже

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

     Предположим, что область допустимых решений сужена до выпуклой оболочки

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

     оболочка  показана затененной областью OEFGH. Эту затененную область

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

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

     программирования, определяющей допустимую область OABCD, добавить

     ограничение типа RR', как показано на рис. 13.1, то вновь полученная

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

     вновь полученная область обладает двумя  важными свойствами: во-первых, она

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

     программирования (поскольку она является выпуклой оболочкой этих точек),

     во-вторых, все крайние точки новой области  — целочисленны. Поэтому любое

     базисное  оптимальное решение модифицированной задачи линейного

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

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

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

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

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

     допустимых  целочисленных точек.

     Как только это будет сделано, можно решать модифицированную задачу линейного

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

     решение автоматически будет целочисленным. Представленный ниже целочисленный

     алгоритм  обладает следующими свойствами: 1) все  дополнительные ограничения

     сохраняют допустимые точки исходной целочисленной  задачи; 2) за конечное число

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

     чтобы оптимальное решение модифицированной задачи было целочисленным; 3)

     дополнительные  ограничения (гиперплоскости) проходят по крайней мере через одну

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

     оболочки; 4) каждое новое ограничение сокращает область допустимых решений

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

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

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

     оптимальное целочисленное решение определяется пересечением п

     гиперплоскостей, таких гиперплоскостей существует не более, чем это необходимо;

     некоторые из них могут быть ограничениями исходной задачи.

         

     Рис, 13.1.

     Обычно  в ограничения задачи (1) включаются в тривиальные соотношения xj=—(—X

     _j) (j'=1, ...,n), а задача в матричной форме принимает вид

     х = А (-х_n),                       (2)

     где х — вектор-столбец с компонентами Х₀, x₁, . . .,

     x_n, x_n+1, . . .,x_n+

     _m    А — соответствующая матрица размера (п + т +

     1) * (n + 1) и (—х_n) — вектор с компонентами (1, —x₁,—x

     ₂, . . ., —x_n), представляющими собой небазисные переменные

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

     виде  таблицы.

     Причины представления переменных в виде (—x₁), (—x₂, .

     . . . . ., (—x_n)) — чисто исторические, но это стало обычной

     практикой в целочисленном программировании. Будем использовать α_j

     (j ⁼ 0, 1, . . ., п) для обозначения j-го столбца

     текущей таблицы и a_ij (i = 0, 1, . . ., п + т;

     j = 0, 1, . . ., n) для обозначения элемента 1-й строки и 7-го столбца

     таблицы. Предполагается, что все a,ij в исходной таблице целые.

     Следовательно, все слабые переменные x_n+1, . . ., Х

     _n+m должны быть также неотрицательными целыми числами.

     При изложении алгоритма для решения  целочисленных задач будем следовать  работе

     Гомори. Вначале задача целочисленного программирования рассматривается как

     линейная  программа и алгоритм решает ее с  помощью прямого или двойственного

     симплекс-метода. В конце работы алгоритма а_ij≥0   (i

     = 1, ... . . ., п + т) и a_0j≥ 0 (j'

     = 1, . . ., n). (Для получения исходного  двойственного допустимого решения

     введем  дополнительное ограничение x_n+m+1 ==

     М — X₁ —x₂ — . . . — x_n≥ 0, где M —

     достаточно большая константа, и проделаем одну итерацию с этой строкой и

     лексикографически минимальным столбцом в качестве ведущего.) Если а_i0

     ≥ 0 и целые для всех i, то получено оптимальное решение