Файл: Исследование операций и методы оптимизации Заданиевариант 2 Выполнена обучающимся группы о. Издтв 23. 1Б22.docx

Определим максимальное значение целевой функции Z(Y) = y₁+y₂ при следующих условиях-ограничений.
y₁+8000y₂≤1
6y₁+6000y₂≤1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
y₁+8000y₂+y₃ = 1
6y₁+6000y₂+y₄ = 1
Решим систему уравнений относительно базисных переменных: y₃, y₄
Полагая, что свободные переменные равны 0, получим первый опорный план:
Y0 = (0,0,1,1)

Базис	B	y1	y2	y3	y4
y3	1	1	8000	1	0
y4	1	6	6000	0	1
Z(Y0)	0	-1	-1	0	0

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной y₂, так как это наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i2
и из них выберем наименьшее:
min (1 : 8000 , 1 : 6000 ) = ¹/₈₀₀₀
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (8000) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	y1	y2	y3	y4	min
y3	1	1	8000	1	0	1/8000
y4	1	6	6000	0	1	1/6000
Z(Y1)	0	-1	-1	0	0

---

Формируем следующую часть симплексной таблицы. Вместо переменной y₃ в план 1 войдет переменная y₂.

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

Базис	B	y1	y2	y3	y4
y2	1/8000	1/8000	1	1/8000	0
y4	1/4	21/4	0	-3/4	1
Z(Y1)	1/8000	-7999/8000	0	1/8000	0

---

Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной y₁, так как это наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i1
и из них выберем наименьшее:
min (¹/₈₀₀₀ : ¹/₈₀₀₀ , ¹/₄ : 5¹/₄ ) = ¹/₂₁
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (5¹/₄) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	y1	y2	y3	y4	min
y2	1/8000	1/8000	1	1/8000	0	1
y4	1/4	21/4	0	-3/4	1	1/21
Z(Y2)	1/8000	-7999/8000	0	1/8000	0

Формируем следующую часть симплексной таблицы. Вместо переменной y₄ в план 2 войдет переменная y₁.

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

Базис	B	y1	y2	y3	y4
y2	1/8400	0	1	1/7000	-1/42000
y1	1/21	1	0	-1/7	4/21
Z(Y2)	401/8400	0	0	-999/7000	7999/42000

---

Итерация №2.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной y₃, так как это наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i3
и из них выберем наименьшее:
min (¹/₈₄₀₀ : ¹/₇₀₀₀ , - ) = ⁵/₆
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (¹/₇₀₀₀) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	y1	y2	y3	y4	min
y2	1/8400	0	1	1/7000	-1/42000	5/6
y1	1/21	1	0	-1/7	4/21	-
Z(Y3)	401/8400	0	0	-999/7000	7999/42000

Формируем следующую часть симплексной таблицы. Вместо переменной y₂ в план 3 войдет переменная y₃.

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

Базис	B	y1	y2	y3	y4
y3	5/6	0	7000	1	-1/6
y1	1/6	1	1000	0	1/6
Z(Y3)	1/6	0	999	0	1/6

---

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:

Базис	B	y1	y2	y3	y4
y3	5/6	0	7000	1	-1/6
y1	1/6	1	1000	0	1/6
Z(Y4)	1/6	0	999	0	1/6

Оптимальный план можно записать так:
y₁ = ¹/₆, y₂ = 0
Z(Y) = 1*¹/₆ + 1*0 = ¹/₆

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
x₁=0, x₂=¹/₆
Это же решение можно получить, применив теоремы двойственности.
Из теоремы двойственности следует, что X = C*A^-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

A = (A3, A1) =

1 1 0 6

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

D = A-1 =

1 -1/6 0 1/6

---