Глава 3 Специальные разделы математического программирования

Упражнение 1.Найдите решение задачи

методами: а) графическим; б) Гомори, сделав графическую иллюстрацию.

Решение.

x2                       O

A

C

K

B

G G K G K G

E

L G K G K G

F G K G K G

D G K G K G

0 1 2 3 4 5 6 7 8 9 x1

а) Графический метод. Область допустимых значений OABC без учёта целочисленности представлена на рис. 8а.

Рисунок 8а

Перемещаем линию уровня по направлению вектора . Точкой выхода из области допустимых решений является точка B(11/2; 21/4).

Полученное оптимальное решение – нецелочисленное. Для нахождения целочисленного решения отметим в области OABC все точки с целочисленными координатами, заменим многоугольник OABC на многоугольник OADEFGKLC, у которого координаты вершин целочисленные, и найдём оптимальное решение для этой области. В данном случае точкой выхода из области допустимых решений является точка (7; 3).

Таким образом, .

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

Сначала решаем задачу симплекс-методом, без учёта целочисленности. Для этого приведем задачу к каноническому виду:

(1)

Внесём данные задачи в симплекс-таблицу 53.

Таблица 53

План	Базис	Сб	bi					di
x1	x2	x3	x4
I	x3							16
x4
F	=		–4	–3

Базисным решением на первом шаге будет X₁ = (0; 0; 16; 27) (точка O(0; 0) рис. 8б), при котором целевая функция будет F равна 0, то есть F₁= 0.

Для базисного решения X₁ критерий оптимальности не выполнен. Чтобы перейти к построению плана II нужно перевести переменную x₁ в базис, а базисную переменную x₄ – в свободные.

Вычисляем элементы новой симплекс-таблицы54.

Таблица 54

План	Базис	Сб	bi					di
x1	x2	x3	x4
II	x3				4/3		–1/3	21/4
x1				2/3		1/3	27/2
F	=			–1/3		4/3

Базисным решением на втором шаге будет X₂ = (9; 0; 7; 0) (точка C(9; 0) рис. 8б), при котором целевая функция будет F равна 36, то есть F₂= 36.

Для базисного решения X₂ критерий оптимальности не выполнен. Чтобы перейти к построению III плана, нужно перевести переменную x₂ в базис, а базисную переменную x₃ – в свободные.

Вычисляем элементы новой симплекс-таблицы 55.

Таблица 55

План	Базис	Сб	bi					di
x1	x2	x3	x4
III	x2		21/4			3/4	–1/4
x1		11/2			–1/2	1/2
F	=	151/4			1/4	5/4

Базисным решением на третьем шаге будет X₃ = (11/2; 21/4; 0; 0) (точка B(11/2; 21/4) рис. 8б), при котором целевая функция будет F равна 151/4, то есть F₃= 151/4.

Для базисного решения X₃ выполнен критерий оптимальности, так как в целевой функции нет отрицательных элементов. Кроме того, все коэффициенты при свободных переменных (x₃, x₄) отличны от нуля, следовательно, полученное решение X₃ оптимально и единственно.

Таким образом, = (11/2; 21/4; 0; 0), = 151/4.

План III – оптимальный, но компоненты оптимального решения нецелочисленные.

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

, но ,

где – дробная часть числа a.

Из всех нецелочисленных компонент и оптимального решения выбираем компоненту с наибольшей дробной частью (если целые части одинаковые, как в нашем случае, то берём любую из компонент, например, x₁) и выписываем из симплекс-таблицы 55 соответствующее ей уравнение:

.

Правильное отсечение определяется по формуле:

,

то есть:

Û

Û Û

Û . (1-ое отсечение)

Это ограничение добавляется в качестве дополнительного условия

(2)

в оптимальную симплекс-таблицу 55, то есть получаем таблицу 56.

Таблица 56

План	Базис	Сб	bi						–M	di
x1	x2	x3	x4	x5	r1
III¢	x2		21/4			3/4	–1/4
x1		11/2			–1/2	1/2			¥
r1	–M	1/2			1/2	1/2	–1
F	=	151/4			1/4	5/4
M	=	–1/2			–1/2	–1/2

Базисным решением в таком случае будет X₃ = (11/2; 21/4; 0; 0; 0) (точка X₃(11/2; 21/4) рис. 8б), при котором целевая функция будет F равна 151/4, то есть F₃= 151/4.

Таблица 57

План	Базис	Сб	bi						–M	di
x1	x2	x3	x4	x5	r1
IV	x2		9/2				–1	3/2
x1							–1
x3							–2
F	=	75/2					1/2
M	=

Для базисного решения X₃ критерий оптимальности целочисленной задачи не выполнен, так как в столбце, соответствующем свободной переменной x₃, в M-функции есть отрицательный элемент (–1/2). Чтобы перейти к построению плана IV, нужно перевести переменную x₃ в базис, а базисную переменную r₁ – в свободные.

Вычисляем элементы новой симплекс-таблицы 57.

Базисным решением на четвёртом шаге будет X₄ = (6; 9/2; 1; 0; 0) (точка X₄(6; 9/2) рис. 8б), при котором целевая функция будет F равна 75/2, то есть F₄= 75/2.

Для базисного решения X₄ критерий оптимальности целочисленной задачи выполнен, так как из базисного решения выведена единственная искусственная переменная r₁, а в целевой функции нет отрицательных элементов.

Таким образом, = (6; 9/2; 1; 0; 0) и = 75/2.

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

Единственная нецелочисленная компонента – x₂ = 9/2. Выписываем из симплекс-таблицы 57 соответствующее ей уравнение:

.

Правильное отсечение имеет вид:

или

,

или

. (2-ое отсечение)

Это ограничение добавляется в качестве дополнительного условия:

,

в оптимальную нецелочисленную симплекс-таблицу 57, то есть получаем таблицу 58.

Таблица 58

План	Базис	Сб	bi							–M	di
x1	x2	x3	x4	x5	x6	r2
IV¢	x2		9/2				–1	3/2
x1							–1			¥
x3							–2			¥
r2	–M	1/2					1/2	–1
F	=	75/2					1/2
M	=	–1/2					–1/2

Базисным решением в таком случае будет X₄¢ = (6; 9/2; 1; 0; 0; 0) (точка X₄(6; 9/2) рис. 8б), при котором целевая функция будет F равна 75/2, то есть F₄= 75/2.

Для базисного решения X₄¢ критерий оптимальности целочисленной задачи не выполнен, так как в столбце, соответствующем свободной переменной x₅, в M-функции есть отрицательный элемент (–1/2). Чтобы перейти к построению плана V, нужно перевести переменную x₅ в базис, а базисную переменную r₂ – в свободные.

Вычисляем элементы новой симплекс-таблицы 59.

Базисным решением на пятом шаге будет X₅ = (7; 3; 3;0; 1; 0) (точка X₅(7; 3) рисунка 8б), при котором целевая функция будет F равна 37, то есть F₄= 37.

Для решения X₅ критерий оптимальности целочисленной задачи выполнен, так как из базисного решения выведена единственная искусственная переменная r₂, а в целевой функции нет отрицательных элементов.

Все компоненты оптимального решения целочисленные, поэтому .

Таблица 59

План	Базис	Сб	bi							–M	di
x1	x2	x3	x4	x5	x6	r2
V	x2						–1
x1								–2
x3								–4
x5								–2
F	=
M	=

Проиллюстрируем графически метод Гомори (рисунок 8б).

Мы начинаем с оптимального решения непрерывной задачи линейного программирования = (11/2;21/4), = 151/4.

Затем прибавляем 1-ое отсечение:

Û x₃ + x₄ ³ 1.

Выражая переменные x₃ и x₄ из системы ограничений (1)

x₃ = 16 – x₁ – 2x₂ и

x₄ = 27 – 3x₁ – 2x₂ ,

получаем, что

x₃ + x₄ ³ 1 Û (16 – x₁ – 2x₂) + (27 – 3x₁ – 2x₂) ³ 1 Û

Û – 4x₁ – 4x₂ ³ – 42 Û x₁ + x₂ £ 21/2.

Это отсечение вместе с ограничениями исходной задачи линейного программирования приводит к оптимальному решению = (6; 9/2),
= 75/2.

После этого прибавляется 2-ое отсечение:

Û x₅ ³ 1.

Выражая переменную x₅ из системы ограничений (2)

и пользуясь ранее полученными выражениями для переменных x₃ и x₄, получаем, что

Û x₃ + x₄ ³ 3 Û (16 – x₁ – 2x₂) + (27 – 3x₁ – 2x₂) ³ 3 Û

Û – 4x₁ – 4x₂ ³ – 40 Û x₁ + x₂ £ 10.

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

1-ое отсечение

2-ое отсечение

x2                       O

0 1 2 3 4 5 6 7 8 9 x1

Рисунок 8а

Ответ: .

Задача 1. Найдите решение задачи методами:

а) графическим;

б) Гомори, сделайте графическую иллюстрацию.

1.7.

Упражнение 2.Найдите решение задачи

методами: а) графическим; б) ветвей и границ графически.

Решение.

а) Графический метод.

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

x2

B

0 1 2 3 4 5 6 7 8 9 x1

XZ*

Рисунок 9

Перемещаем линию уровня по направлению вектора (подробнее смотри упражнение 1, глава 1). Точкой выхода из области допустимых решений непрерывной задачи является точка B(16/3; 5), а для целочисленной задачи – (5; 5).

Таким образом, .

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

x2

0 1 2 3 4 5 6 7 8 9 x1

X1

Рисунок 10а

Начальная задача линейного программирования (задача 1) получается путём отбрасывания условия целочисленности. Её оптимальным решением будет точка X₁(16/3; 5), в которой F₁ = 109/3 (рис 10а).

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

Для этого сначала выбирается одна из целочисленных переменных, значение которой в оптимальном решении задачи 1 не является целочисленным. Выбирая x₁, замечаем, что область 5 < x₁ < 6 пространства допустимых решений задачи 1 не содержит целочисленных значений переменной x₁, и, следовательно, может быть исключена из рассмотрения как бесперспективная. Это эквивалентно замене исходной задачи 1 двумя новыми задачами линейного программирования (задача 2 и задача 3).

задача 1
задача 2	задача 3
x2 0 1 2 3 4 5 6 7 8 9 x1 X2

Рисунок 10б

x2

0 1 2 3 4 5 6 7 8 9 x1

X3

Рисунок 10в

X₂(5; 21/4) и F₂ = 143/4; X₃(6; 3) и F₃ = 33.

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

На рисунках 10б и 10в изображены пространства допустимых решений задач 2 и 3. Оптимальное решение исходной задачи находится в пространстве допустимых решений либо задачи 2, либо задачи3, следовательно, обе задачи должны быть решены.

Оптимальное решение задачи 2 не является целочисленным, поэтому обращаемся к целочисленной переменной x₂, значение которой в оптимальном решении задачи 2 не является целочисленным. Так как в области 5 < x₁ < 6 пространства допустимых решений задачи 1 не содержит целочисленных значений переменной x₂, заменяем задачу 2 двумя новыми задачами линейного программирования (задача 4 и задача 5), которые обе должны быть решены.

задача 2
задача 4	задача 5
x2 0 1 2 3 4 5 6 7 8 9 x1 X4 Рисунок 10г	x2 0 1 2 3 4 5 6 7 8 9 x1 X5 Рисунок 10д
X4(5; 5) и F4 = 5;	X5(4; 6) и F5 = 34.

На рисунках 10г и 10д изображены пространства допустимых решений задач 4 и 5.

Оптимальные решения задач 4 и 5 целочисленные, поэтому дальнейшего ветвления не требуется.

Таким образом, схематически:

1.
2.	3.
4.	3.

Ответ:

Задача 2. Найдите решение задачи методами:

а) графическим;

б) ветвей и границ графически.

2.7.

Упражнение 3. Параметрическое программирование Найдите решение задачи параметрического программирования графическим методом.

Решение.

Чтобы найти решение задачи, построим многоугольник решений (рис. 11), определяемый системой ограничений:

0 1 2 3 4 5 6

B

A

x1

x2

(1)

(2)

t = 0

t = 10

C

Рисунок 11

Пусть t = 0. Найдём решение задачи F = 3x₁ + 13x₂ ® max. Перемещая прямую 3x₁ + 13x₂ = a в направлении её вектора нормали – градиента , получаем X* = A(0; 5), F_max = 0·3 + 5·13 = 65.

Из рисунка видно, что план X* = A(0; 5), F_max = 65 будет оставаться оптимальным для всякого t, пока вектор не станет перпендикулярен прямой x₁ + 4x₂ = 20 (1), то есть пока не будет выполнено соотношение:

Þ t = 1/5.

Таким образом, для задача имеет оптимальный план X* = A(0; 5), F_max = 65 – 5t.

При t = 1/5 координаты любой точки отрезка AB дают оптимальный план задачи, то есть X* = a×(0; 5) + (1–a)×(4; 4) = (4–4a; 4+a), aÎ[0; 1], и F_max = 64.

Если t > 1/5, то план X* = B(4; 4), F_max = 64 будет оставаться оптимальным до тех пор, пока вектор не станет перпендикулярным прямой 2x₁ + x₂ = 12 (2), то есть пока не будет выполнено соотношение

Þ t = 23/3.

Таким образом, для задача имеет оптимальный план X* = B(4; 4), F_max = 64.

При t = 23/3 координаты любой точки отрезка BC дают оптимальный план задачи, то есть X* = a×(4; 4) + (1–a)×(6; 0) = (6–2a; 4a), aÎ[0; 1], и F_max = 64.

Если же 23/3 < t £ 10, то оптимальным является план X* = C(6; 0), F_max = 18 + 6t.

Ответ:

если , то X* = (0; 5), F_max = 65,

если t = 1/5, то X* = (4–4a; 4+a), aÎ[0; 1], F_max = 64,

если , то X* = (4; 4), F_max = 64,

если t = 23/3, то X* = (6–2a; 4a), aÎ[0; 1], F_max = 64,

если , то X* = (6; 0), F_max = 18 + 6t.

Задача 3. Найдите решение задачи параметрического программирования графическим методом.

3.7.

Упражнение 4. Найдите решение задачи параметрического программирования симплексным методом.

Решение.

Решим задачу симплекс-методом (подробно этот метод был описан в упражнении 2, глава 1). Для этого приведем задачу к каноническому виду:

Внесём данные задачи в симплекс-таблицу 60.

Таблица 60

План	Базис	Сб	bi	1+t				di
x1	x2	x3	x4
I	x3							8
x4
F	=		–1–t	–11

Базисным решением в таком случае будет X₁ = (0; 0; 32; 30), при котором целевая функция будет F равна 0, то есть F₁= 0.

Для базисного решения X₁ критерий оптимальности не выполнен, так как в столбце, соответствующем свободной переменной x₂, в целевой функции есть отрицательный элемент (–11). Чтобы перейти к построению плана II, нужно перевести переменную x₂ в базис, а базисную переменную x₃ – в свободные.

Вычисляем элементы новой симплекс-таблицы 61.

Таблица 61

План	Базис	Сб	bi	1+t				di
x1	x2	x3	x4
II	x2			3/4		1/4		32/3
x4			7/2		–1/2
F	=		29/4–t		11/4

Базисным решением в таком случае будет X₂ = (0; 8; 0; 14), при котором целевая функция будет F равна 88, то есть F₂= 88.

Для базисного решения X₂ при проверке критерия оптимальности возможны три случая:

а) 29/4 – t > 0 Û t < 29/4, тогда решение X₂ является оптимальным и единственным;

б) 29/4 – t = 0 Û t = 29/4, тогда решение X₂ является оптимальным, но не единственным, и следует продолжать поиск;

в) 29/4 – t < 0 Û t > 29/4, тогда решение X₂ не оптимальное, и поиск решения продолжается.

Чтобы в случаях б) и в) перейти к построению плана III, нужно перевести переменную x₁ в базис, а базисную переменную x₄ – в свободные.

Вычисляем элементы новой симплекс-таблицы 62.

Таблица 62

План	Базис	Сб	bi	1+t				di
x1	x2	x3	x4
III¢	x2					5/14	–3/14	14
x1	1+t				–1/7	2/7	¥
F	=	59+4t

Базисным решением в таком случае будет X₃ = (4; 5; 0; 0), при котором целевая функция будет F равна (59+4t), то есть F₃= 59+4t.

Для базисного решения X₃ при проверке критерия оптимальности возможны четыре случая:

а) t = 29/4, тогда решение X₃ является оптимальным, но не единственным. Общий вид оптимального решения можно записать:

X* = a×(0; 8; 0; 14) + (1–a)×(4; 5; 0; 0) = (4–4a; 5+3a; 0; 14a), aÎ[0; 1],

при этом F_max = 88;

б)

,

тогда решение X₃ является оптимальным и единственным;

в) 53/14 – 1/7·t = 0 Û t = 53/2, тогда решение X₃ является оптимальным, но не единственным, и следует продолжать поиск решения;

г) t > 53/2, тогда решение X₃ не оптимальное, и поиск решения продолжается.

Чтобы в случаях в) и г) перейти к построению плана IV, нужно перевести переменную x₃ в базис, а базисную переменную x₂ – в свободные.

Вычисляем элементы новой симплекс-таблицы 63.

Таблица 63

План	Базис	Сб	bi	1+t				di
x1	x2	x3	x4
IV²	x3				14/5		–3/5
x1	1+t			2/5		1/5
F	=	6+6t

Базисным решением в таком случае будет X₄ = (6; 0; 14; 0), при котором целевая функция будет F равна (6+6t), то есть F₄= 6+6t.

Для базисного решения X₄ при проверке критерия оптимальности возникают два случая:

а) t = 53/2, тогда решение X₄ является оптимальным, но не единственным. Общий вид оптимального решения можно записать:

X* = a×(4; 5; 0; 0) + (1–a)×(6; 0; 14; 0) = (6–2a; 5a; 14–14a; 0), aÎ[0; 1],

при этом F_max = 165;

б)

тогда решение X₄ является оптимальным и единственным.

Ответ:

если , то X* = (0; 8; 0; 14), F_max = 88,

если t = 29/4, то X* = (4–4a; 5+3a; 0; 14a), aÎ[0; 1], F_max = 88,

если , то X* = (4; 5; 0; 0), F_max = 59 + 4t,

если t = 53/2, то X* = (6–2a; 5a; 14–14a; 0), aÎ[0; 1], F_max = 165,

если , то X* = (6; 0; 14; 0), F_max = 6 + 6t.

Задача 4. Найдите решение задачи параметрического программирования симплексным методом.

4.7.

Упражнение 5. Найдите решение задачи параметрического программирования симплексным методом.

Решение.

Решим задачу симплекс-методом. Для этого приведем задачу к каноническому виду:

Внесём данные задачи в симплекс-таблицу 64.

Таблица 64

План	Базис	Сб	bi					di
x1	x2	x3	x4
I	x3		35 – t					35/3+1/3t II¢
x4		14 – t		1			7–1/2t II²
F	=		–3	–2

Базисным решением в таком случае будет X₁ = (0; 0; 35–t; 14–t), при котором целевая функция будет F равна 0, то есть F₁= 0.

Для базисного решения X₁ критерий оптимальности не выполнен, так как в целевой функции есть отрицательные элементы. Чтобы перейти к построению плана II нужно перевести переменную x₁ в базис.

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

а) Û –34 £ t £ –28/5, тогда в свободные переводим переменную x₃ (план II¢);

б) Û –28/5 < t £ 13, тогда в свободные переводим переменную x₄ (план II²).

Вычисляем элементы новой симплекс-таблицы 65 в случае а).

Таблица 65

План	Базис	Сб	bi					di
x1	x2	x3	x4
II¢	x1		35/3 + 1/3t		5/3	1/3
x4		–28/3 – 5/3t		–7/3	–2/3
F	=	35 + t

Базисным решением в таком случае будет

X₂¢ = (35/3 + 1/3t; 0; 0; –28/3 – 5/3t),

при котором целевая функция будет F равна 35 + t, то есть F₂¢= 35 + t.

Для решения X₂¢ выполнен критерий оптимальности, так как в целевой функции нет отрицательных элементов. Кроме того, все коэффициенты при свободных переменных (x₂, x₃) отличны от нуля, следовательно, полученное решение X₂¢ оптимально и единственно.

Вычисляем элементы новой симплекс-таблицы 66 в случае б).

Таблица 66

План	Базис	Сб	bi					di
x1	x2	x3	x4
II²	x3		14 + 5/2t		7/2		–3/2	4+5/7t III¢
x1		7 – 1/2t		1/2		1/2	14 – t III²
F	=	21 – 3/2t		–1/2		3/2

Базисным решением в таком случае будет X₂² = (7–1/2t; 0; 14 + 5/2t; 0), при котором целевая функция будет F равна 21 – 3/2t, то есть F₂²= 21 – 3/2t.

Для базисного решения X₂² критерий оптимальности не выполнен, так как в целевой функции есть отрицательные элементы. Чтобы перейти к построению плана III нужно перевести переменную x₂ в базис.

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

а)

тогда в свободные переводим переменную x₃ (план III¢);

б)

тогда в свободные переводим переменную x₁ (план III²).

Вычисляем элементы новой симплекс-таблицы 67 в случае а).

Таблица 67

План	Базис	Сб	bi					di
x1	x2	x3	x4
III¢	x2		4 + 5/7t			2/7	–-3/7
x1		5 – 6/7t			–1/7	5/7
F	=	23 – 8/7t			1/7	9/7

Базисным решением в таком случае будет X₃¢ = (5 – 6/7t; 4 + 5/7t; 0; 0), при котором целевая функция будет F равна 23 – 8/7t, то есть F₃¢= 23 – 8/7t.

Таблица 68

План	Базис	Сб	bi					di
x1	x2	x3	x4
III²	x3		–35 + 6t	–7			–5
x2		14 – t
F	=	28 – 2t

Для решения X₃¢ выполнен критерий оптимальности, так как в целевой функции нет отрицательных элементов. Кроме того, все коэффициенты при свободных переменных (x₃, x₄) отличны от нуля, следовательно, полученное решение X₃¢ оптимально и единственно.

Вычисляем элементы новой симплекс-таблицы 68 в случае б).

Базисным решением в таком случае будет X₃² = (0; 14 – t; –35 + 6t; 0), при котором целевая функция будет F равна 28 – 2t, то есть F₃²= 28 – 2t.

Для решения X₃² выполнен критерий оптимальности, так как в целевой функции нет отрицательных элементов. Кроме того, все коэффициенты при свободных переменных (x₁, x₄) отличны от нуля, следовательно, полученное решение X₃² оптимально и единственно.

Ответ:

если , то X* = (35/3 + 1/3t; 0; 0; –28/3 – 5/3t), F_max = 35 + t,

если , то X* = (5 – 6/7t; 4 + 5/7t; 0; 0), F_max = 23 – 8/7t,

если , то X* = (0; 14 – t; –35 + 6t; 0), F_max = 28 – 2t.

Задача 5. Найдите решение задачи параметрического программирования симплексным методом.

5.7.