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

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

выпуклое множество не выпуклое множество

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

Множество называется ограниченным, если существует шар, радиусом R, содержащий в себе всё множество.

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

точек.

Лемма Пересечение любого количества выпуклых множеств является выпуклым множеством.

возьмем произвольную точку А4 и через нее проведем отрезок А1А4.
Так как точка А принадлежит отрезку А1А4, то она — выпуклая линейная комбинация его концов, т. е.
А = t1A1 + t4А4, t1 ≥ 0, t4 ≥ 0,
t1 + t4 = 1. (2.46)
Точка А4 принадлежит отрезку А2А3, следовательно, является выпуклой линейной комбинацией его концов, т. е.
А4 = t2А2 + t3А3, t2 ≥ 0, t3 ≥ 0, t2 + t3 = 1. (2.47)
Подставляя (2.47) в (2.46) получаем
А = t1A1 + t4(t2А2 + t3А3) = t1А1 + t2t4А2 + t3t4А3.
Полагая t1 = λ1, t2t4 = λ2, t3t4 = λ3, окончательно имеем
А = λ1А1 + λ2А2 + λ3А3,
λ1 ≥ 0, λ2 ≥ 0, λ3 ≥ 0, λ1 + λ2 + λ3 = 1, (2.48)
т. е. точка А — выпуклая линейная комбинация вершин А1, А2, А3.
В выпуклом многоугольнике, имеющем n вершин (n > 3), добавляя к правой части соотношения (2.48) остальные n ‑ 3 вершины, умноженные на нуль, окончательно получим
А = λ1А1 + λ2А2 + λ3А3 + 0⋅А4 + ... + 0⋅Аn,
λI ≥ 0 (i = 1, 2, ..., n), ,
т. е. точка А — выпуклая линейная комбинация угловых точек многоугольника.

в пространстве параллельны.

(градиент) f = grad(f) – вектор из частных производных =

Градиент всегда показывает направление возрастания функции. Вектор градиент функции в точке всегда перпендикулярен касательной.

линейного программирования выпукло.
(или ОДЗ ЗЛП выпукла)

Доказательство.
Необходимо доказать, что если Х1 и Х2 — планы задачи линейного программирования, то их выпуклая линейная комбинация Х = λ1Х1 + λ2Х2, λ1 ≥ 0, λ2 ≥ 0, λ1 + λ2 = 1 также план задачи.
Так как Х1 и Х2 — планы задачи, то выполняются соотношения
АХ1 = А0, Х1 ≥ 0, АХ2 = А0, Х2 ≥ 0.
Перемножая
АХ = A(λ1Х1 + λ2Х2) = λ1АХ1 + λ2АХ2 = λ1А0 + λ2А0 =
= (λ1 + λ2)А0 = А0,
получаем, что Х удовлетворяет системе (2.43).
(2.52)
xi ≥ 0 (i = 1, 2, ..., n) (2.53)
Но так как Х1 ≥ 0; Х2 ≥ 0, λ1 ≥ 0, λ2 ≥ 0, то и Х ≥ 0, т. е. удовлетворяет и условию (2.53). Таким образом Х — план задачи линейного программирования.

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

Обозначим его через К. В двумерном пространстве К имеет вид многоугольника, изображенного на рис. 2.5. Обозначим угловые точки К через Х1, Х2, ..., Хp, а оптимальный план — через Х0. Тогда Z(X0) ≤ Z(X) для всех Х из К. Если Х0 — угловая точка, то первая часть теоремы доказана. Предположим, что Х0 не является угловой точкой; тогда Х0 на основании теоремы 1 можно представить как выпуклую линейную комбинацию угловых точек К, т. е.
Х0 = λ1Х1 + λ2Х2 + ... + λpХp,
λI ≥ 0 (i = 1, 2, ..., p), .
Так как Z(X) — линейная функция, получаем
Z(X) = Z(λ1Х1 + λ2Х2 + ... + λpХp) =
= λ1Z(X1) + λ2Z(X2) + ...
… + λpZ(Xp). (2.54)

наименьшее [пусть оно соответствует угловой точке Хk (1 ≤ k ≤ p)] и обозначим его через m, т. е. Z(Xk) = m. Заменим в (2.54) каждое значение Z(Xi) этим наименьшим значением. Тогда, так как λi ≥ 0, , то
Z(X0) ≥ λ1m + λ2m + ... + λpm = m.
По предположению, Х0 — оптимальный план, поэтому, с одной стороны, Z(X0) ≤ m, но с другой стороны, доказано, что Z(X0) ≥ m, значит, Z(X0) = m = Z(Xk), где Xk — угловая точка. Итак, существует угловая точка Xk, в которой линейная функция принимает минимальное значение.
Для доказательства второй части теоремы допустим, что Z(X) принимает минимальное значение более чем в одной угловой точке, например в точках Х1, Х2, ..., Хq, 1< q ≤ p; тогда Z(X1) = Z(X2) = ... = Z(Xq) = m. Если Х — выпуклая линейная комбинация этих угловых точек:
Х = λ1Х1 + λ2Х2 + ... + λqХq , λI ≥ 0 (i = 1, 2, ..., q), ,
то
Z(X) = Z(λ1Х1 + λ2Х2 + ... + λqХq) = λ1Z(X1) + λ2Z(X2) + ...
… + λqZ(Xq) = λ1m + λ2m + ... + λqm = m.
т. е. линейная функция Z принимает минимальное значение в произвольной точке Х, являющейся выпуклой линейной комбинацией угловых точек Х1, Х2, ..., Хq .

в двумерном пространстве, т. е. ограничения содержат две переменные.
Найти минимальное значение функции
Z = C1x1 + C2x2
при условиях
х1 ≥ 0, х2 ≥ 0.

в ограничениях знаков неравенств на знаки точных равенств.
2. Находят полуплоскости, определяемые каждым из ограничений задачи.
3. Находят многоугольник решений.
4. Строят вектор N (C1; C2),
5. Строят прямую C1х1 + C2x2 = const.
6. Передвигают эту прямую в направлении вектора N, в результате чего либо находят точку (точки), в которой целевая функция принимает минимальное значение, либо устанавливают неограниченность снизу функции на множестве планов.
7. Определяют координаты точки минимума функции на множестве планов.

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

переменных.

– неотрицательные,

оптимальное решение исходной задачи.

то такое опорное решение является оптимальным.

Теорема 1 Пусть исходная задача решается на минимум, тогда если для некоторого опорного решения все z-оценки

получаем

случае, когда все

неположительные,

в

k-ом столбце системы ограничений есть хотя бы
одно положительное число, т.е. не все

, то существует

, что

, где x – исходное

Теорема 4 Если опорное решение ЗЛП не вырождено и

и в k-ом

столбце системы ограничений нет ни одного положительного числа, т.е. все

, то целевая функция
не ограничена на ОДР.

такое опорное решение

опорное.