4.3. Решение задач дискретного линейного программирования

Задача линейного программирования усложняется, если на все или некоторые переменные накладываются дополнительные ограничения вида xi – целая величина или xi – дискретная величина (с заданным множеством возможных значений).

Симплекс-метод в своем исходном рассмотренном выше варианте таких ограничений не учитывает. Развитие симплекс-метода для решения задач целочисленного и дискретного программирования обеспечивается в рамках семейства алгоритмов, или метода Гомори [12].

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

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

1. Задача приводится к форме ОЗЛП и далее к линейному пла-

ну.

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

3.Если получено целочисленное решение, оно окончательное.

4.Если полученное решение не является целочисленным, строится дополнительная граница допустимой области – «правильное отсечение» по одной из переменных, для которой найденное значение нецелое. Это приводит к повышению размерности рассматриваемой ОЗЛП, появлению дополнительной базисной переменной и новой строки линейного плана. Принцип построения правильного отсечения таков, что получаемый новый план оказывается заведомо не допустимым.

5.Пункты 2-4 повторяются до получения допустимого и оптимального целочисленного решения.

Правильное отсечение по некоторой базисной переменной xl′ определяется условием

70

−{αl0}+ n∑−m(−{αlj }{− x′′j})≥ 0 ,	(43)
j=1

где αl0 – свободный член; αlj – коэффициенты при свободных переменных в разложении xl′ по свободным переменным, получен-

ном на шаге 2 алгоритма, т. е. коэффициенты строки полученного линейного плана; {α} – дробная часть числа α (разность данного

числа и его целой части – наибольшего целого, не превосходяще-

го α: {α}= α −[α], {1,25}=1,25 −1 = 0,25 , {−1,25}=–1,25–(–2) =

= 0,75).

Для учета условия (43) вводится новая базисная переменная

xm′ +1 = −{αl0}+ n∑−m(−{αlj }) (− x′′j ), xm′ +1 ≥ 0 . Ее появление вызывает

j=1

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

−{αl0} в первом столбце, чем и определяется дальнейшая проце-

дура преобразования плана.

Если для промежуточного оптимального плана несколько базисных переменных оказались нецелочисленными, наиболее про-

стая рекомендация состоит в выборе в качестве xl′ нецелочислен-

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

Пример 28. Определить значения переменных состояния системы x1 ,x2 , доставляющие максимум целевой функции q=–x1 –x2 с учетом ограничений:

5x1 + x2 ≥12 , x1 +3x2 ≥15 , xi ≥ 0 ; i=1,2; x1 ,x2 – целые.

Преобразуем задачу в форму ОЗЛП с двумя базисными и двумя свободными переменными, вводя две новые переменные:

x3 = −12 +5x1 + x2 ≥ 0 , x4 = −15 + x1 +3x2 ≥ 0 ,

и составим линейный план (табл. 5).

Решение нецелочисленной задачи симплекс-методом требует двух преобразований плана (табл. 6, 7). Оптимальное базисное решение представлено в табл. 7. Оно оказалось нецелочисленным. Правильное отсечение по переменной x1 приводит к дополнению задачи базисной переменной x5 и соответствующей строкой таблицы. Значение x5= –1/2 отрицательно, что требует повторного решения нецелочисленной задачи (табл. 8).

71

Таблица 5

Базис

1

-x1

-x2

q

0

−12/ 5

1

1

−1/ 5

1/ 5

x3

–12

–5

–1

12/ 5

−1/ 5

1/ 5

x4

–15

–1

–3

12/ 5

−1/ 5

1/ 5

Таблица 6

Базис

1

-x3

-x2

Q

–12/5

1/5

4/5

–18/5

–2/35

2/7

X1

12/5

–1/5

1/5

–9/10

–1/70

1/14

X4

–63/5

–1/5

–14/5

9/2

1/14

–5/14

Таблица 7

Базис

1

-x3

-x4

q

-6

1/7

2/7

x1

3/2

–3/14

1/14

x2

9/2

1/14

–5/14

x5

–1/2

–11/14

–1/14

Таблица 8

Базис

1

-x3

-x4

q

–6

1/7

2/7

–1/11

2/11

–1/77

x1

3/2

–3/14

1/14

3/22

–3/11

3/154

x2

9/2

1/14

–5/14

–1/22

1/11

–1/154

x5

–1/2

–11/14

–1/14

7/11

–14/11

1/11

72

В табл. 9...12 представлены последующие преобразования задачи, связанные с введением дополнительных отсечений (попеременно по x2 и по x1). Окончательное решение приведено в табл. 13.

Полученное базисное решение допустимо, оптимально и целочисленно, следовательно, решение задачи достигнуто: x1 =2, x2 =5, q=–7.

Таблица 9

Базис

1

–x5

–x4

q

–67/11

–15/77

2/11

–3/77

3/11

3/7

x1

18/11

–5/77

–3/11

–1/77

1/11

1/7

x2

49/11

20/77

1/11

4/77

–4/11

–4/7

x3

7/11

–5/77

–14/11

–1/77

1/11

1/7

x6

–5/11

5/7

–1/11

1/7

–7/11

–11/7

Таблица 10

Базис

1

-x5

-x6

q

–44/7

–4/35

1/7

1/5

3/7

–1/35

x1

11/7

8/35

–2/7

–2/5

1/7

2/35

x2

33/7

–4/35

1/7

1/5

–4/7

–1/35

x3

4/7

36/35

–9/7

–9/5

1/7

9/35

x4

5/7

–4/35

1/7

1/5

–11/7

–1/35

x7

–4/7

4/5

–5/7

–7/5

–1/7

1/5

73

Таблица 11

Базис

1

-x7

-x6

q

–32/5

1/5

2/5

–3/5

–1/5

1

x1

9/5

–2/5

1/5

–3/10

–1/10

1/2

x2

23/5

1/5

–3/5

9/10

3/10

–3/2

x3

8/5

–9/5

2/5

–3/5

–1/5

1

x4

3/5

1/5

–8/5

12/5

4/5

–4

x5

4/5

–7/5

1/5

–3/10

–1/10

1/2

x8

–3/5

–1/5

–2/5

3/2

1/2

–5/2

Таблица 12

Базис

1

-x7

-x8

q

–7

0

1

0

0

0

x1

3/2

–1/2

1/2

1/2

–1

1/2

x2

11/2

1/2

–3/2

–1/2

1

–1/2

x3

1

-2

1

2

–4

2

x4

3

1

–4

–1

2

–1

x5

1/2

–3/2

1/2

3/2

-3

3/2

x6

3/2

1/2

–5/2

–1/2

1

–1/2

x9

–1/2

–1/2

–1/2

1

-2

1

74