Симплексный метод решения задачи линейного

Программирования

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

Предположим, составляется план производства для предприятия, выпускающего два вида продукции А и В. На изготовление единицы изделия А требуется затратить а₁ = 2 кг сырья первого типа, а₂ = 3 кг сырья второго типа и а₃ = 1 кг сырья третьего типа. Для единицы изделия B: b₁ = 1 кг сырья первого типа, b₂ = 4 кг сырья второго типа и b₃ = 3 кг сырья третьего типа. Производство обеспечено сырьем каждого типа в количествах 400 кг, 900 кг, 600 кг, соответственно. Стоимость реализации единицы изделия А составляет 60 (д. ед), а единицы изделия В – 40 (д. ед). следует составить план производства изделий А и В, обеспечивающий максимум прибыли от реализации.

Сформулируем задачу математически. Пусть х₁ и х₂ – неизвестные количества изготавливаемых изделий А и В, соответственно. Необходимо найти такие х₁ и х₂, чтобы выполнялись условия:

2x₁+x₂ 400

3x₁+4x₂ 900

X₁+3x₂ 600

X1 0,x₂ 0

и при этом функция f = 60 х₁ + 40 х₂ была максимальна. Система ограничений описывает условия производства. Функция f – целевая функция, а х₁ и х₂ - аргументы целевой функции.

Задача имеет стандартную форму. Представим эту задачу в канонической форме, введя дополнительные переменные х₃, х₄, х₅, экономический смысл которых - неиспользованное сырье, соответственно, первого, второго и третьего типов.

2x₁+x₂+x₃=400

3x₁+4x₂+x₄=900 (1.23)

X₁+3x₂+ x₅=600

X₁ 0,x₂ 0, x₃ 0,x₄ 0,x₅ 0 (1.24)

Функцию f представим в неявном виде:

f - 60x₁ – 40 x₂= 0

Заметим, что если бы в задаче требовалось найти не max f, a min Z, то следовало бы перейти к функции f = - Z.

Пусть переменные х₁, х₂, входящие в функцию f, будут свободными, а переменные х₃, х₄, х₅ – базисными. Базисные переменные выразятся через свободные следующим образом:

(1.25)

Полагая свободные переменные равными нулю, получим первое опорное решение:

x₁ = x₂ = 0; x₃ = 400; x₄ = 900; x₅ = 600

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

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

Таблица 5

№ 1	x1	x2	x3	x4	x5	bi	bi / aij
x3							400/2=200 Z
x4							900/3=300
x5							600/1=600
f	-60	-40

ñ

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

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

В последней строке таблицы среди отрицательных значений находим наибольший по абсолютной величине элемент (это (-60)). Столбец, в котором находится этот элемент, называется ведущим, он соответствует новой базисной переменной x₁. Делим свободные члены (b_i) на соответствующие элементы ведущего столбца (отрицательные элементы ведущего столбца и нули во внимание не принимаются) и среди частных от деления находим минимальное значение,

т.е. min

Строка, которой соответствует минимальное значение, называется ведущей строкой. Смысл этой операции – сократить перебор вершин многоугольника за счет выбора строки с наименьшим допустимым значением новой базисной переменной x₁. Ведущая строка соответствует старой базисной переменной x₃, которая переводится в свободные. На пересечении ведущей строки и ведущего столбца расположен разрешающий элемент. В нашем случае это число а* = 2.

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

w Ведущую строку переписываем во вторую таблицу, поделив предварительно все элементы строки на разрешающий элемент;

w Все элементы ведущего столбца, кроме разрешающего, заменяем нулями, так как переменная в ведущей строке, соответствующая этому столбцу, становится базисной;

w Столбцы соответствующие оставшимся базисным переменным переписываем в новую таблицу без изменения;

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

a_{ij A}

В а*

Рис. 1.4. Схема правила прямоугольника

На рис. 1.4. элемент исходной таблицы a_ij и разрешающий элемент а* располагаются на одной из диагоналей прямоугольника; А – элемент ведущего столбца, стоящий в одной строке с a_ij ; В – элемент ведущей строки, стоящий в одном столбце с a_ij. Тогда элемент a_ij´ новой таблицы определяется по формуле:

a_ij´ ₌ a_ij-(A*B)/ а*

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

Таблица 6

№ 2	x1	x2	x3	x4	x5	bi	bi / aij
x1		½	½
x4		2,5	-1,5				120 Z
x5		2,5	-0,5
f		-10

ñ

Из полученной симплексной таблицы можно записать второе опорное решение. Переменные х₂, х₃ являются свободными и равны нулю: х₂ = х₃ = 0. Базисные переменные: x₁ = 200; х₄ = 300; х₅ = 400. Прибыль составляет: f = 12000 (д.ед.).

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

Преобразуя таблицу 6, как и ранее, методом Гаусса, получим таблицу 7.

aТаблица 7

№ 3	x1	x2	x3	x4	x5	bi
x1			4/5	-1/5
x2			-3,5	2/5
x5				-1
f

В последней строке таблицы 7 все элементы положительны, что означает, что полученное опорное решение является оптимальным. Предприятие получит максимальную прибыль от реализации выпускаемых изделий при выпуске х₁ = 140 ед. изделия А, х₂ = 120 ед. изделия В. При этом ресурсы первого и второго вида будут использоваться полностью, х₃ = х₄ = 0. По ресурсу третьего вида будет остаток х₅ = 100 кг. Прибыль, которую получит предприятие от реализации изделий, составит f = 13200 (д.ед.).

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

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