Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Симплекс-метод.
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = - 3x1 + 6x2 при следующих условиях-ограничений.
5x1 - 2x2≤4
- x1 + 2x2≤4
x1 + x2≥4
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус.
5x1-2x2 + 1x3 + 0x4 + 0x5 = 4
-1x1 + 2x2 + 0x3 + 1x4 + 0x5 = 4
1x1 + 1x2 + 0x3 + 0x4-1x5 = 4
Введем искусственные переменные x: в 3-м равенстве вводим переменную x6;
5x1-2x2 + 1x3 + 0x4 + 0x5 + 0x6 = 4
-1x1 + 2x2 + 0x3 + 1x4 + 0x5 + 0x6 = 4
1x1 + 1x2 + 0x3 + 0x4-1x5 + 1x6 = 4
Для постановки задачи на минимум целевую функцию запишем так:
F(X) = -3x1+6x2+Mx6 → min
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x6 = 4-x1-x2+x5
которые подставим в целевую функцию:
F(X) = -3x1 + 6x2 + M(4-x1-x2+x5) → min
или
F(X) = (-3-M)x1+(6-M)x2+(M)x5+(4M) → min
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных:
x3, x4, x6,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,4,4,0,4)
Базисное решение называется допустимым, если оно неотрицательно.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x3 |
4 |
5 |
-2 |
1 |
0 |
0 |
0 |
|
x4 |
4 |
-1 |
2 |
0 |
1 |
0 |
0 |
|
x6 |
4 |
1 |
1 |
0 |
0 |
-1 |
1 |
|
F(X0) |
4M |
3+M |
-6+M |
0 |
0 |
-M |
0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент .
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (4 : 5 , - , 4 : 1 ) = 4/5
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
min |
|
x3 |
4 |
5 |
-2 |
1 |
0 |
0 |
0 |
4/5 |
|
x4 |
4 |
-1 |
2 |
0 |
1 |
0 |
0 |
- |
|
x6 |
4 |
1 |
1 |
0 |
0 |
-1 |
1 |
4 |
|
F(X1) |
4M |
3+M |
-6+M |
0 |
0 |
-M |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x3 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=5
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (5), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
|
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
|
4 : 5 |
5 : 5 |
-2 : 5 |
1 : 5 |
0 : 5 |
0 : 5 |
0 : 5 |
|
4-(4 • -1):5 |
-1-(5 • -1):5 |
2-(-2 • -1):5 |
0-(1 • -1):5 |
1-(0 • -1):5 |
0-(0 • -1):5 |
0-(0 • -1):5 |
|
4-(4 • 1):5 |
1-(5 • 1):5 |
1-(-2 • 1):5 |
0-(1 • 1):5 |
0-(0 • 1):5 |
-1-(0 • 1):5 |
1-(0 • 1):5 |
|
(0)-(4 • (3+M)):5 |
(3+M)-(5 • (3+M)):5 |
(-6+M)-(-2 • (3+M)):5 |
(0)-(1 • (3+M)):5 |
(0)-(0 • (3+M)):5 |
(-M)-(0 • (3+M)):5 |
(0)-(0 • (3+M)):5 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
4/5 |
1 |
-2/5 |
1/5 |
0 |
0 |
0 |
|
x4 |
44/5 |
0 |
13/5 |
1/5 |
1 |
0 |
0 |
|
x6 |
31/5 |
0 |
12/5 |
-1/5 |
0 |
-1 |
1 |
|
F(X1) |
-22/5+31/5M |
0 |
-44/5+12/5M |
-3/5-M |
0 |
-M |
0 |
Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент .
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (- , 44/5 : 13/5 , 31/5 : 12/5 ) = 22/7
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (12/5) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
min |
|
x1 |
4/5 |
1 |
-2/5 |
1/5 |
0 |
0 |
0 |
- |
|
x4 |
44/5 |
0 |
13/5 |
1/5 |
1 |
0 |
0 |
3 |
|
x6 |
31/5 |
0 |
12/5 |
-1/5 |
0 |
-1 |
1 |
22/7 |
|
F(X2) |
-22/5+31/5M |
0 |
-44/5+12/5M |
-3/5-M |
0 |
-M |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x6 в план 2 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=12/5
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
|
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
|
4/5-(31/5 • -2/5):12/5 |
1-(0 • -2/5):12/5 |
-2/5-(12/5 • -2/5):12/5 |
1/5-(-1/5 • -2/5):12/5 |
0-(0 • -2/5):12/5 |
0-(-1 • -2/5):12/5 |
0-(1 • -2/5):12/5 |
|
44/5-(31/5 • 13/5):12/5 |
0-(0 • 13/5):12/5 |
13/5-(12/5 • 13/5):12/5 |
1/5-(-1/5 • 13/5):12/5 |
1-(0 • 13/5):12/5 |
0-(-1 • 13/5):12/5 |
0-(1 • 13/5):12/5 |
|
31/5 : 12/5 |
0 : 12/5 |
12/5 : 12/5 |
-1/5 : 12/5 |
0 : 12/5 |
-1 : 12/5 |
1 : 12/5 |
|
(0)-(31/5 • (-44/5+12/5M)):12/5 |
(0)-(0 • (-44/5+12/5M)):12/5 |
(-44/5+12/5M)-(12/5 • (-44/5+12/5M)):12/5 |
(-3/5-M)-(-1/5 • (-44/5+12/5M)):12/5 |
(0)-(0 • (-44/5+12/5M)):12/5 |
(-M)-(-1 • (-44/5+12/5M)):12/5 |
(0)-(1 • (-44/5+12/5M)):12/5 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
15/7 |
1 |
0 |
1/7 |
0 |
-2/7 |
2/7 |
|
x4 |
11/7 |
0 |
0 |
3/7 |
1 |
11/7 |
-11/7 |
|
x2 |
22/7 |
0 |
1 |
-1/7 |
0 |
-5/7 |
5/7 |
|
F(X2) |
84/7 |
0 |
0 |
-12/7 |
0 |
-33/7 |
33/7-M |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
15/7 |
1 |
0 |
1/7 |
0 |
-2/7 |
2/7 |
|
x4 |
11/7 |
0 |
0 |
3/7 |
1 |
11/7 |
-11/7 |
|
x2 |
22/7 |
0 |
1 |
-1/7 |
0 |
-5/7 |
5/7 |
|
F(X3) |
84/7 |
0 |
0 |
-12/7 |
0 |
-33/7 |
33/7-M |
Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.
Оптимальный план можно записать так:
x1 = 15/7
x2 = 22/7
F(X) = -3•15/7 + 6•22/7 = 84/7
Анализ оптимального плана.
В оптимальный план вошла дополнительная переменная x4. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 2-го вида в количестве 11/7
Значение 0 в столбце x1 означает, что использование x1 - выгодно.
Значение 0 в столбце x2 означает, что использование x2 - выгодно.
Значение -12/7 в столбце x3 означает, что теневая цена (двойственная оценка) равна -12/7.
Значение -33/7 в столбце x5 означает, что теневая цена (двойственная оценка) равна -33/7.
Значение 33/7-1M в столбце x6 означает, что теневая цена (двойственная оценка) равна 33/7-1M.
Ответы на вопросы преподавателя:
1. По какому методу пересчитываются симплекс-таблицы?
Используется правило прямоугольника (метод жордановских преобразований).
2. Обязательно ли каждый раз выбирать максимальное значение из индексной строки?
Можно не выбирать, но это может привести к зацикливанию алгоритма.
3. В индексной строке в n-ом столбце нулевое значение. Что это означает?
Нулевые значения должны соответствовать переменным, вошедшим в базис. Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов.
Свободную переменную, соответствующую указанному столбцу, можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.