Симплекс-метод решения задачи линейного программирования. Табличная реализация симплекс-метода в задаче об ассортименте выпускаемой продукции. Алгоритм поиска оптимального плана
Симплекс-метод решения задачи линейного программирования
Стандартная
форма задачи линейного программирования
формулируется так: найти неотрицательные
значения переменных 
,
удовлетворяющих условиям:
…
и обращающих в максимум линейную функцию этих переменных
К этой форме можно свести любую задачу линейного программирования, рассмотренную в вопросе №1.
Оптимальное решение при использовании симплексного метода находят в соответствии со следующим алгоритмом.
Вначале находится некоторое допустимое базисное решение. Если n – число неизвестных, а m – число уравнений, то для определения базисного решения следует принять n-m переменных за свободные, приравнивая их число и разрешая получившуюся систему уравнений относительно базисных переменных. В том случае, когда некоторые базисные переменные окажутся отрицательными, необходимо выбрать другие базисные переменные.
Когда базисное решение будет допустимым, целевая функция проверяется на максимум. Если максимума целевой функции нет, то в новый базис включается переменная, увеличение которой приводит к увеличению целевой функции. Если же такой переменной нет, то найденное решение оптимально. В противном случае система уравнений разрешается относительно новых базисных переменных.
Табличная реализация симплекс-метода в задаче об ассортименте выпускаемой продукции
Исходная таблица
|
x1 |
x2… |
xm |
xm+1… |
xn |
b1 |
a11 |
a12… |
a1m |
a1m+1… |
a2n |
b2 |
a21 |
a22… |
a2m |
a2m+1… |
a2n |
bk |
ak1 |
ak2… |
akm |
akm+1… |
akn |
bm |
am1 |
am2… |
amm |
amm+1… |
amn |
0 |
c1 |
c2… |
cm |
cm+1… |
cn |
Переход к базису из векторов
|
1 |
0… |
0 |
|
|
|
0 |
1… |
0 |
….. |
….. |
|
0 |
0… |
0 |
….. |
….. |
|
0 |
0… |
0 |
….. |
….. |
|
0 |
0… |
1 |
|
|
|
0 |
0… |
0 |
|
|
{Нижняя строка – строка оценок; левый столбец – допустимый план; левый нижний квадрат – целевая функция с обратным знаком.}
Cтандартный алгоритм симплекс-метода
Для текущего базисного плана приводится критерий оптимальности: если в строке оценок нет положительного коэф. , план и задача решена.
Если среди ,…, есть >0, план можно улучшить за счет ввода в числе базисных той свободной переменной, для которой оценка макс.
Для определения переменной, которую следует внести из числа базисно, нужно просмотреть столбец матрицы A , соотв. включенной в базис новой переменной. Если все элементы этого столбца <=0, то задача решения не имеет. Если есть элементы> то выбирается тот, для которого величина
/
-
min.
Тем самым определяется базис перем.,
вывед из матрицы.Столбец с ведущим элементом приводится к виду, в котором ведущий элемент равен 1, остальные – неизм.
Шаги 1-4 повторяют до тех пор, пока не будет получено оптимальное решение.