Найти максимум функции F(X)=2x1+4x2+6x3 при следующих ограничениях: -x1+x2+x3≥1 x1+x2+2x3≥1 x1≥0, x2≥0 x3≥0 Необходимо: а) решить задачу симплекс-методом (ПЗЛП); б) составить задачу, двойственную данной (ДЗЛП), и решить обе на компьютере; в) используя первую теорему двойственности, найти оптимум исходной задачи. (Решение → 19083)

Заказ №39105

Задание 3. Найти максимум функции F(X)=2x1+4x2+6x3 при следующих ограничениях: -x1+x2+x3≥1 x1+x2+2x3≥1 x1≥0, x2≥0 x3≥0 Необходимо: а) решить задачу симплекс-методом (ПЗЛП); б) составить задачу, двойственную данной (ДЗЛП), и решить обе на компьютере; в) используя первую теорему двойственности, найти оптимум исходной задачи.

Решение

а) Добавим дополнительные переменные в ограничения: -x1+x2+x3 -х4=1 x1+x2+2x3-х5=1 xi≥0, i=1..5 Получим первое базисное решение Вычтем из второго уравнения первое, умноженное на 2: -x1+x2+x3 -х4=1 3x1 –х2+2х4 -х5=-1 Разделим второе уравнение на -1: -x1+x2+x3 -х4=1 -3x1 +х2-2х4 +х5=1 Базисные переменные х3 и х5. Исключим из целевой функции переменную х3: F(X)=2x1+4x2+6(1+x1-x2+x4) =6+8х1-2х2+6х4 Окончательно получим: F(X)= 6+8х1-2х2+6х4max -x1+x2+x3 -х4=1 -3x1 +х2-2х4 +х5=1 xi≥0, i=1..5 Составляем симплекс-таблицу: сi Базисные переменные 8 -2 0 6 0 х1 х2 х3 х4 х5 bi 0 x3 -1 1 1 -1 0 1 0 x5 -3 1 0 0 1 1 -8 2 0 -6 0 6 В индексной строке две отрицательные оценки: –8, –6. Выбираем в качестве разрешающего столбец, соответствующий х1, т.к. оценка этого столбца (–8) наименьшая отрицательная оценка. В столбце х1 нет положительных коэффициентов, задача не имеет решения. б) Составим двойственную задачу. Запишем исходную задачу в виде: F(X)=2x1+4x2+6x3 при следующих ограничениях: x1-x2-x3-1 -x1-x2-2x3-1 x1≥0, x2≥0 x3≥0 Матрица коэффициентов:                              1 2 1 1 1 1 1 1 2 1 1 1 Т Тогда двойственная к ней имеет вид: G=-y1-y2min y1-y2≥2 -y1-y2≥4 -y1-2y2≥6 y1,y2≥0 Решим прямую задачу на компьютере. Вводим исходные данные: