70. Каноническая форма задач линейного программирования.

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

Главная особенность ЗЛП – экстремум целевой функции находится на границе области допустимых решений (D).

х ₂

D Z(x)max

х₁

Z(x) Z(x)min

Математическая модель ЗЛП: max(min) Z = z(x); x D.

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

Каноническая форма:

Чтобы перейти к канонической форме необходимо:

- если в ограничении правая часть отрицательная, то ограничение умножают на -1;

- если среди ограничений имеются неравенства, то они преобразуются в равенства путём прибавления (вычитания) к левым частям дополнительных неотрицательных переменных;

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

71. Симплексный метод: построение начального опорного плана, предпочтительный вид.

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

Рассмотрим задачу линейного программирования:

Говорят, что ограничение имеет предпочтительный вид, если при неотрицат.правой части, т.е. , левая содержит переменную, входящую в данное уравнение с коэфф-том 1, а в остальные ограничения с коэфф-том 0. Например:

х ₁+2х₂-4х₄=5; -> предпочтительный вид

2х₂+х₃+2х₄=8; -> предпочтительный вид

х₂-3х₄=3. -> непредпочтительный вид

Е сли каждое ограничение системы имеет предпочтительный вид, то система ограничений представлена в предпочтительном виде. В этом случае легко найти опорное решение системы, т.е. базисность с неотрицат.координатами. Для этого все переменные, кроме тех, кот. находятся в предпочтительном виде, надо приравнять к 0. Тогда последние примут значения, равные правым частям уравнений. Пример: х₁+х₂-х₅=10;

5х₁+х₃+3х₅=80; -> система в предпочтит.виде, =>

-5х₁+х₄+2х₅=32.

х₂=10; Так как полученный план будет иметь не более

=> х₃=80; m компонент, отличных от 0, то он будет

х₄=32. опорным.

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

При приведении с-мы огр-ий к предпочтит.виду возможны 2 случая:

1) Пусть задана система:

Добавим к левым частям неравенств дополнительные переменные .

Получим:

В этой расширенной задаче система ограничений имеет предпочтит.вид, поэтому получим начальный опорный план:

; ;… ).

n m

В ЦФ доп.переменные вводят с коэфф-том 0: с_n+i=0 (i=1,m).

2) Задана система огр-ий:

Вычитаем из левых частей неравенств дополнит. переменные .

Получим:

В этой расширенной задаче с-ма огр-ий не имеет предпочтит.вида, т.к. доп.переменные входят в уравнение с коэфф-том = -1. Начальный опорный план: ; ;… ) недопустим

n m

Тогда вводят искусственный базис. К левым частям системы, неимеющих предпочтит.вида, добавляют искусственные переменные w_i. В ЦФ их вводят с коэфф-том = +М (если решается задача на min) или с коэфф-том = - М (если решается задача на max). М- большое положительное число. Начальный опорный план:

; ;… ).

n m

Если в оптим. плане М-задачи все искусственные переменные = 0, то данный план оптимален и для исходной задачи.