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

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

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

Совместная система неравенств – система, которая имеет хотя бы одно решение. Каждое из неравенств задачи линейного программирования определяет на координатной плоскости X1OX2 некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР) или многоугольником решений. Он всегда представляет собой выпуклуюфигуру.

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

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

Задача

Для более полного представления о задаче линейного программирования сделаем её геометрическую интерпретацию. Рассмотрим задачу:

, ограничения: , .

Порядок графического решения задачи:

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

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

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

4. Если ОДР не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня c₁x₁+c₂x₂=L (где L – произвольное число, например, кратное c₁ и c₂, т.е. удобное для проведения расчетов).

5. Построить вектор – вектор градиентного направления.

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

7. Определить координаты точки максимума (минимума) целевой функции x*=(x₁*,x₂*) и вычислить значение Z(x*). Для вычисления координат оптимальной точки x* необходимо решить систему уравнений прямых, на пересечении которых находится x*.

Градиент– вектор, показывающий направление наискорейшего возрастания функции.

, , – градиент.

Линия уровня – прямая, получаемая из целевой функции, при задании ей фиксированного значения: Z=c₁x₁+c₂x₂=const. Изменяя значения целевой функции, получаем семейство прямых, называемых линиями уровня. Линии уровня перпендикулярны вектору градиента.

Варианты решений

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

2. Оптимальных планов множество: линия уровня проходит через сторону ОДР.

3. Целевая функция не ограничена: линия уровня, сколько бы ее не перемещали, не может занять разрешенного положения.

4. ОДР состоит из одной точки, в которой целевая функция достигает max и min значений.

5. Задача не имеет решения: область допустимых решений – пустое множество, т.е. система ограничений несовместна.

Симплексный метод. Общая идея симплексного метода. Построение начального опорного плана. Признак оптимальности опорного плана. Симплексные таблицы. Переход к нехудшему опорному плану.

Симплексный метод – метод последовательного улучшения плана.

В алгебраических терминах симплексный метод предполагает:

– умение находить начальный опорный план;

– наличие признака оптимальности опорного плана;

– умение переходить к не худшему опорному плану.

Построение начального опорного плана.

Пусть задача линейного программирования представлена системой ограничений в каноническом виде:

Предпочтительный вид.

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

Базисный план.

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

Если система ограничений имеет вид, как на рисунке слева, то нужно задачу привести к каноническому виду, т.е. добавить к левым частям дополнительные переменные: x_n+i ³ 0 (i=1,m).

Получим систему ограничений, которая имеет предпочтительный вид, следовательно, начальный опорный план будет равен

X₀ = (0₁, 0₂, …, 0_n, b₁, b₂, …, b_m).

Т.е. базисными переменными будут дополнительные переменные. В целевую функцию дополнительные переменные входят с коэффициентами, равными нулю.

Пусть система ограничений имеет вид, как на рисунке слева.

Сведем ее к каноническому виду вычитанием дополнительных переменных x_n+i ³ 0 (i=1,m) из левой части.

Эта система не предпочтительного вида, потому что дополнительные переменные входят в нее с коэффициентами, равными –1, и базисный план является недопустимым. В таких случаях вводится искусственный базис. К левым частям ограничений равенств, не имеющих предпочтительного вида, добавляют искусственные переменные u_i (i=1,n). В целевую функцию эти переменные входят с коэффициентами М. В случае решения задачи на максимум коэффициенты берутся с минусом, при решении задачи на минимум – коэффициенты берутся с плюсом. На самом деле число М – это большое положительное число. Полученная задача называется М-задачей, ее система ограничений имеет предпочтительный вид и соответствует исходной.

М-задача. Система ограничений этой задачи имеет предпочтительный вид, ее начальный опорный план будет иметь вид X₀ = (0₁, 0₂, …, 0_n, b₁, b₂, …, b_m).

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

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

Выразим базисные переменные x₁, x₂, …, x_m через свободные переменные (x_m+1, x_m+2, …, x_n) и подставим их в целевую функцию. После группировки подобных членов получим

Введем обозначения

D₀ = c₁b₁ + c₂b₂ + … + c_mb_m = С_БА_0;

D_j = c₁a_1j + c₂a_2j + … + c_ma_mj = С_БА_j;

С_Б = (с₁, с₂, …, с_m) – вектор коэффициентов целевой функции при базисных переменных;

A₀ = (b₁, b₂, …, b_m)^T – вектор-столбец свободных членов;

A_j = (a_1j, a_2j, …, a_mj)^T – вектор-столбец коэффициентов при переменных x_j.

Последняя строка называется индексной строкой; число D₀ – это значение целевой функции для начального опорного плана Х₀; D_j называется оценками свободных переменных.

Задачу запишем в виде симплекс-таблицы

Критерии оптимальности опорного плана.

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

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

Пример

min Z = 2x₁ – x₂ + 3x₃ – 2x₄ + x₅;

x₂ + 0.5x₃ + 0.5x₅ = 1.5;

x₃ + x₄ = 2;

x₁ – 0.5x₃ + 0.5x₅ = 0.5.

D₀ = С_БА₀ = (-1)*1.5 + (-2)*2 + 2*0.5 = -4.5;

D₁ = C_БА₁ – С₁ = 2 – 2 = 0;

D₂ = С_БА₂ – С₂ = -1 – (-1) = 0;

D₃ = C_БА₃ – С₃ = -0.5 – 2 – 1 – 3 = -6.5;

D₄ = С_БА₄ – С₄ = -2 – (-2) = 0;

D₅ = C_БА₅ – С₅ = -0,5 + 1 – 1 = -0,5.

Задача на минимум, оценки D_j должны быть не положительными, следовательно,

план X₀ = (0.5, 1.5, 0, 2, 0); Z(X₀) = -4.5.

Понятие двойственности и построение двойственных задач для симметричных задач линейного программирования. Принцип двойственности.

Понятие двойственности.

Прямая задача ; ; x_j ³ 0 (j=1,n).

Двойственная задача ; _; y_i ³ 0 (i=1,m).

По мат. модели одной из этих задач можно легко построить модель двойственной к ней задачи.

Правила построения двойственной задачи:

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

2. Коэффициенты c_j целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.

3. Свободные члены b_i ограничений прямой задачи являются коэффициентами целевой функции двойственной задачи.

4. Матрица ограничений двойственной задачи – это транспонированная матрица прямой задачи.

5. Если прямая задача на максимум, то система ограничений – неравенства вида (£). Двойственная задача же задача будет на минимум и ее система ограничений будет в виде (³).

6. Число ограничений прямой задачи равно числу переменных двойственной задачи, а число ограничений двойственной равно числу ограничений прямой задачи.

7. Все переменные в обеих задачах больше либо равны нулю.