Задание 2. Симплекс-метод решения задачи линейного программирования

Сайт: www.melashchuk.com

 

Решить задачу 1 симплекс-методом.

Решение

Приводим задачу к каноническому виду:

 

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

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:

, где – коэффициенты при базисных переменных в целевой функции; – коэффициенты при переменной в системе ограничений; – коэффициент при переменной в целевой функции.

 

 

Опорное решение, коэффициенты разложений и оценки разложений векторов условий по базису опорного решения записываем в симплексную таблицу:

1 2 ↓ 0 0 0

	Б	Сб	А 0	Х 1	Х 2	Х 3	Х 4	Х 5	q l 2
	Х 3
	Х 4
←	Х 5		1,5						1,5
	f		D k	–1	–2

 

Начальное опорное решение не является оптимальным, так как в рассматриваемой задаче на максимум векторам Х ₁, Х ₂ соответствуют отрицательные оценки.

Найдем новое опорное решение, на котором значение целевой функции будет больше.

Так как из всех оценок D _i наименьшая оценка , то будем вводить в базис вектор Х ₂. Для этого вектора находим оценки .

Наименьшая из этих оценок соответствует вектору Х ₅. Поэтому выводим из базиса вектор Х ₅. За разрешающий элемент принимаем элемент . Получаем опорное решение с базисом :

 

 

1↓ 2 0 0 0

	Б	Сб	А 1	Х 1	Х 2	Х 3	Х 4	Х 5	q l 1
←	Х 3		1,5					-3	0,75
	Х 4							-2	1,4
	Х 2		1,5						–
	f		D k	-1

 

 

Опорное решение А ₁ не является оптимальным, так как в рассматриваемой задаче на максимум вектору Х ₁ соответствует отрицательная оценка.

Найдем новое опорное решение.

Вводим в базис вектор Х ₁. Исключаем из базиса вектор Х ₄. За разрешающий элемент принимаем элемент . Получаем второе опорное решение с базисом :

 

 

1 2 0 0 0

	Б	Сб	А 2	Х 1	Х 2	Х 3	Х 4	Х 5
	Х 1		0,75			0,5		-1,5
←	Х 4		3,25			-2,5		5,5
	Х 2		1,5
	f	3,75	D k			0,5		0,5

 

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

Таким образом, при .

Симплекс-метод решения задач линейного программирования (ЗЛП)

Симплекс-метод является универсальным методом решения ЗЛП, так как позволяет решить практически любую задачу, представленную в канонической форме.

Данный метод состоит в целенаправленном переборе опорных решений ЗЛП. Он позволяет за конечное число шагов расчета либо найти оптимальное решение, либо установить его отсутствие.

Алгоритм симплексного метода решения ЗЛП

1. Привести задачу к каноническому виду.

Каноническая ЗЛП имеет вид:

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

2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решения).

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

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

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

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

Для проверки опорного решения на оптимальность необходимо найти оценки разложения вектора условий по базису опорного решения:

,

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

Опорное решение является оптимальным, если:

1) в задаче на максимум все ;

2) в задаче на минимум все .

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

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

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

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

Вектор, вводимый в базис, из условия:

1) в задаче на максимум ;

2) в задаче на минимум .

Вектор, выводимый из базиса, находим из условия: при .

 

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается.

5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения.