Симплекс-метод
Определим минимальное значение целевой функции F(X) = - 2x2 при следующих условиях-ограничениях:- x1 + 3x2 ≤ 9
x1 – x2 ≤ 4
x1 + x2 ≤ 5
2x1 + 3x2 ≥ 6
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
-1x1 + 3x2 + 1S1 + 0S2 + 0S3 + 0S4 = 9
1x1 – 1x2 + 0S1 + 1S2 + 0S3 + 0S4 = 4
1x1 + 1x2 + 0S1 + 0S2 + 1S3 + 0S4 = 5
2x1 + 3x2 + 0S1 + 0S2 + 0S3 – 1S4 = 6
Введем искусственные переменные x: в 4-м равенстве вводим переменную S5;
-1x1 + 3x2 + 1S1 + 0S2 + 0S3 + 0S4 + 0S5 = 9
1x1-1x2 + 0S1 + 1S2 + 0S3 + 0S4 + 0S5 = 4
1x1 + 1x2 + 0S1 + 0S2 + 1S3 + 0S4 + 0S5 = 5
2x1 + 3x2 + 0S1 + 0S2 + 0S3-1S4 + 1S5 = 6
Для постановки задачи на минимум целевую функцию запишем так:
F(X) = -2x2+M•S5 → min
Из уравнений выражаем искусственные переменные:
S5 = 6-2x1-3x2+S4
которые подставим в целевую функцию:
F(X) = -2Mx1+(-2-3M)x2+ M•S4+6M → min
Матрица коэффициентов A = aij этой системы уравнений имеет вид:
| -1 | 3 | 1 | 0 | 0 | 0 | 0 |
| 1 | -1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| 2 | 3 | 0 | 0 | 0 | -1 | 1 |
Решим систему уравнений относительно базисных переменных:
S1, S2, S3, S5,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0, 0 ,9, 4, 5, 0, 6)
| Базис | B | x1 | x2 | S1 | S2 | S3 | S4 | S5 |
| S1 | 9 | -1 | 3 | 1 | 0 | 0 | 0 | 0 |
| S2 | 4 | 1 | -1 | 0 | 1 | 0 | 0 | 0 |
| S3 | 5 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| S5 | 6 | 2 | 3 | 0 | 0 | 0 | -1 | 1 |
| F(X0) | 6M | 2M | 2+3M | 0 | 0 | 0 | -1M | 0 |
Переходим к основному алгоритму симплекс-метода.
Нулевая (начальная) "Итерация".
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент .
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
Следовательно, 4-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | B | x1 | x2 | S1 | S2 | S3 | S4 | S5 | min |
| S1 | 9 | -1 | 3 | 1 | 0 | 0 | 0 | 0 | 3 |
| S2 | 4 | 1 | -1 | 0 | 1 | 0 | 0 | 0 | - |
| S3 | 5 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 5 |
| S5 | 6 | 2 | 3 | 0 | 0 | 0 | -1 | 1 | 2 |
| F(X1) | 6M | 2M | 2+3M | 0 | 0 | 0 | -1M | 0 | 0 |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | S1 | S2 | S3 | S4 | S5 |
| S1 | 3 | -3 | 0 | 1 | 0 | 0 | 1 | -1 |
| S2 | 6 | 12/3 | 0 | 0 | 1 | 0 | -1/3 | 1/3 |
| S3 | 3 | 1/3 | 0 | 0 | 0 | 1 | 1/3 | -1/3 |
| x2 | 2 | 2/3 | 1 | 0 | 0 | 0 | -1/3 | 1/3 |
| F(X1) | -4 | -11/3 | 0 | 0 | 0 | 0 | 2/3 | -2/3-1M |
Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной S4, так как это наибольший коэффициент .
Вычислим значения Di по строкам как частное от деления: bi / ai6
и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | B | x1 | x2 | S1 | S2 | S3 | S4 | S5 | min |
| S1 | 3 | -3 | 0 | 1 | 0 | 0 | 1 | -1 | 3 |
| S2 | 6 | 12/3 | 0 | 0 | 1 | 0 | -1/3 | 1/3 | - |
| S3 | 3 | 1/3 | 0 | 0 | 0 | 1 | 1/3 | -1/3 | 9 |
| x2 | 2 | 2/3 | 1 | 0 | 0 | 0 | -1/3 | 1/3 | - |
| F(X2) | -4 | -11/3 | 0 | 0 | 0 | 0 | 2/3 | -2/3-1M | 0 |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | S1 | S2 | S3 | S4 | S5 |
| S4 | 3 | -3 | 0 | 1 | 0 | 0 | 1 | -1 |
| S2 | 7 | 2/3 | 0 | 1/3 | 1 | 0 | 0 | 0 |
| S3 | 2 | 11/3 | 0 | -1/3 | 0 | 1 | 0 | 0 |
| x2 | 3 | -1/3 | 1 | 1/3 | 0 | 0 | 0 | 0 |
| F(X2) | -6 | 2/3 | 0 | -2/3 | 0 | 0 | 0 | -1M |
Итерация №2.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент .
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (11/3) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | B | x1 | x2 | S1 | S2 | S3 | S4 | S5 | min |
| S4 | 3 | -3 | 0 | 1 | 0 | 0 | 1 | -1 | - |
| S2 | 7 | 2/3 | 0 | 1/3 | 1 | 0 | 0 | 0 | 101/2 |
| S3 | 2 | 11/3 | 0 | -1/3 | 0 | 1 | 0 | 0 | 11/2 |
| x2 | 3 | -1/3 | 1 | 1/3 | 0 | 0 | 0 | 0 | - |
| F(X3) | -6 | 2/3 | 0 | -2/3 | 0 | 0 | 0 | -1M | 0 |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | S1 | S2 | S3 | S4 | S5 |
| S4 | 71/2 | 0 | 0 | 1/4 | 0 | 21/4 | 1 | -1 |
| S2 | 6 | 0 | 0 | 1/2 | 1 | -1/2 | 0 | 0 |
| x1 | 11/2 | 1 | 0 | -1/4 | 0 | 3/4 | 0 | 0 |
| x2 | 31/2 | 0 | 1 | 1/4 | 0 | 1/4 | 0 | 0 |
| F(X3) | -7 | 0 | 0 | -1/2 | 0 | -1/2 | 0 | -1M |
Конец итераций: индексная строка не содержит положительных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
| Базис | B | x1 | x2 | S1 | S2 | S3 | S4 | S5 |
| S4 | 71/2 | 0 | 0 | 1/4 | 0 | 21/4 | 1 | -1 |
| S2 | 6 | 0 | 0 | 1/2 | 1 | -1/2 | 0 | 0 |
| x1 | 11/2 | 1 | 0 | -1/4 | 0 | 3/4 | 0 | 0 |
| x2 | 31/2 | 0 | 1 | 1/4 | 0 | 1/4 | 0 | 0 |
| F(X4) | -7 | 0 | 0 | -1/2 | 0 | -1/2 | 0 | -1M |
Оптимальный план можно записать так:
S4 = 71/2
S2 = 6
x1 = 11/2
x2 = 31/2
F(X) = 0•11/2 - 2•31/2 = -7
Помощь студентам. Решение задач - математика, физика, химия, ТОЭ, механика.
ОтветитьУдалитьскайп-репетитор.рф
Решение задач по физике, математике, математическому анализу, теории вероятности, программированию, химии, ТОЭ, электротехнике, сопромату, теоретической механике.
MOCKBA3452061.narod.ru
Симплекс метод легко решить только с репетитором Алексеем Учителем!
ОтветитьУдалитьрепетитор-по-математике.рф
Пусть ABCD-равнобокая трапеция, с основаниями AD и BC. Диагональ АС= основанию АD. Углы ВАС=АDC=ACD (так как треугольник АСD равнобедренный).
УдалитьТрапеция. Свойства трапеции, диагональ равнобедренной трапеции с основаниями 4 и 16 образует с основанием угол 45 градусов. найдите площадь трапеции. В равнобокий трапеции АВСD с основаниями ВС=9 и АD=15 диагональ АС перпендикулярна боковой стороне СD. Найти высоту трапеции, диагональ и косинус большего угла между диагоналями. Разбор III этапа всероссийской олимпиады школьников по физике. Теоретический тур.