4. Методические рекомендации к выполнению контрольной работы

Приведем решение некоторых задач типового варианта контрольной работы № 3.

3.1.Линейное программирование

Для решения задачи 3.1 необходимо изучить следующую литературу:

[1] Раздел D. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, главы: 1 – 5, стр. 516…596.

[3] Раздел 1. МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ЕГО ПРИЛОЖЕНИЯ, главы: 1 – 6, стр. 16…122.

[4] Глава 2. Задачи линейного программирования и методы их решения, стр. 9…37.

Учебно-методическая литература

[3] Пункты 1 – 6, стр.4…26.

Задача 3.1. Дана стандартная задача линейного программирования с ограничениями - неравенствами:

и целевой функцией:

• Решить симплексным методом.

• Составить двойственную задачу и указать ее решение по второй теореме двойственности.

• Найти область устойчивости двойственных оценок.

• Как изменится решение задачи при изменении правых частей системы ограничений на b₁ = 9; b₂ = 30?

• Решить геометрическим методом.

Симплексный метод.

Приведем задачу к каноническому виду, т.е. неравенства системы преобразуем в уравнения путём введения дополнительных переменных х₃ и х₄.

; где х_j  0; j = 1, , 4.

Переменные x₃ и x₄ в системе линейных уравнений образуют неотрицательный базис, поскольку каждая из них входит только в одно уравнение, причём с коэффициентом единица, и правая часть уравнения неотрицательна.

П редставим целевую функцию в неявном виде, перенеся все члены в левую часть уравнения: f – 2x₁ – x₂ = 0. Это уравнение не содержит базисных переменных x₃ и x₄, зато формально содержит переменную f, которую также можно считать базисной. Составим расширенную систему уравнений:

Запишем расширенную матрицу этой системы в виде симплексной таблицы. В заголовках столбцов указаны обозначения соответствующих этим столбцам переменных и правой части b, а в заголовках строк - обозначения базисных переменных для соответствующих уравнений.

баз. перем.	f	x1	x2	x3	x4	b
x3	0	1	3	1	0	6
x4	0	4	-3	0	1	9
f	1	-2	-1	0	0	0

С толбец f обычно не пишут, поскольку он состоит из нулей и единственной единицы на пересечении со строкой f. По той же причине можно отбросить столбцы базисных переменных x₃ и x₄, - это столбцы единичной матрицы с единицей в строке для той же базисной переменной. При необходимости столбцы базисных переменных легко могут быть восстановлены по обозначениям базисных переменных в заголовках строк. Отбрасывая базисные столбцы, получим компактную симплексную таблицу, столбцы которой соответствуют свободным переменным, а строки - базисным переменным.

своб. п. баз. п.	x1	x2	знач. баз. п.
x3	1	3	6
x4	(4)	-3	9
f	-2	-1	0

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

Значения свободных переменных полагаем равными нулю:

x_{1 =} x_{2 = 0}, а значения базисных переменных и целевой функции находим в последнем столбце: x_{3 = 6;} x_{4 = 9;} f = 0. Первое базисное решение: = (0; 0; 6; 9) и f = 0. Решение не оптимально, так как в нижней (индексной) строке имеются отрицательные числа. Необходимо перейти к другому базисному решению, обменяв базисную переменную на свободную, но так, чтобы новое базисное решение было допустимым, а новое значение целевой функции не хуже старого.

С этой целью сначала выбираем ведущий столбец по отрицательному элементу нижней строки (наибольшему по модулю: -2),  столбец x_1.

Затем выбираем ведущую строку по наименьшему отношению соответствующих элементов последнего и ведущего столбцов, причём рассматриваем только строки с положительными элементами ведущего столбца. В нашем случае в ведущем столбце два элемента положительны (а_{12 = 1;} а_{21 = 4}), и минимум отношения: min{ } = - соответствует строке x_{4. Итак, ведущая} строка: x_{4, а} ведущий элемент: Э = а_{21 =} 4. В таблице ведущие ряды выделены жирным шрифтом, а ведущий элемент Э – помечен скобками: (4).

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

1. Меняем местами переменные x_{1 и} x_4, соответствующие ведущему элементу.

2. На место ведущего элемента (4) записываем обратную ему величину: = 0,25.

3. Остальные элементы ведущей строки делим на ведущий элемент, то есть на 4.

4. Остальные элементы ведущего столбца тоже делим на ведущий элемент Э и меняем знак.

5. Элементы е_{, не принадлежащие ведущим рядам, можно пересчитывать по правилу прямоугольника, вычитая из} е _{произведение соответствующих ему элементов   ведущих рядов, делённое на ведущий элемент} Э_:

или : е заменить на (е  )

Например, на место элемента а₁₂ = 3 запишется:

3 – = 3 + = = 3,75;

на место f = 0 запишется: 0 - = = 4,5; и т.д. Результат - новая симплексная таблица:

своб. п. баз. п.	x4	x2	знач. баз. п.
x3	-0,25	(3,75)	3,75
x1	0,25	-0,75	2,25
f	0,5	-2,5	4,5

Новое базисное решение = (x_1, x_2, x_3, x₄) = (2,25; 0; 3,75; 0) и

f = 4,5 не является оптимальным, т.к. в строке f имеется отрицательный элемент (-2,5). Поэтому новый ведущий столбец: x₂. В ведущем столбце только один положительный элемент: 3,75, который и определяет ведущую строку: x_{3 (первую строку).} Новый ведущий элемент: Э = 3,75.

Вводим в базис x_{2 (вместо} x_{3) и} строим новую симплексную таблицу.

своб. п. баз. п.	x4	x3	знач. баз. п.
x2	-1/15	4/15	1
x1	1/5	1/5	3
f	1/3	2/3	7

Например, на месте ведущего элемента Э = 3,75 = записано ; на месте элемента нижней строки 0,5 записано: 0,5 – = 0,5 - = ; на месте элемента последнего столбца 2,25 записано: 2,25 - = 2,25 + 0,75 = 3; и т.д.

В нижней строке последней симплексной таблицы нет отрицательных элементов, поэтому базисное решение

= (x_1, x_2, x_3, x₄) = (3; 1; 0; 0) и f = 7

- оптимальное!

Проверка №1: ;

f = 2x₁ + x₂ ,

где x₁ = 3, x₂ = 1, f = 7. Подставим:

; истина,

7 = 23 + 1; истина.

Двойственная задача.

Составим таблицу коэффициентов и правых частей ограничений исходной задачи:

	x1	x2	b
y1	1	3	6
y2	4	-3	9
c	2	1	Z=f

В двойственной задаче ограничения-неравенства и целевая функция z относительно неизвестных y_{1 и} y_{2 соответствуют столбцам:}

Неравенства системы ограничений имеют противоположный знак, и у целевой функции z ищут минимум.

Неравенствам системы ограничений соответствуют переменные x₁ и x₂, а также дополнительные переменные y₃ и y₄ – разницы между левой и правой частью каждого неравенства. Аналогично переменным y₁ и y₂ соответствуют переменные x₃ и x₄. По второй теореме двойственности неизвестные y₁, y₂, y₃, y₄ равны модулям коэффициентов при x₃, x₄, x₁, x₂ у целевой функции f , выраженной через свободные переменные. Эти модули коэффициентов находятся в нижней строке оптимальной симплексной таблицы.

Запишем таблицу соответствия:

x1 = 3	x2 = 1	x3 = 0	x4 = 0	f = 7
y3 = 0	y4 = 0	y1 = 2/3	y2 = 1/3	z = 7

Ответ: y₁ = 2/3; y₂ = 1/3; y₃ = 0; y₄ = 0; z_min = 7.

Область устойчивости двойственных оценок

Проверка №2: восстановим систему уравнений по последней (оптимальной!) симплексной таблице:

Э той системе должно удовлетворять любое базисное решение, в том числе, первое: = (x₁, x₂, x₃, x₄) = (0; 0; 6; 9) и f = 0. Подставим:

; истина.

Прибавим к правым частям ограничений-неравенств изменения b₁ , b₂. Изменится и первое базисное решение:

= (x₁, x₂, x₃, x₄) = (0; 0; 6 + b₁; 9 + b₂) и f = 0.

П одставив измененное в систему, найдем изменившееся последнее базисное решение, которое нетрудно записать непосредственно по последней симплексной таблице. Получим:

Е сли это решение допустимо, то есть: x₁  0, x₂  0, - то задачу заново решать не нужно, и двойственные оценки не меняются. Поэтому область устойчивости двойственных оценок задается системой неравенств:

Изменение правых частей системы ограничений на

b₁ = 9; b₂ = 30.

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

9 + 30 ₊ 3 = x_{1  0;}

9 - 30 + 1 = x_{2  0;}

или:

x₁ = 10,8 _{> 0;}

x₂ = 1,4 _{> 0.}

Это – новое решение, так как оно неотрицательно. Новое значение целевой функции:

f = b₁ + b₂ + 7 = 9 + 30 + 7 = 23.

Ответ напишем в виде таблицы соответствия:

x1 = 10,8	x2 = 1,4	x3 = 0	x4 = 0	f = 23
y3 = 0	y4 = 0	y1 = 2/3	y2 = 1/3	z = 23

Геометрический метод

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

,

,

и целевой функцией:

Решение проводится в два этапа: 1) построение области ограничений Ω, называемой также многоугольником решений; 2) отыскание крайней точки области Ω, через которую проходит линия уровня целевой функции с max f (прямая f = Const, наиболее удалённая от начала координат).

Построение области ограничений.

Область Ω строится как пересечение полуплоскостей для ограничений – неравенств. Условия неотрицательности переменных: x₁  0; x₂  0 - выполняются в первой четверти. Для каждого ограничения уравнение границы полуплоскости получается заменой знака неравенства на знак равенства:

₁: x₁ + 3x₂ = 6;

₂: 4x₁ - 3x₂ = 9;

x1	0	6
x2	2	0

x1	0	2,25
x2	-3	0

Строим на плоскости Оx₁x₂ прямую ₁ по точкам пересечения с осями координат A(0; 2), D(6; 0) и прямую ₂ по точкам E(0; -3), C(2,25; 0).

Выделим полуплоскости. С этой целью возьмем пробную точку О(0;0) и подставим в неравенства для определения их истинности.

₁ : x₁ + 3x₂  6; ₂ : 4x₁ - 3x₂  9;

0 + 30  6; истина. 40 - 30  9; истина.

Точка О(0;0) принадлежит обеим полуплоскостям, поэтому заштриховываем вблизи прямых ₁ и ₂ со стороны начала координат. На рисунке многоугольник OABC - область допустимых решений.

Отыскание крайней точки.

_{Строим график линии уровня целевой функции для некоторого значения f , например, для f = 2: 2 = 2x1 + x2.}

x1	0	1
x2	2	0

Прямая f = 2 проходит через точки _{А(0, 2) и P(1, 0).}

Все линии уровня образуют семейство параллельных прямых. В частности, прямая f = 0 проходит через начало координат, а наиболее удалённая от точки О линия уровня f = f _max проходит через крайнюю точку В области Ω. Точка В = ₁  ₂ принадлежит прямым ₁ и ₂. Координаты т. В найдём, решая систему уравнений этих прямых:

;

5x₁ = 15;

x₁ = 3;  x₂ = 1;  т. В(3, 1).

Подставляя координаты т. В в уравнение целевой функции, найдём её оптимальное значение: f _max = 23 + 1 = 7.

Ответ: x₁ = 3; x₂ = 1; f _max = 7.

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