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

• 1 условие. Система ограничений должна быть приведена к единичному базису (15), т.е. каждое уравнение системы ограничений разрешают относительно какой-либо переменной. В системе ограничений (12) x₃, x₄, x₅  – называются базисными, а x₁, x₂ – свободными;
• 2 условие. Базисные переменные должны принимать только положительные значения, т.е. ее члены в каждом ограничении должны быть не отрицательными.

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

Например, когда мы задачу ЛП (9 - 11) привели к каноническому виду (12), то система получилась приведённой к единичному базису, причем свободные члены неотрицательны, значит, мы имеем опорный план

(1.13)

и на этом 1-я часть симплекс метода закончена. Приступают ко 2-ой части  улучшают опорный план до оптимального в симплекс-таблице. Дальнейший алгоритм симплекс метода рассмотрим на конкретной задаче.

Задача. Максимизировать  функцию F=ax₁+ax₂  при ограничениях

(1.14)

Решение. Приводим эту модель к канонической форме, прибавив в  левой части каждого неравенства  соответственно - балансовые переменные. Они же будут базисными переменными. Базисные переменные войдут в целевую функцию с нулевыми коэффициентами, в результате получим:

(1.15)

Запишем начальное опорное  решение:

(1.16)

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

Симплекс - таблицу заполняем из коэффициентов при неизвестных из системы ограничений и функции, пример показан в таблице 1.1.

Таблица 1.1 – Первая итерация

Баз. перемен.	С	План	a1	a2	a3	a4	a5
	0	b	a11	a12	a13	a14	a15
	0	c	a21	a22	a23	a24	a25
	0	d	a31	a23	a33	a34	a35
		0	a1	a2	a3	a4	a5

В 1 таблице элементы индексной строки подсчитывают по следующему правилу:

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

В нашем примере это  правило выглядит так:

1)

2)

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

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

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

Это делается так:

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

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

Разрешающий элемент выбирается на пересечении разрешающего столбца  и разрешающей строки. В нашем  примере разрешающий элемент 5.

Составим вторую симплекс-таблицу, пример приведен в таблице 1.2.

Таблица 1.2 – Вторая итерация

Баз. перемен.	С	План	a1	a2	a3	a4	a5
	0	b	a11	a12	a13	a14	a15
	0	c	a21	a22	a23	a24	a25
	0	d	a31	a23	a33	a34	a35
		0	a1	a2	a3	a4	a5

 

 

Составим третью симплекс-таблицу, пример приведен в таблице 1.3.

Таблица 1.3 – Третья итерация

Баз. перемен.	С	План	a1	a2	a3	a4	a5
	0	b	a11	a12	a13	a14	a15
	0	c	a21	a22	a23	a24	a25
	0	d	a31	a23	a33	a34	a35
		t	a1	a2	a3	a4	a5

В первую очередь заполняются первые два столбика. Выводится из базиса переменная x₃ с коэффициентом 0 и вводится в базис бывшая свободная переменная x₂ с коэффициентом a₁₂. Затем подсчитываем новые элементы разрешающей строки. Для этого старые элементы разрешающей строки делим на разрешающий элемент (на a₁₂), а в разрешающем столбце во 2-ой таблице расставляем нули.

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

 

 

 

 

 

 

 

Рисунок 1 – Правила треугольника

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

(1.17)

Практический совет:

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

Примечание: коэффициент  индексной строки подсчитывают тоже по правилу прямоугольника.

На рисунке 2 показан подсчет элемента по правилу прямоугольника.

 

 

 

 

 

 

Рисунок 2 – Правила треугольника

(1.18)

По последней симплексной  таблице, где в индексной строке все оценки положительные, записываем оптимальное решение. Для этого  базисные переменные, указанные в  первом столбце, приравниваем к числам, стоящим в третьем столбце (план). Все остальные переменные являются свободными, они приравниваются к  нулю. Таким образом, получаем оптимальный  план:

(1.19)

При этом прибыль от реализации изделий  и равна ; в оптимальном плане означает, что сырье третьего вида не использовано полностью, осталось еще c кг, а x₃ =x₄ =0 говорит о том, что сырье первого и второго вида использовано полностью.

Можно ответ записать коротко:

при

(1.20)

 

2 Решение задачи  при помощи симплекс – метода

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

Задача:

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

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

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

 В таблице 2.1 приведены данные, характеризующие содержание (по весу) питательных веществ в каждом из ингредиентов и удельную стоимость каждого ингредиента. Заметим, что известняк не содержит ни белка, ни клетчатки.

Таблица 2.1 – Кормовые смеси

Ингредиент	Содержание питательных  веществ (кг/ингредиента)			Стоимость (руб./кг)
	Кальций	Белок	Клетчатка
Известняк	0.38	-	-	0.04
Зерно	0.001	0.09	0.02	0.15
Соевые бобы	0.002	0.50	0.08	0.40

Смесь должна содержать:  

не менее 0,8%, но не более 1,2% кальция;

не менее 22% белка;

не более 5% клетчатки.

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

2.2 Решение поставленной  задачи

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

Определим минимальное значение целевой функции F(X) = 0,04x₁+0,15x₂+0,4x₃ при следующих условиях - ограничений.

((1.21)

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x₄ со знаком плюс. В 2-м неравенстве смысла (≥) вводим базисную переменную x₅ со знаком минус. В 3-м неравенстве смысла (≥) вводим базисную переменную x₆ со знаком минус. В 4-м неравенстве смысла (≥) вводим базисную переменную x₇.

	(1.22)
	(1.23)

Для постановки задачи на минимум  целевую функцию запишем так:

F(X) = 0,04x1+0,15x2+0,40x3→ min

(1.24)