Пример использования симплекс-метода

Размещено на http://www.allbest.ru/

Примеры использования симплекс-метода

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

F(X) = x1 + 2x2

при следующих условиях ограничений.

- 2x1 + x2?2 x1 + x2?3 x1 - 2x2?2.

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (?) вводим базисную переменную x3 со знаком минус. В 2-м неравенстве смысла (?) вводим базисную переменную x4 со знаком минус. В 3-м неравенстве смысла (?) вводим базисную переменную x5.

-2x1 + 1x2-1x3 + 0x4 + 0x5 = 2 1x1 + 1x2 + 0x3-1x4 + 0x5 = 3 1x1-2x2 + 0x3 + 0x4 + 1x5 = 2

Введем искусственные переменные x: в 1-м равенстве вводим переменную x6; в 2-м равенстве вводим переменную x7;

-2x1 + 1x2-1x3 + 0x4 + 0x5 + 1x6 + 0x7 = 2 1x1 + 1x2 + 0x3-1x4 + 0x5 + 0x6 + 1x7 = 3 1x1-2x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 = 2

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

F(X) = x1+2x2+Mx6+Mx7 > min

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

Из уравнений выражаем искусственные переменные:

x6 = 2+2x1-x2+x3 x7 = 3-x1-x2+x4

которые подставим в целевую функцию:

F(X) = x1 + 2x2 + M(2+2x1-x2+x3) + M(3-x1-x2+x4) > min или F(X) = (1+M)x1+(2-2M)x2+(M)x3+(M)x4+(5M) > min

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана. Решим систему уравнений относительно базисных переменных: x6, x7, x5.

Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,2,2,3)

Базисное решение называется допустимым, если оно неотрицательно.

линейный программирование симплексный переменная

Переходим к основному алгоритму симплекс-метода. Итерация №0.

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

2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент.

3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее:

min (2 : 1 , 3 : 1 , - ) = 2

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. Вместо переменной x6 в план 1 войдет переменная x2.

Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=1. На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x2 плана 1 записываем нули.

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

РЭ. НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

Получаем новую симплекс-таблицу

Итерация №1.

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

2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент.

3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее:

min (-, 1 : 3, - ) = 1/3

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x7 в план 2 войдет переменная x1. Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x7 плана 1 на разрешающий элемент РЭ=3

На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x1 плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы

Получаем новую симплекс-таблицу:

Размещено на Allbest.ru