Табличная реализация симплекс – метода

Постановка задачи ЛП.

Модель задачи математического программирования включает:

1) Совокупность неизвестных величин Х=(x₁, x­­­₂, …, x_n), действуя на которые, систему можно совершенствовать. Их называют планом задачи;

2) Целевую функцию z(x) [f(x)];

3) Условия (или систему ограничений), налагаемые на неизвестные величины. Эти условия следуют из ограниченности ресурсов, из необходимости удовлетворения насущных потребностей, из условий производственных и технологических процессов. Математически ограничения выражаются в виде уравнений и неравенств. Их совокупность образует область допустимых решений.

План Х, удовлетворяющий системе ограничений задачи, называется допустимым.

Допустимый план, доставляющий целевой функции экстремальное значение, называется оптимальным.

Оптимальный план обозначается Х*, а экстремальное значение целевой функции – z(Х*)=z*

 

Модель задачи ЛП может быть записана в одной из приведённых ниже форм.

1. Общая, или произвольная, форма записи:

 

2. Симметричная, или стандартная, форма записи:

 

3. Каноническая, или основная, форма записи:

 

Указанные формы записи ЗЛП эквивалентны, т.е. каждая из них с помощью несложных преобразований может быть сведена к другой форме.

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

min z(x)=-max (-z(x))

Неравенство типа ≥ путём умножения левых и правых частей на -1 можно превратить в неравенство типа ≤, и наоборот.

Ограничения – неравенства

преобразуются в ограничения – равенства путём прибавления (вычитания) к левым частям дополнительных (балансовых) неотрицательных переменных x_n+1≥0:

.

В случае необходимости ограничение – равенство

можно записать в виде системы неравенств:

­Если в ЗЛП какая-то переменная x_k не подчинена условию неотрицательности, её заменяют разностью двух других неотрицательных переменных и :

.

Симплекс – метод

Существует универсальный способ решения задач линейного программирования, называемый симплекс – методом.

Идея симплекс – метода заключается в следующем: сначала надо найти некоторую (начальную) вершину многогранника допустимых решений (начальный опорный план), затем надо проверить это решение на оптимальность. Если оно оптимально, то решение найдено; если нет, то надо перейти к другой вершине многогранника и вновь проверить решение на оптимальность. При этом при переходе от одной вершины к другой значение целевой функции убывает (в задаче на min) или возрастает (в задаче на max).

Для построения симплекс – метода решения задач ЛП соответствующие модели должны быть представлены в канонической форме.

Построение начального опорного плана.

1 случай. В системе ограничений имеется единичный неотрицательный базис, т.е. ЗЛП имеет вид:

max z=c₁x₁+c₂x₂+…+c_nx_n;

Без ограничения общности можно положить, что базисными являются первые m переменные. Тогда начальный опорный план содержит m базисных и (n-m) свободных переменных. Свободные переменные приравниваются нулю, а базисные – свободным членам. Получаем начальный опорный план

2 случай. Система ограничений имеет вид:

Приводим задачу к каноническому виду, добавляя к левым частям неравенств дополнительные неотрицательные переменные x_n+1, x_n+2, …, x_n+m. Получим систему ограничений

,

в которой базисными являются переменные x_n+1, …, x_n+m, а свободными x₁, x₂, …, x_n.

В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю:

z=c₁x₁+c₂x₂+…+c_nx_n+0∙x_n+2+…+0∙x_n+m

 

3 случай. Система ограничений имеет вид:

(1)

Приводим задачу к каноническому виду, вычитая из левых частей неравенств дополнительные неотрицательные переменные x_n+1­, x_n+2, …, x_n+m. Получим систему ограничений:

, (2)

которая не содержит единичного неотрицательного базиса. В этом случае может быть использован искусственный базис. Вводится m искусственных переменных .

(3)

Искусственные переменные ω₁, …, ω_m теперь станут базисными, а переменные x₁, x₂, …, x_n+m – свободными.

В целевую функцию z искусственные переменные входят с коэффициентом M со знаком “+”, если эта задача минимизации, и со знаком “-”, если – максимизации. При этом M полагается достаточно большим положительным числом. Т.о. целевая функция имеет вид:

z=c₁x₁+…+c_nx_n±Mω₁±Mω₂±…±Mω_m.

 

Преобразованная подобным образом ЗЛП называется M-задачей.

В оптимальном плане все искусственные переменные ω_i должны быть равны нулю, т.к. в исходной задаче таких переменных нет. Дополнительные переменные x_n+1, …, x_n+m могут иметь положительные значения.

 

Табличная реализация симплекс – метода

Условия задачи заносятся в таблицу

 

	A1 A2 An
БП			x1	x2	…	xn
c1	c2	…	cn
			Рабочее поле
Индексные оценки, Δj	Δ0	Δ1	Δ2	…	Δn
	z(x0)

В столбец БП заносятся базисные переменные.

Столбец С_Б содержит коэффициенты целевой функции, стоящие при базисных переменных.

Столбец А₀ (базисные значения) содержит значения БП в опорном плане.

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

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

Признак оптимальности опорного плана:

1. если исходная задача на max и для некоторого опорного плана все индексные оценки Δ_j≥0, то такой план оптимален.

2. если исходная задача на min и для некоторого опорного плана все индексные оценки Δ_j≤0, то такой план оптимален.

Переход к нехудшему опорному плану.

Если в таблице все Δ_j≥0 (max) {Δ_j≤0 (min)}, то начальный опорный план Х₀ оптимален. Если же существуют Δ_j<0 {Δ_j>0}, то находим среди них (неправильных индексных оценок) максимальную по модулю:

Δ_j<0

{Δ_j>0}

 

Столбец j₀ называется разрешающим. Переменную x_j0, соответствующую разрешающему столбцу, следует ввести в базис.

Для определения переменной, выводимой из базиса, находят симплексные отношения: для этого делим соответственно элементы A₀ на положительные коэффициенты A_j0. Среди симплексных отношений определяют наименьшее; оно и укажет строку, в которой содержится исключаемая из базиса переменная x­_i0. Строка i₀, соответствующая минимальному симплексному отношению, называется разрешающей. Элемент, стоящий на пересечении разрешающего столбца и разрешающей строки, также называется разрешающим.

 

 

Строим новую симплексную таблицу по правилу:

1. элементы разрешающей i₀ -той строки делим на разрешающий элемент;

2. все элементы разрешающего столбца j₀ равны нулю (включая Δ_j0), за исключением

3. столбцы, соответствующие оставшимся БП остаются без изменений;

4. остальные элементы получаем по правилу прямоугольника:

 

Элементы? = (произведению элементов по главной диагонали минус произведение элементов по побочной диагонали), деленному на разрешающий элемент.

Контроль вычислений элементов индексной строки осуществляется по формулам:

 

Признак неограниченности целевой функции:

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