Частные производные целевой функции по х1 и х2 показывают скорость ее возрастания вдоль данных осей координат и называются градиентами функции.

Базис пространства

Графический способ решения ЗЛП

Первая геометрическая интерпретация ЗЛП

Основные свойства ЗЛП

Решение ЗЛП графическим способом в случае многомерного пространства

Базис пространства

Базисным решением системы m линейных уравнений с n переменными называется решение, в котором все n - m неосновных переменных равны нулю.

Множество точек называется выпуклым, если вместе с двумя его точками М1 и М2 ему принадлежат и все внутренние точки отрезка М1М2.

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

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

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

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

Рассмотрим теперь несколько важных теорем, касающихся вершин выпуклых многогранников.

Теорема 1. Любая точка выпуклого многогранника является выпуклой комбинацией его вершин.

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

Теорема 3. Если известно, что система векторов линейно независима и такова, что где все , то точка является вершиной допустимой области.

План, соответствующий вершине допустимой области, называется опорным планом.

Графический способ решения ЗЛП

Совокупность чисел x ₁ , x ₂ ,.. x_n , удовлетворяющих ограничениям, называется решением.

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

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

Для нахождения направления возрастания (или убывания) целевой функции, находятся  частные производные:

 и .

Частные производные целевой функции по х1 и х2 показывают скорость ее возрастания вдоль данных осей координат и называются градиентами функции.

Градиентом функции Z ( x ) называется вектор , указывающий направление наиболее быстрого возрастания функции и ориентированный перпендикулярно линиям уровня.

Противоположное направление этого вектора есть направление наискорейшего убывания целевой функции или антиградиента.

В общем случае графически задача линейного программирования решается следующим образом:

1) строится множество допустимых решений D с учетом системы ограничений;

2) строится произвольная линия уровня целевой функции;

3) строится вектор градиентного направления;

4) при решении задачи на max перемещаем прямую Z ( x ) в направлении градиента, чтобы она заняла крайнее положение; при решении задач на min перемещаем прямую Z (x) в направлении антиградиента.

5) определяется оптимальный план.

В зависимости от области допустимых решений возможны следующие случаи при решении ЗЛП:

1) оптимальный план единственный. Тогда линия уровня целевой функции и область D в крайнем положении будут иметь одну общую точку (рисунок а);

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

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

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

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

А)                                       б)                    в)                   

                                                                                                                                                                                                                                                                                                                                                                                                                                                             

              г)                              д)                             е)          

Рассмотрим пример определения оптимального ассортимента продукции.

Предприятие изготавливает два вида продукции - П1 и П2, которая поступает в оптовую продажу. Для производства продукции используются два вида сырья - А и В. Максимально возможные запасы сырья в сутки составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции вида П1 и вида П2 дан в таблице.

Сырье