Работа По теме: «Целочисленное программирование» (стр. 2 из 6)

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

Пример 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.

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

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

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

Вид груза у	mj	V,	Сj
1	3	1	10
2	1	2	12

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

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

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₃) являются линиями разбиения.

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

Рис. 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. Строим в случае необходимости дополнительные ограничения, согласно возможным четырем случаям получаем оптимальный целочисленный план либо устанавливаем неразрешимость задачи.

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

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

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

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 в качестве области допустимых решений. Такая вновь полученная область обладает двумя важными свойствами: во-первых, она содержит все допустимые целочисленные точки исходной задачи линейного программирования (поскольку она является выпуклой оболочкой этих точек), во-вторых, все крайние точки новой области — целочисленны. Поэтому любое базисное оптимальное решение модифицированной задачи линейного программирования имеет своими компонентами целые числа и является оптимальным решением исходной задачи целочисленного программирования.