Лекция 3. Идея симплексного метода заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по

-3-

СИМПЛЕКСНЫЙ МЕТОД

Идея симплексного метода заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному. Опорным решением называется допустимое неотрицательное решение.

Алгоритм симплексного метода

1. Математическая модель должна быть канонической. Если она неканоническая, то её надо привести к каноническому виду.

2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу. Все строки таблицы 1-го шага, за исключением строки ∆_j заполняем по данным системы ограничений и целевой функции:

сi	БП	с1	с2	…	cm	cm+1	…	cn
x1	x2	…	xm	xm+1	…	xn	fi
c1	x1			…		h1,m+1	…	h1n	f1
c2	x2			…		h2.m+1	…	h2n	f2
…	…	…	…	…	…	…	…	…	…
cm	xm			…		hm,m+1	…	hmn	fm
	∆j			…		∆m+1	…	∆n

Индексная строка для переменных находится по формуле

и по формуле для свободного члена.

Возможны следующие случаи при решении задачи на максимум:

- если все оценки , то найденное решение оптимальное;

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

- если хотя бы одна оценка отрицательна, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению;

- если отрицательных оценок в индексной строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка.

Если хотя бы одна оценка , то к -й столбец принимаем за ключевой. За ключевую строку принимаем ту, которой соответствует минимальное отношение свободных членов (f_i) к положительным коэффициентам к -го столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называется ключевым элементом.

3. Заполняем симплексную таблицу 2-го шага:

- переписываем ключевую строку, разделив её на ключевой элемент;

- заполняем базисные столбцы;

- остальные коэффициенты таблицы находим по правилу «прямоугольника». Оценки можно считать по приведённым выше формулам или по правилу «прямоугольника». Получаем новое опорное решение, которое проверяем на оптимальность, и т. д.

Правило «прямоугольника» заключается в следующем. Пусть ключевым элементом 1-го шага является элемент 1-й строки (m+1)-го столбца h_1,m+1. Тогда элемент i -й строки (m+2)-го столбца 2-го шага – обозначим его согласно правилу «прямоугольника» выражается формулой

,

где h_i,m+2, h_i,m+1, h_1,m+1 – элементы 1-го шага.

Примечание 1. Если целевая функция требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок ∆_j при всех

Примечание 2. В случае, если задача на минимум не решается по каким-либо причинам, можно попробовать решить задачу на максимум, изменив целевую функцию на противоположную. А потом умножить найденное значение целевой функции на (-1).

Примечание 3. В случае, если модель каноническая, но нет переменных, которые можно использовать в качестве базисных (т. е. таких, которые в одном уравнении стоят с коэффициентом 1, а в других вообще отсутствуют), нужно по своему усмотрению выбирать базисные переменные, определять ключевой столбец и строку, пересчитывать элементы таблицы по правилу «прямоугольника», не заполняя оценочной строки. Это нужно проделывать до тех пор, пока не будут найдены все базисные переменные. Затем заполнить оценочную строку и определить, является ли найденное решение оптимальным. Если нет, то пересчитать таблицу.

Дата добавления: 2014-01-11