10. Каноническая и стандартная формы злп. Приведение злп к стандартному и каноническому виду. Примеры.

Каноническая форма ЗЛП предполагает нетривиальную³ систему ограничений, которые являются уравнениями.

Стандартная форма ЗЛП предполагают эту систему, но уже только с неравенствами.

Любая ЗЛП может быть сведена как к канонической, так и к стандартной форме.

Пример 1

Привести данную ЗЛП к каноническому виду

Где

Пример 2.

Привести данную ЗЛП к стандартному виду

Преобразуем систему уравнений методом Гаусса к виду

с базисными неизвестными , и свободными неизвестными .

Учитывая неотрицательность неизвестных, получаем систему неравенств

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

Теорема 1

Если в ЗЛП допустимое множество непусто и целевая функция ограничена, то существует хотя бы одно оптимальное решение.

Теорема 2

Если в ЗЛП f(x)-> max (min) при условии x принадлежит X допустимое множество X имеет хотя бы одну угловую точку, а целевая функция f(x) ограничена, то угловая точка X, в которой f(x) принимает наибольшее (наименьшее) значение среди всех угловых точек X, является оптимальные решением данной задачи.

Теорема 2'

Если в ЗЛП все переменные имеют условие неотрицательности и целевая функция f(x) ограничена на допустимом множестве X, то угловая точка X, в которой f(x) принимает наибольшее (наименьшее) значение среди всех угловых точек X, является оптимальным решением данной задачи.

12. Теорема о структуре множества оптимальных решений

Если в ЗЛП допустимое множество X непусто и ограничено, то задача разрешима, а множество всех оптимальных решений X* является выпуклой оболочкой оптимальных угловых точек X.

13. Графический метод решения злп.

Примеры ЗЛП с единственным и неединственным (отрезок, луч) оптимальным решением, пустым допустимым множеством и неограниченной целевой функцией

Графический метод состоит в следующем:

1. Строится множество X всех допустимых решений

2. Если X = Ø, то задача неразрешима

3. Если X ≠ Ø, то рассматриваются прямые уровня f=a при монотонном изменении a от -∞ до +∞. При увеличении a прямая f=a смещается параллельно в направлении вектора ē. Если A – первая точка встречи прямой уровня с областью X, f(A) = a₀, то прямая уровня f(x) = a при a < a₀ не имеет общих точек с X. Откуда следует, что a₀ = min f на X. Аналогичны образом, если A – последняя точка пересечения линии уровня с X, то f(A) = max f на X.

Если первой точки пересечения линии уровня с X не существует (т.е. при всех a из некоторого промежутка вида [ -∞;a₀ ] прямая f=a пересекает X), то min f = -∞, и задача на минимум неразрешима. Если не существует последней точки пересечения, то max f = +­­∞, и задача на максимум неразрешима.

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

Допустимый вид системы ограничений:

Какие-то из неизвестных должны быть выражены через остальные неизвестные, причем свободные члены этих выражений неотрицательны.

Пример:

x₁ = -2x₄ + 7x₅ + 5

x₂ = 3x₄ + 6x₅ + 4

x₃ = -x₄ + 2x₅

Допустимый базис:

Все свободные члены в правых частях неотрицательны

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

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

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

x₁ + a_{1 r+1} x_r+1 + … + a_{1 n} x_n = b₁

x₂ + a_{2 r+1} x_r+1 + … + a_{2 n} x_n = b₂ (1)

_{……………………………………………………….}

x_r + a_{r r+1} x_r+1 + … + a_{r n} x_n = b_r

где x₁, x₂, ….., x_r – базисные переменные, x_r+1, x_r+2, ….., x_n – свободные переменные b_i ≥ 0, I = 1, 2, …, r

3. Исключить из целевой функции базисные переменные с помощью (1) и записать ее в виде

f + c_r+1 x_r+1 + … + c_nx_n = c₀ (2)

Коэффициенты , c_i , i = r + 1, …,n называются оценками соответствующих переменных x_r+1 , x_r+2 , … , x_n

Из (1), (2) следует, что на допустимом базисном решении

X_баз = (c₁; c₂; … ; c_r ; 0; 0; … ; 0) *принадлежит* Rⁿ

целевая функция принимает значение f (x_баз) = c₀

После выполнения подготовительного этапа заполняется начальная симплекс-таблица:

Б. н.	С. ч.	X1	…	Xr	Xr+1	…	Xp	…	Xn
X1	b1	1	…	0	a1 r+1	…	a1 p	…	a1 n
…	…	…	…	…	…	…	…	…	…
Xq	bq	0	…	0	aq r+1	…	aq p	…	aq n
…	…	…	…	…	…	…	…	…	…
Xr	br	0	…	1	ar r+1	…	ar p	…	ar n
f	c0	0	…	0	cr+1	…	cp	…	cn

Здесь и ниже используются следующие сокращения:

1. Б.н. – базисные неизвестные.

2. С.ч. – свободные члены.

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

а) Если в строке оценок среди чисел c_k (k ≠ 0) имеется хотя бы одна положительная (например c_p), а в соответствующем столбце (разрешающем столбце) хотя бы один положительный элемент, то решение может быть улучшено. Среди указанных положительных элементов столбца в качестве разрешающего элемента a_ip выбирается тот, которому отвечает минимальное отношение b_i/a_ip. Если имеется несколько элементов с подобным свойством, то в качестве разрешающего выбирается любой из них. В таблице таким элементом является a_qp. Далее над таблицей проводятся элементарные преобразования: переменная x_p становится базисной, а x_q – свободной. На новом базисном решении значение целевой функции не увеличивается, и снова анализируется строка оценок.

б) Если в строке оценок нет положительных чисел, то оптимальное решение найдено.

в) Если в строке оценок есть положительное число, а в соответствующем ей столбце нет положительных элементов, то задача ЛП не имеет решения. В задаче о нахождении минимума функции это обозначается так: min f = −∞.

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

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