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

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

Основные определения

Доказательство Докажем, что любая точка треугольника удовлетворяет теореме. В треугольнике A1А2А3 (рис.2.3) возьмем произвольную точку А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), , т. е. точка А — выпуклая линейная комбинация угловых точек многоугольника.

Геометрическая интерпретация задач линейного программирования

В этом разложении среди значений Z(Xi) (i = 1, 2, ..., p) выберем наименьшее пусть оно соответствует угловой точке Хk (1  k  p) и обозначим его через m, т. е. Z(Xk) = m. Заменим в (2.54) каждое значение Z(Xi) этим наименьшим значением. Тогда, так как i  0, , то В этом разложении среди значений Z(Xi) (i = 1, 2, ..., p) выберем наименьшее пусть оно соответствует угловой точке Х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.

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

Симплекс-метод