2.Осн.Виды записи злп,способы преобразования

ЗЛП в общей постановке имеет 3 формы:

- произвольная форма:

- симметричная форма:

- каноническая форма ЗЛП:

Преобразования:

1. Неравенство вида «≥» можно преобразовать в неравенство вида «≤» путём замены знаков в обеих частях.

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

3. min(f) = -max(-f), т.е. задачи минимизации функции при необходимости можно заменить задачей максимизации, и наоборот, т.к. экстремумы этих функций достигаются в одной и той же точке, а после решения задачи надо заменить знак оптимума на противоположный;

4. Преобразование неравенств в уравнения и уравнений в неравенства проводится на основании теоремы: Всякому решению (α₁;…; α_n) неравенства а₁х₁ +…+ a_nx_n≤a соответствует вполне определенное решение (α₁;…; α_n ; α_n+1) уравнения а₁х₁ +…+ a_nx_n + x_n+1= a, в котором x_n+1≥0. И наоборот, каждому решению (α₁;…; α_n ; α_n+1) уравнения а₁х₁ +…+ a_nx_n + x_n+1= a и неравенства x_n+1 ≥ 0 соответствует вполне определенное решение (α₁;…; α_n) неравенства а₁х₁ +…+ a_nx_n ≤ a.

На основании этой теоремы систему m линейных неравенств с n переменными

a₁₁x₁ + … + a_1nx_n ≤ a₁₀;

…..

a_m1x₁ + … + a_mnx_n ≤ a_m0

можно заменить эквивалентной системой m линейных уравнений с n+m переменными

a₁₁x₁ + … + a_1nx_n + x_n+1 = a₁₀;

…..

a_m1x₁ + … + a_mnx_n + x_n+m = a_m0

3.Геом.Интерпретация и осн.Св-ва злп.Графич.Решение

План задачи (х₁, х₂) – точка на плоскости. Каждое неравенство системы представляет собой полуплоскость. Полуплоскость – выпуклое множество (множество, в котором отрезок, соединяющий точки А и В этого множества, тоже принадлежат множеству). Система представляет собой пересечение полуплоскостей. При пересечении могут получиться:

- выпуклая многоугольная замкнутая область;

- выпуклая открытая многоугольная область;

- единственная точка; - луч;

- пустое множество; - отрезок.

Пересечение полуплоскостей принято называть областью допустимых решений (ОДР).

Геометрическая интерпретация целевой функции. Целевая функция представляет собой семейство параллельных прямых, которые называют линиями уровня (линиями постоянного значения целевой функции). Частные производные функции по х₁ и х₂ показывают скорость возрастания целевой функции вдоль координатных осей. Вектор-градиент (с₁; с₂) показывает направление наискорейшего возрастания целевой функции. Он выходит из точки (0, 0) и направлен в точку с координатами (с₁; с₂). Вектор-градиент перпендикулярен линиям уровня.

Графическим методом можно решать ЗЛП с n>2 переменными, если в ее канонической записи число неизвестных n и число линейных независимых уравнений m связаны соотношением n-m≤2.

1. Построить ОДР (выпуклое множество на пересечении полуплоскостей, определяемых неравенствами из системы ограничений ЗЛП).

2. Построить вектор-градиент С (-С) (показывает направление наибольшего возрастания (убывания) целевой функции).

3. Перпендикулярно С построить линию уровня f=0.

4. Перемещая линию уровня в градиентном направлении найти точку максимума или минимума ОДР.

5. Найти координаты точки максимума (минимума) и значение функции в этой точке.

В ходе решения ЗЛП графическим способом могут получиться:

1. Оптимальный план единственный: линия уровня и ОДЗ в крайнем положении имеют одну общую точку;

2. Оптимальных планов бесконечное множество: в разрешающем положении линия уровня проходит через грань ОДЗ;

3. Задача не имеет решения: ОДЗ=ø;

4. Целевая функция не ограничена, в этом случае добавляется еще одно ограничение.