Контрольные вопросы и упражнения

1. В какой из точек построенной области допустимых решений на рисунке 5 функция достигает максимального и минимального значения?

Рисунок 5

2. В какой из точек области допустимых решений на рисунке 6 функциядостигает максимального и минимального значения?

Рисунок 6

3. Построить область допустимых решений неравенства .

4. Каковы координаты градиента функции (вектора ) в следующей задаче линейного программирования:

5. При решении задачи линейного программирования получили область допустимых решений (рис.7). Найти максимальное значение функции .

Рисунок 7

6. Построить линию нулевого уровня , соответствующую целевой функции.

7. Построить область допустимых решений задачи линейного программирования:

8.Решить графическим методом задачи N№ 2, 3 из пункта 1.

9. Решить графическим методом задачи ЛП:

4 Симплекс-метод решения задач линейного программирования с естественным базисом

Для решения задач ЛП существует универсальный метод – метод последовательного улучшения плана или симплекс-метод, который состоит из двух вычислительных процедур: симплекс-метода с естественным базисом и симплекс-метода с искусственным базисом. Выбор конкретной процедуры осуществляется после приведения исходной задачи линейного программирования к каноническому виду. В теории линейного программирования показано, что оптимальное решение связано с угловыми точками многогранника решений, которым отвечают опорные планы (неотрицательные базисные решения системы уравнений канонической задачи ЛП). Каждый из опорных планов определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов. Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний .

Пример. Решить задачу линейного программирования.

Решение: Приведем задачу к каноническому виду путем введения дополнительных переменных

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

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

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

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

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

Алгоритм симплекс-метода с естественным базисом:

ШАГ 1. Приведение задачи к каноническому виду, притом все элементы столбца свободных членов должны быть не отрицательны.

ШАГ 2. Нахождение начального опорного решения. Путем элементарных алгебраических преобразований, включающих умножение правой и левой частей уравнений на одно и то же число и их сложение задача (1) приобретает предпочтительный вид

(3)

Выбираем m переменных, называемых базисными (БП) и обладающих свойством: они входят с коэффициентом 1 только в одно уравнение и с коэффициентом 0 в остальные уравнения системы (3). Остальные n-m переменных называются свободными. Все свободные переменные полагаются равными 0, а базисные переменные – равным правым частям соответствующих ограничений системы. Пусть m базисных переменных – это переменные . Тогда начальное решениеимеет вид:

ШАГ 3. Целевая функция выражается через свободные переменные и максимизируется. Для этого базисные переменные выразим из системы ограничений через свободные и подставим в выражение функцииZ . Получим приведенные коэффициенты целевой функции .

ШАГ 4. Проверка плана на оптимальность. Составим исходную симплекс-таблицу, записывая приведенные коэффициенты целевой функции в Z-строку с противоположными знаками, а константу со своим знаком.

Таблица 4 – Исходный вид симплекс-таблиц

БП	СП	Коэффициенты при переменных									Q
		x1	x2	…	xm	xm+1	…	xm+k	…	xn
x1	b1	1	0	…	0	a1,m+1	…	a1,m+k	…	a1n
x2	b2	0	1	…	0	a2,m+1	…	a2,m+k	…	a2n
…	…	…	…	…	…	…	…	…	…	…
xq	bq	0	0	…	0	aq,m+1	…	aq,m+k	…	aqn
…	…	…	…	…	…	…	…	…	…	…
xm	bm	0	0	…	1	am,m+1	…	am,m+k	…	amn
Z	Z0	0	0	…	0		…		…

1. Если в Z- строке симплекс-таблицы, содержащей некоторый опорный план, нет отрицательных элементов (не считая ), то данный план оптимален и задача решена. К тому же, если вZ- строке симплексной таблицы, содержащей оптимальный план, нет нулевых элементов (не считая и элементов, соответствующих базису), то оптимальный план единственный. Если же вZ- строке последней симплексной таблицы, содержащей оптимальный план, есть хотя один нулевой элемент, соответствующий свободной переменной, то ЗЛП имеет бесконечное множество решений.

2. Если в Z- строке есть хотя бы один отрицательный элемент (не считая ), а в любом столбце с таким элементом есть хотя бы один положительный, то можно перейти к новому опорному плану, более близкому к оптимальному. Для этого столбец с отрицательным элементомвZ- строке берут за разрешающий (если в Z- строке отрицательных элементов несколько, то за разрешающий выбирают столбец с наименьшим элементом). Следовательно, столбец с номером m+ k станет ведущим или разрешающим и переменная будет включена в базис.

3. Среди элементов ведущего столбца находят положительные. Если таковых нет, то задача не имеет решений в силу неограниченности целевой функции ().

4. Для положительных элементов а_i,m+k подсчитывают симплексные отношения (отношения свободных членов к соответствующим положительным элементам ведущего столбца) , и выбирают среди них наименьшее. Пусть минимальное симплексное отношение будет в строкеq. Строка с номером q станет ведущей (разрешающей), а элемент а_q,m+k – ведущим. Переменная x_q выйдет из базиса.

5. Выполнят одну итерацию по замещению базисной переменной методом Жордана - Гаусса. Строят новую симплексную таблицу и переходят к первому пункту.

Рассмотрим симплекс-метод и метод замещения Жордана – Гаусса на примере.

Пример. Предприятие изготавливает три вида продукции, при этом используется три вида сырья. Нормы расхода каждого сырья на 1 ед. продукции определенного вида приведены в таблице 5. Известны запасы этого сырья, а также прибыль, получаемая при реализации единицы продукции каждого вида.

Таблица 5 – Нормы расходы сырья и получаемая прибыль

	А	В	С	Запасы сырья, ед.
І	-	1	1	12
ІІ	1	3	2	18
ІІІ	-	1	2	16
Прибыль, ден.ед.	2	7	6

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

Решение:

1. Составим математическую модель задачи.

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

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

2. Приведем задачу к каноническому виду

3. Выразим базисные переменныеи целевую функцию через свободные переменные:

4. Найдем начальный опорный план задачи

5. Занесем коэффициенты целевой функции и системы ограничений в симплексную таблицу

Таблица 6 – Исходная симплекс-таблица

БП	СЧ	х1	х2	х3	х4	х5	Q
х4	12	0	1	1	1	0	12
х1	18	1	3	2	0	0	9
х5	16	0	1	2	0	1	8
Z	36	0	-1	-2	0	0

В Z- строке есть отрицательные элементы. Следовательно, начальный опорный план не является оптимальным. Найдем минимальный отрицательный элемент Z- строки: (-2) в столбце «х₃». За ведущий столбец выбираем «х₃», значит, переменная х₃ будет включена в базис.

Так как среди элементов ведущего столбца есть положительные, то существует новый опорный план, более близкий к оптимальному. Подсчитаем симплексные отношения (отношения свободных членов к соответствующим положительным элементам ведущего столбца) и найдем среди них минимальное: . Значит, 3-я строка является ведущей, а элемента₃₃ = 2 – разрешающим. Следовательно, переменная х₅ выйдет из базиса.

6. Методом Жордана – Гаусса проведем одну итерацию замещения.

Таблица 7 – Одно из оптимальных решений

БП	СЧ	х1	х2	х3	х4	х5	Q
х4	4	0	½	0	1	-½	8
х1	2	1	2	0	0	0	1
х3	8	0	½	1	0	½	16
Z	52	0	0	0	0	1

Так как в Z- строке все элементы больше или равны нулю, то найден оптимальный план: .

Он не единственный, так как существует нулевой элемент Z- строки, соответствующий свободной переменной х₂.

7. Найдем второе оптимальное решение. Столбец «х₂» принимаем за ведущий и находим минимальное симплексное отношение: . Тогда вторая строка станет ведущей.

Таблица 8 – Второе оптимальное решение

БП	СЧ	х1	х2	х3	х4	х5	Q
х4	3,5	-½	0	0	1	-½
х2	1	½	1	0	0	0
х3	7,5	-½	0	1	0	½
Z	52	0	0	0	0	1

Из последней таблицы

,

но данное решение не отвечает условию целочисленности.