Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Симплексный метод решения задачи линейного программирования
|
|
Пусть имеется ЗЛП, записанная в стандартной форме:
max 
, (1)
(2)
Обозначим через 
и 
векторы-столбцы:
, 
и через 
- вектор-строку 
.
Тогда условия (1) и (2) можно записать в виде
max 
, 
или max ,
Прежде чем приступить к обоснованию симплексного метода, множество всех векторов 
, удовлетворяющих условию , обозначим через 
и введем несколько определений:
Определение 1. Линейная функция, определенная на выпуклом многограннике К, достигает своего оптимального значения в крайней точке этого многогранника.
Определение 2. Допустимая точка называется базисной или опорной (опорным планом), если она соответствует крайней точке многогранника решений;
Определение 3. Допустимая точка называется вырожденной, если менее чем 
значений 
отличны от нуля (
- число ограничений в задаче);
Определение 4. Если X – крайняя точка многогранника К, то не более 
её координат отличны от нуля, и векторы 
, коэффициенты при которых отличны от нуля, линейно независимы.
Пусть 
- крайняя точка многогранника решений 
, определяемого равенством , причем координат 
точки 
отличны от нуля, т.е.
- невырожденный опорный план задачи.
Согласно определению 4, векторы 
линейно независимы и образуют базис 
-мерного пространства. Функция цели 
в точке 
принимает значение 
и равенство объединяется в равенство 
(3)
Найдём опорный план 
, которому соответствует значение 
функции цели 
. Поскольку векторы 
образуют базис, то любой вектор 
может быть представлен в виде линейной комбинации этих векторов 
. Выберем вектор 
и, умножив его на число 
, прибавим к левой части равенства (3), а затем вычтем из неё 
, в результате получим
(4)
Так как 
, то получим 
.
Таким образом, если выбрать точку 
с координатами
то она будет удовлетворять условию 
и, если при этом все координаты точки 
будут неотрицательны, т.е. 
(5), то будет допустимой точкой задачи. Условие (5) выполняется, если выбрать 
, (6)
где берётся min только положительных отношений 
и 
. В случае, когда все 
, величину 
можно выбрать как угодно большой. Это свидетельствует о неограниченности многогранника решений. Пусть выбрано , удовлетворяющее условию (6); тогда имеем в предположении, что 
: 
. Координаты второй точки будут:
При выборе 
в соответствии с (6) обращается в нуль лишь одна координата 
, поэтому новое решение 
, как и старое 
, содержит 
положительных координат. Таким образом точка является опорным планом задачи и переход от плана к плану соответствует переходу от одной крайней точки многогранника решений к другой.
Выясним, как следует выбирать вектор 
, чтобы при переходе от одной крайней точки к другой линейная функция 
по крайней мере не убывала.
Точке соответствует значение функции цели , равное
Преобразовав это выражение для 
, получим 
, где 
. Очевидно 
, если 
.
Решение задачи 1 симплексным методом
max 
Стандартная форма max 
| Ба- зис | сz | bi | θ | Замечания | ||||||
| Результи- рующая строка | zопт | |||||||||
| Результи- рующая строка | zопт | |||||||||
| Результи- рующая строка | zопт | |||||||||
Презентация решения задачи 1 симплексным методом