5. Формы записи задач лп.

Общей ЗЛП называют задачу максимизации (минимизации) линейной функции f=Σcj*xj-max(min) (1) при линейных ограничениях ∑aij *xj{=<,=,>=}bi (i=1,n) (2) при условии xj>=0(j=1,n1), xj-произвольное (j=n1+1,n )(3) где cj,aij, bi-постоянные числа.

Симметрической формой записи ЗЛП наз-ся задача максимизации функции (1) при линейных ограничениях в неравенствах со знаком < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > либо = и неотрицательных переменных. Канонической формой записи ЗЛП наз-ся задача максимальной функции (1) при линейных ограничениях равенствах и неотрицательных переменных. Любая другая форма называется смешенной.

min f(x) = -max(-f(x))

Преобразование нерав-ва в уравнение и наоборот осущ-ся на основе Леммы: всякому решению х1…хn нерав-ва a1x1+…+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) и наоборот. Всякому решению x1…xn,xn+1 уравнения 6 и неравенства 7 соответствует решение x1…xn неравенства 5.

6.Алгоритм графического метода решения злп.

1. В системе координат построить прямые по уравнениям, соответствующим каждому неравенству системы ограничений;

2. найти полуплоскости решения каждого неравенства системы (обозначить стрелками);

3. найти многоугольник (многоугольную область) решений системы ограничений как пересечение полуплоскостей;

4. п остроить вектор n (с₁,с₂) по коэффициентам целевой функции f = c₁x₁ + c₂x₂;

5. в семействе параллельных прямых целевой функции выделить одну, например, через начало координат;

6. перемещать прямую целевой функции параллельно самой себе по области решения, достигая max f при движении вектора n и min f при движении в противоположном направлении.

7. найти координаты точек max и min по чертежу и вычислить значения функции в этих точках (ответы).

7. Общая идея симплексного метода решения задач лп.

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

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

Алгоритм симплексного метода:

1. Мат. модель задачи привести к каноническому виду

2. Построить начальный опорный план задачи

3. Составить симплексную таблицу и проверить выполнение критериев оптимальности

4. Переход к нехудшему опорному плану и проверка новой таблицы (нового опорного плана) на оптимальность.

8. Понятие предпочтительной(базисной) и свободной переменной

Все переменные делятся на базисные и свободные. Базисные переменные – это переменные, которые входят в одно из ограничений с коэффициентом 1, а в остальные с коэффициентом 0. Остальные переменные в этой системе являются свободными(х₁, х₂, х₃…х_n). Решение системы наз допустимым, если все компоненты вектора решения неотрицательны. Решение с-мы наз базисным, если в нем все свободные переменные =0. Допустимое базисное решение наз опорным планом задачи. Т.о. для построения начального опорного плана задачи необходимо приравнять базисные переменные к свободным членам с-мы ограничений, а свободные переменные приравнять к нулю. Т.о. начальный опорный план(х₀): х₀ = (0,0,…0,в₁,в₂…в_n).