max z=sum(Cj*Xj)
Sum(Aij*Xj)=Bi
Xj>=0;
Приведение ЗЛП к каноническому виду:
1. Если в исходной задаче некоторое ограничение не было неравенством, то оно преобразуетсяв равенство, введением в левую часть некоторой неотрицательной переменной (если стоит «≤», то со знаком «+», если «≥» - со знаком «-»).
В каждое из неравенств вводится своя “уравнивающая” переменная, после чего система ограничений становится системой уравнений.
2. Если в исходной задаче некоторая переменная не подчинена условию неотрицательности, то ее заменяют (в целевой функции и во всех ограничениях) разностью неотрицательных переменных, l - свободный индекс
3. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1)
4. Наконец, если исходная задача была задачей на минимум, то введением новой целевой функции F1 = -F мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F1.
Таким образом, всякую задачу линейного программирования можно сформулировать в канонической форме.
В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений ее состоит из одних линейных неравенств типа «<=» или «>=». Все переменные задачи неотрицательны. Всякую задачу линейного программирования можно сформулировать в стандартной форме. Преобразование задачи на минимум в задачу на максимум, а также обеспечение не отрицательности переменных производится так же, как и раньше. Всякое равенство в системе ограничений равносильно системе взаимопротивоположных неравенств:
Существует и другие способы преобразования системы равенств в систему неравенств, т.е. всякую задачу линейного программирования можно сформулировать в стандартной форме.
Симплексный метод (назначение метода, приведение систем к предпочтительному виду (3 случая), построение начального опорного плана)
В общем виде, когда в задаче участвуют N-неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n-мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах. Решить данные задачи графически, когда количество переменных более 3 весьма затруднительно. Существует универсальный способ решения задач линейного программирования, называемый симплекс-методом.
Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.
Симплекс-метод является основным в линейном программировании. Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение функции цели при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.
Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные.
Имея систему ограничений, приведенную к общему виду, то есть к системе m линейных уравнений с n переменными (m < n), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще.
Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то, осуществляется переход к другому, обязательно допустимому базисному решению.
Симплексный метод гарантирует, что при этом новом решении линейная форма, если и не достигнет оптимума, то приблизится к нему. С новым допустимым базисным решением поступают так же, пока не находят решение, которое является оптимальным.
Если первое найденное базисное решение окажется недопустимым, то с помощью симплексного метода осуществляется переход к другим базисным решениям, которые приближают нас к области допустимых решений, пока на каком-то шаге решения либо базисное решение окажется допустимым и к нему применяют алгоритм симплексного метода, либо мы убеждаемся в противоречивости системы ограничений.
Таким образом, применение симплексного метода распадается на два этапа: нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности; нахождение оптимального решения.
Приведение к предпочтительному виду. Построение начального опорного плана
1) Пусть система ограничений имеет вид
Xi+ 
ijXj=bi , bi=>0,(i=1,m)
X0=(0,0,…,0,bi)
Z(x0)=0.
Ограничение канонической задачи линейного программирования имеет предпочтительный вид, если при неотрицательной его части левая часть содержит переменную, входящую с коэффициентом равным 1, а остальные с коэффициентом равным 0. Если каждое ограничение канонической задачи линейного программирования имеет предпочтительный вид, т.е. система ограничений приведена к единичному неотрицательному базису, то начальный опорный план строиться следующим образом: Предпочтительные переменные выбираются в качестве базисных, а все остальные свободные.
2) Сведение задачи к каноническому виду, путем введения дополнительной переменной
ijXj<=bi, bi>=0
Xn+i>=0
Дополнительную переменную вводят с коэффициентом равным 0
ijXj+Xn+1=bi, bi>=0
X0=(0,…,0,b1,...,bm)
3)
ijXj>=bi , bi>=0
ijXj-Xn+i=bi
M-задача
Max(min)Z= 
jXj-(+)M 
i
Дата добавления: 2015-04-20; просмотров: 188 | Поможем написать вашу работу | Нарушение авторских прав |