Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)


 

 

 

 



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



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

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

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

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

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

Задача

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

X0 = (01, 02, …, 0n, b1, b2, …, bm).

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

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

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

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

М-задача. Система ограничений этой задачи имеет предпочтительный вид, ее начальный опорный план будет иметь вид X0 = (01, 02, …, 0n, b1, b2, …, bm).

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

 

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

Выразим базисные переменные x1, x2, …, xm через свободные переменные (xm+1, xm+2, …, xn) и подставим их в целевую функцию. После группировки подобных членов получим

 

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

D0 = c1b1 + c2b2 + … + cmbm = СБА0;

Dj = c1a1j + c2a2j + … + cmamj = СБАj;

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

A0 = (b1, b2, …, bm)T – вектор-столбец свободных членов;

Aj = (a1j, a2j, …, amj)T – вектор-столбец коэффициентов при переменных xj.

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

 

 

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

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

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

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

Пример

min Z = 2x1 – x2 + 3x3 – 2x4 + x5;

x2 + 0.5x3 + 0.5x5 = 1.5;

x3 + x4 = 2;

x1 – 0.5x3 + 0.5x5 = 0.5.

 

D0 = СБА0 = (-1)*1.5 + (-2)*2 + 2*0.5 = -4.5;

D1 = CБА1 – С1 = 2 – 2 = 0;

D2 = СБА2 – С2 = -1 – (-1) = 0;

D3 = CБА3 – С3 = -0.5 – 2 – 1 – 3 = -6.5;

D4 = СБА4 – С4 = -2 – (-2) = 0;

D5 = CБА5 – С5 = -0,5 + 1 – 1 = -0,5.

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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


Просмотров 1396

Эта страница нарушает авторские права



allrefrs.ru - 2022 год. Все права принадлежат их авторам!