Лабораторная работа №5. Двойственность задач линейного программирования.

12

Построить двойственную задачу линейного программирования. Решить исходную и двойственную задачу с использованием пакета MS Excel.

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

Определим минимальное значение целевой функции F(X) = 8x1 + 6x2 + 5x3 при следующих условиях-ограничений.

2x1 + x2 + 3x3≥4

3x1 + x2 + 2x3≥5

4x1 + 5x2 + x3≥3

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

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

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

4x1 + 5x2 + 1x3 + 0x4 + 0x5-1x6 = 3

Умножим все строки на (-1) и будем искать первоначальный опорный план.

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

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

-4x1-5x2-1x3 + 0x4 + 0x5 + 1x6 = -3

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

Решим систему уравнений относительно базисных переменных:

x4, x5, x6,

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

X1 = (0,0,0,-4,-5,-3)

Базис B x1 x2 x3 x4 x5 x6
x4 -4 -2 -1 -3
x5 -5 -3 -1 -2
x6 -3 -4 -5 -1
F(X0)

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-2).

Базис B x1 x2 x3 x4 x5 x6
x4 -4 -2 -1 -3
x5 -5 -3 -1 -2
x6 -3 -4 -5 -1
F(X0)
θ 8 : (-3) = -22/3 6 : (-1) = -6 5 : (-2) = -21/2 - - -

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис B x1 x2 x3 x4 x5 x6
x4 31/2 21/2 1/2 -11/2
x3 21/2 11/2 1/2 -1/2
x6 -1/2 -21/2 -41/2 -1/2
F(X0) -121/2 1/2 31/2 21/2



План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1/2).

Базис B x1 x2 x3 x4 x5 x6
x4 31/2 21/2 1/2 -11/2
x3 21/2 11/2 1/2 -1/2
x6 -1/2 -21/2 -41/2 -1/2
F(X0) -121/2 1/2 31/2 21/2
θ 1/2 : (-21/2) = -1/5 31/2 : (-41/2) = -7/9 - - 21/2 : (-1/2) = -5 -

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис B x1 x2 x3 x4 x5 x6
x4 -3
x3 -1
x5 -2
F(X1) -15 -12 -19

В базисном столбце все элементы положительные.

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

Итерация №0.

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai2

и из них выберем наименьшее:

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

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

Базис B x1 x2 x3 x4 x5 x6 min
x4 -3 5/14
x3 -1 3/5
x5 -2 1/9
F(X1) -15 -12 -19

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

Базис B x1 x2 x3 x4 x5 x6
x4 34/9 22/9 -15/9 1/9
x3 24/9 12/9 -5/9 1/9
x2 1/9 5/9 1/9 -2/9
F(X1) -128/9 -14/9 21/9 7/9

Итерация №1.

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai1

и из них выберем наименьшее:

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

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

Базис B x1 x2 x3 x4 x5 x6 min
x4 34/9 22/9 -15/9 1/9 111/20
x3 24/9 12/9 -5/9 1/9
x2 1/9 5/9 1/9 -2/9 1/5
F(X2) -128/9 -14/9 21/9 7/9

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

Базис B x1 x2 x3 x4 x5 x6
x4 -4 -2
x3 21/5 -21/5 -4/5 3/5
x1 1/5 14/5 1/5 -2/5
F(X2) -123/5 23/5 22/5 1/5

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

Окончательный вариант симплекс-таблицы:

Базис B x1 x2 x3 x4 x5 x6
x4 -4 -2
x3 21/5 -21/5 -4/5 3/5
x1 1/5 14/5 1/5 -2/5
F(X3) -123/5 23/5 22/5 1/5

Оптимальный план можно записать так:

x4 = 3

x3 = 21/5

x1 = 1/5

F(X) = 5•21/5 + 8•1/5 = 123/5

Составим двойственную задачу к прямой задаче.

2y1 + 3y2 + 4y3≤8

y1 + y2 + 5y3≤6

3y1 + 2y2 + y3≤5

4y1 + 5y2 + 3y3 → max

y1 ≥ 0

y2 ≥ 0

y3 ≥ 0

Решение двойственной задачи дает оптимальную систему оценок ресурсов.

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.

Из теоремы двойственности следует, что Y = C*A-1.

Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных.

Тогда Y = C*A-1 =

Оптимальный план двойственной задачи равен:

y1 = 0

y2 = 22/5

y3 = 1/5

Z(Y) = 4*0+5*22/5+3*1/5 = 123/5


6900745267687741.html
6900789986207043.html
    PR.RU™