Симплексный метод.

В конце 40-х годов американским математиком Дж. Данцигом был разработан широко используемый в настоящее время универсальный метод линейного программирования — симплексный метод.

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

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

Вид ресурса (сырья)	Запас сырья	Норма расхода сырья, на изготовление единицы продукции
		1	2	3
А	9	1	2	0
Б	6	0	1	1
В	3	2	2	0

Прибыль, получаемая предприятием от единицы продукции составляет 2, 1 и 3 тыс. руб. соответственно.

Необходимо составить такой план производства продукции, при котором прибыль от её реализации будет максимальной.

Решение:

Составим экономико-математическую модель задачи.

Обозначим через х₁, х₂ и х_з - количество планируемых единиц продукции.

Целевая функция определяет величину получаемой прибыли:

L(X) =2 x₁+ x₂ + 3x₃ max

Для их изготовления по­требуется х₁ + 2х₂ единиц ресурса первого вида, х₂ + х₃ единиц второго ресурса, 2х₁ + 2х₂ - третьего ресурса. Использование сырья для производства продукции не должно превышать запасов 9, 6 и 3 единиц соответственно. Ограничивающее условие по потреблению ресурсов и их запасами записывается в виде следующего неравенства:

х₁ + 2х₂  9

х₂ + х₃  6

2х₁ + 2х₂  3

Отдельные виды продукции или планируются к выпуску, или не планируются; поэтому искомые переменные могут быть только по­ложительными или равными нулю, то есть должны нести условие неотрицательности:

х₁  0, х₂ 0, х₃ 0.

В итоге получаем: L(X) =2 x₁+ x₂ + 3x₃ max

при ограничениях:

х₁ + 2х₂  9

х₂ + х₃  6

2х₁ + 2х₂  3

х₁  0, х₂ 0, х₃ 0.

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

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

L(X) =2 x₁+ x₂ + 3x₃ + 0х₄+ 0х₅ + 0х₆ max

х₁ + 2х₂ + х₄ = 9

х₂ + х₃ + х₅ = 6

2х₁ + 2х₂ + х₆ = 3

x_j  0, j=1,2,….6

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

У нас их четыре:

х₃ = 6 – ( х₂ + х₅)₎

х₄ = 9 – ( х₁ + 2х₂ )

х₅ = 6 - ( х₂ + х₃)

х₆ = 3 – (2х₁ + 2х₂)

Переменные эти называется базисными, а все остальные – небазисными, или свободными. Решение системы уравнений, соответствующее нулевым значениям свободных переменных, называется базисным.

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

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

В симплексной таблице может быть только три базисных переменных: возьмем х₃, х₄ и х₆.

Заполняем первую симплексную таблицу.

Таблица 2

СБ	ХБ	В	2	1	3	0	0	0
			Х1	х2	х3	х4	х5	х6
3	х3	6	0	1	1	0	1	0
0	х4	9	1	2	0	1	0	0
0	х6	3	2	2	0	0	0	1
Z j=cБхj		CБВ 18	0	3	3	0	3	0
j= zj - cj			-2	2	0	0	3	0

Порядок заполнения:

1. В первой строке записываем коэффициенты при переменных целевой функции.

2. В первом столбце записываем коэффициенты целевой функции при базисных переменных (С_Б).

3. Во втором столбце – базисные переменные (Х_Б).

4. В третьем – значения свободных членов соответствующего уравнения (В).

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

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

6. Предпоследняя строка определяется как сумма попарных произведений элементов первого столбца (С_Б) на соответствующий элемент столбца при переменной j.

7. Последняя строка таблицы называется индексной и равна разности предпоследней и первой строки (коэффициент при переменной j в целевой функции.

8. Находим значение целевой функции в базисном решении: L(X₀)= C_БВ.

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

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

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

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

Далее следует установить какую из прежних базисных переменных заменит х₁ с этой целью находим ключевую строку.

Ключевая строка отыскивается по наименьшему соотношению свободного члена (В) на соответствующий положительный элемент ключевого столбца. В нашем примере: 9/1=9 и 3/2=1,5. Значит ключевая строка принадлежит переменной х₆, которая должна уступить место новой базисной переменной х₁.

На пересечении ключевой строки и ключевого столбца расположен генеральный элемент.

Составляем новую таблицу по следующим правилам.

1. Для нахождения элементов вводимой строки (вместо старой ключевой) необходимо все элементы ключевой строки поделить на генеральный элемент.

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

3. Те столбцы и строки старой таблицы, у которых элемент в ключевой строке или столбце равен нулю, переносится в новую таблицу без изменений.

4. Все остальные элементы новой таблицы находят расчетом:

Элемент

ключевого столбца

Элемент

ключевой строки

х

Новый

элемент

Соответствующий старый элемент

= _ ____________________________

Генеральный

элемент

Таблица 3

СБ	ХБ	В	2	1	3	0	0	0
			х1	х2	х3	х4	х5	х6
3	х3	6	0	1	1	0	1	0
0	х4	7,5	0	1	0	1	0	-0,5
2	х1	1,5	1	1	0	0	0	0,5
Z j=cБхj		CБВ 21	2	5	3	0	3	1
j= zj - cj			0	4	0	0	3	1

В полученной таблице в индексной строке отсутствуют отрицательные элементы; следовательно, найдено оптимальное решение (х₁=1,5; х₂ = 0; х₃ =6; х₄ =7,5; х₅ =0; х₆ = 0). Целевая функция равна 21.

Полученное решение допустимо, так как удовлетворяет системе ограничений:

1,5 + 0 + 7,5 = 9 = 9

0 + 6 + 0 = 6 = 6

3 + 0 + 0 = 3 = 3

Проверим также значение целевой функции

L_max=2 * 1,5 + 1*0 + 3*6 + 0*7,5+ 0*0 + 0*0=21

То есть следует выпускать 1,5 единиц продукции первого вида и 6 единиц третьего, продукцию второго вида не выпускать. При этом будет получена максимальная прибыль 21 тыс. руб.

Получили х₄ = 7,5 (значение ослабляющей переменной). Это говорит о том, что первый вид сырья при оптимальном плане будет использован не полностью, остаток = 7,5.