Решение задач линейного программирования
 |
|
|
|
|
|
|
Мастерская программиста Гирича Семёна Николаевича Решение задач линейного программирования |
|||||||||||
|
|||||||||||||
|
|||||||||||||
|
|||||||||||||
3. Решение методом симплекс-таблиц |
|
3.1. Приведение математической модели к каноническому виду 3.2. Векторный анализ 3.3. Метод искусственных переменных 3.4. Построение симплекс-таблицы 3.5. Анализ симплекс-таблицы 3.6. Пример(1) решения задачи ЛП методом симплекс-таблиц 3.7. Пример(2) решения задачи ЛП методом симплекс-таблиц Идея метода симплекс-таблиц
заключается в целенаправленном переборе вершин симплекса. Для начало перебора
необходимо выбрать опорную вершину с которой начнется перебор. Симплексный метод
решения задачи линейного программирования основан на переходе от одного опорного
плана к другому, (перебирая симплекс вершины) при котором значение целевой
функции возрастает (убывает). Указанный переход возможен, если известен
какой-нибудь исходный опорный план. Для составления такого плана необходимо
произвести векторный анализ, на основе которого определить опорную вершину, с
которой начнется перебор. Система неравенств приводится к
каноническому виду: x1 +
a1,m+1* xm+1
+ ... + a1s*
xs+...+
a1n*
xn = b1; ... x2 + a2,m+1* xm+1 + ... + a2s * xs+...+ a2n* xn = b2; ... xm + am,m+1* xm+1 + ... + ams* xs+...+ amn* xn = bm. Переменные x1, x2,...,xm, входящие с
единичными коэффициентами только в одно уравнение системы и с нулевыми - в
остальные, называются базисными. В канонической
системе каждому уравнению соответствует ровно одна базисная переменная.
Остальные n-m переменных (xm+1, ...,xn) называются небазисными переменными. При векторном анализе строятся вектора для каждой переменной: составляющими координатами n-мерного (n-количество уравнений системы) вектора будут коэффициенты этой переменной в соответствующих уравнениях. Как было сказано выше вектор в котором единичный коэффициент только в одном уравнении и нулеые коэффициенты в других - называется базисным. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. После проверки всех ограничений получается система в каноническом виде и появляется возможность заполнить начальную симплексную таблицу. 3.3. Метод искусственных переменных Зачастую случается так, что базисных векторов меньше чем количество уравнений, т.е. несколько уравнений не содерджат базисных переменных. В таком случае используют метод искусственных переменных для добавления базисных переменных. Так как введенные переменные не имеют отношения к существу задачи ЛП в исходной постановке, то необходимо добиться обращения в нуль искусственных переменных. Этого можно сделать с помощью двухэтапного симплекс-метода. Этап 1. Рассматривается искусственная целевая функция, равная сумме искусственных переменных, которая минимизируется при помощи симплекс-метода. Другими словами, производится исключение искусственных переменных. Если минимальное значение вспомогательной задачи равно нулю, то все искусственные переменные обращаются в нуль и получается допустимое базисное решение начальной задачи. Далее реализуется этап 2. Если минимальное значение вспомогательной задачи положительное, то по крайней мере одна из искусственных переменных также положительная, что свидетельствует о противоречивости начальной задачи, и вычисления прекращаются. Этап 2. Допустимое базисное решение, найденное на первом этапе, улучшается в соответствии с целевой функцией исходной задачи ЛП на основе симплекс-метода, т.е. оптимальная таблица 1 этапа превращается в начальную таблицу этапа 2 и изменяется целевая функция. 3.4. Построение симплекс-таблицы Выбираем начальное допустимое
базисное решение. Базисным решением называется решение, полученное при
нулевых значениях небазисных переменных, т.е. xi=0, i=m+1,...,n. Базисное решение называется допустимым базисным решением, если значения входящих в
него базисных переменных неотрицательны, т.е. xj
= bj
>=0, j=1,2,...,m. В этом случае целевая функция примет
следующий вид: S = cb* xb = c1* b1 + c2* b2+...+cm*
bm. Заполняем
первоначальную таблицу симплекс - метода: Таблица 2.3
cj
= cj - cb* Sj , где сb - вектор оценок
базисных переменных; Sj - j-тый столбец
в канонической системе, соответствующей рассматриваемому базису. Дополняем первоначальную таблицу c - строкой. Таблица 2.4
3. Если все оценки
cj <=0 (cj >= 0),
i=1,...,n, то текущее допускаемое решение - максимальное (минимальное). Решение
найдено. 4. Впротивном
случае в базис необходимо ввести небазисную переменную xr с наибольшим значением cj вместо одной из
базисных переменных (табл. 2.5).
Таблица 2.5
Таблица 2.6
6. Применяем
элементарные преобразования для получения нового допускаемого базового решения и
новой таблицы. В результате ведущий элемент должен равняться 1, а остальные
элементы столбца ведущего элемента принять нулевое значение.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
 |
 |
|||||
| © 2011 Семён Гирич, |
|
|
|||||
 |
 |
 |
![Система Orphus: Выделите текст с ошибкой и нажмите [Ctrl] + [Enter]](../../orphus/orphus.gif){kind=small}