Консультация № 172907
05.10.2009, 03:12
0.00 руб.
0 1 1
Здравствуйте, господа!) Вобщем надо решить задачку по линейному программированию алгебраическим симплексным методом. Я уже запарился, не могу понять как решить. После графического решения получил: Х1=16; Х2=9.

F=5X1+3X2 → max

при условиях

6X1-5X2 ≥17;

X1+2X2 ≤34;

-4X1+9X2 ≥17;

X1≥0; X2 ≥0.

Обсуждение

Неизвестный
05.10.2009, 19:05
общий
это ответ
Здравствуйте, Глушков Артем.
Задачу можно решить, используя так называемые симплекс-таблицы. Преимущество этого метода заключается в том, что он строго алгоритмизирован (т.е. действуй как написано и не ошибешься).

Однако здесь используем другой метод, чтобы просто разобраться, в чем, собственно заключается суть симплекс-метода.

Путем добавления новых переменных, приведем систему ограничений к системе уравнений.
6X1-5X2-x3=17;
X1+2X2+x4=34;
-4X1+9X2-x5=17;
Xi≥0 (i=1...5).

Данная система уравнений совместна, т.к. ранг матрицы системы
6 -5 1 0 0
1 2 0 1 0
-4 9 0 0 1

равен рангу расширенной матрицы системы
6 -5 1 0 0 17
1 2 0 1 0 34
-4 9 0 0 1 17

и равен 3, т.к. из строк и столбцов каждой из данных матриц можно образовать неравный 0 определитель 3-го порядка
|6 -5 1|
|1 2 0| = 17[$8800$]0
|-4 9 0|

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

Поэтому выразим три любые переменные (скажем, X1, X2 и X3) через остальные (X4 и X5):
X1=16-(9/17)*X4-(2/17)*X5
X2=9-(4/17)*X4+(1/17)*X5
X3=34-2*X4-X5

Подставляя найденные значения для X1 и X2 в целевую функцию F=5X1+3X2, находим
F=107-(57/17)*X4-(7/17)*X5. (1)

Имеем следующее.
При X4=X5=0 F=107.
Далее, по условию, X4[$8805$]0 и X5[$8805$]0. Поэтому уменьшать X4 и X5 по сравнению с нулем мы не имеем право.
Увеличение же X4 и X5 приведет к непременному уменьшению значения целевой функции (1), т.к. коэффициенты в целевой функции при указанных переменных отрицательны.
Поэтому не существует таких значений переменных X4 и X5, при которых при ограничениях X4[$8805$]0 и X5[$8805$]0 функция (1) принимает значения, большие 107 (при этом X4=X5=0 [$8658$] X1=16, X2=9).

Ответ: Fmax = 107 (X1=16, X2=9).

Приложение:
Пример применения симплекс таблиц можно посмотреть в http://www.snipetz.com/math/sysanalysys/line/03.htm, или, чем я лично пользуюсь,
П.Е. Данко, А.Г. Попов, Т.Я. Кожевникова Высшая математика в упражнениях и задачах (в 2-х частях, часть 1).
Форма ответа