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

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

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

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

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

2x1+x2 Симплексный метод решения задачи линейного - student2.ru 400

3x1+4x2 Симплексный метод решения задачи линейного - student2.ru 900

X1+3x2 Симплексный метод решения задачи линейного - student2.ru 600

X1 Симплексный метод решения задачи линейного - student2.ru 0,x2 Симплексный метод решения задачи линейного - student2.ru 0

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

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

2x1+x2+x3=400

3x1+4x2+x4=900 (1.23)

X1+3x2+ x5=600

X1 Симплексный метод решения задачи линейного - student2.ru 0,x2 Симплексный метод решения задачи линейного - student2.ru 0, x3 Симплексный метод решения задачи линейного - student2.ru 0,x4 Симплексный метод решения задачи линейного - student2.ru 0,x5 Симплексный метод решения задачи линейного - student2.ru 0 (1.24)

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

f - 60x1 – 40 x2= 0

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

Пусть переменные х1, х2, входящие в функцию f, будут свободными, а переменные х3, х4, х5 – базисными. Базисные переменные выразятся через свободные следующим образом:

(1.25)

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

x1 = x2 = 0; x3 = 400; x4 = 900; x5 = 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  

ñ

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

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

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

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

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

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

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

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

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

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

aij A

В а*

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

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

aij´ = aij-(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  

ñ

Из полученной симплексной таблицы можно записать второе опорное решение. Переменные х2, х3 являются свободными и равны нулю: х2 = х3 = 0. Базисные переменные: x1 = 200; х4 = 300; х5 = 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 все элементы положительны, что означает, что полученное опорное решение является оптимальным. Предприятие получит максимальную прибыль от реализации выпускаемых изделий при выпуске х1 = 140 ед. изделия А, х2 = 120 ед. изделия В. При этом ресурсы первого и второго вида будут использоваться полностью, х3 = х4 = 0. По ресурсу третьего вида будет остаток х5 = 100 кг. Прибыль, которую получит предприятие от реализации изделий, составит f = 13200 (д.ед.).

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

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

Наши рекомендации