4. Знайти оптимальне рішення злп на першому етапі двохетапного симплекс-метода.

mах Z=X1 +2Х2-2Х3

при 7X1 + 4Х2+Х3 22

4Х1 + 4Х2  4

2Х1 + Х2=14

X1,X2,Х3 0

Решим прямую задачу линейного программирования симплекс-методом.. Определим максимальное значение целевой функции F(X) = x₁ + 2x₂ + 2x₃ при следующих условиях-ограничений. 7x₁ + 4x₂ + x₃≥22 4x₁ + 4x₂≥4 2x₁ + x₂=14 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (≥) вводим базисную переменную x₄ со знаком минус. В 2-м неравенстве смысла (≥) вводим базисную переменную x₅ со знаком минус. 7x₁ + 4x₂ + 1x₃-1x₄ + 0x₅ = 22 4x₁ + 4x₂ + 0x₃ + 0x₄-1x₅ = 4 2x₁ + 1x₂ + 0x₃ + 0x₄ + 0x₅ = 14 Введем искусственные переменные x: в 1-м равенстве вводим переменную x₆; в 2-м равенстве вводим переменную x₇; в 3-м равенстве вводим переменную x₈; 7x₁ + 4x₂ + 1x₃-1x₄ + 0x₅ + 1x₆ + 0x₇ + 0x₈ = 22 4x₁ + 4x₂ + 0x₃ + 0x₄-1x₅ + 0x₆ + 1x₇ + 0x₈ = 4 2x₁ + 1x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ + 1x₈ = 14 Для постановки задачи на максимум целевую функцию запишем так: F(X) = - Mx₆ - Mx₇ - Mx₈ → max Полученный базис называется искусственным, а метод решения называется методом искусственного базиса. Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения. Из уравнений выражаем искусственные переменные: x₆ = 22-7x₁-4x₂-x₃+x₄ x₇ = 4-4x₁-4x₂+x₅ x₈ = 14-2x₁-x₂ которые подставим в целевую функцию: F(X) = - M(22-7x₁-4x₂-x₃+x₄) - M(4-4x₁-4x₂+x₅) - M(14-2x₁-x₂) → max или F(X) = (13M)x₁+(9M)x₂+(M)x₃+(-M)x₄+(-M)x₅+(-40M) → max Введем новую переменную x₀ = 13x₁ + 9x₂ + x₃. Выразим базисные переменные <6, 7, 8> через небазисные. x₀ = -40+13x₁+9x₂+x₃-x₄-x₅ x₆ = 22-7x₁-4x₂-x₃+x₄ x₇ = 4-4x₁-4x₂+x₅ x₈ = 14-2x₁-x₂ Переходим к основному алгоритму симплекс-метода. Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x₀. 1. Проверка критерия оптимальности. В выражении для x₀ присутствуют отрицательные элементы. Следовательно, текущий план неоптимален 2. Определение новой базисной переменной. max(13,9,1,-1,-1,0,0,0) = 13 x₀ = -40+13x₁+9x₂+x₃-x₄-x₅ x₆ = 22-7x₁-4x₂-x₃+x₄ x₇ = 4-4x₁-4x₂+x₅ x₈ = 14-2x₁-x₂ В качестве новой переменной выбираем x₁. 3. Определение новой свободной переменной. Вычислим значения D_i по всем уравнениям для этой переменной: b_i / a_i1 и из них выберем наименьшее: min (22 : 7 , 4 : 4 , 14 : 2 ) = 1 Вместо переменной x₇ в план войдет переменная x₁. 4. Пересчет всех уравнений. Выразим переменную x₁ через x₇ x₁ = 1-x₂+¹/₄x₅^-1/₄x₇ и подставим во все выражения. x₀ = -40+13(1-x₂+¹/₄x₅^-1/₄x₇)+9x₂+x₃-x₄-x₅ x₆ = 22-7(1-x₂+¹/₄x₅^-1/₄x₇)-4x₂-x₃+x₄ x₈ = 14-2(1-x₂+¹/₄x₅^-1/₄x₇)-x₂ После приведения всех подобных, получаем новую систему, эквивалентную прежней: x₀ = -27-4x₂+x₃-x₄+⁹/₄x₅-¹³/₄x₇ x₆ = 15+3x₂-x₃+x₄-⁷/₄x₅+⁷/₄x₇ x₁ = 1-x₂+¹/₄x₅-¹/₄x₇ x₈ = 12+x₂-¹/₂x₅+¹/₂x₇ Полагая небазисные переменные x = (6, 1, 8) равными нулю, получим новый допустимый вектор и значение целевой функции: x = (0, 4, -1, 1, ^-9/₄, 0, ¹³/₄, 0), x₀ = -27 1. Проверка критерия оптимальности. В выражении для x₀ присутствуют отрицательные элементы. Следовательно, текущий план неоптимален 2. Определение новой базисной переменной. max(0,-4,1,-1,⁹/₄,0,^-13/₄,0) = ⁹/₄ x₀ = -27-4x₂+x₃-x₄+⁹/₄x₅-¹³/₄x₇ x₆ = 15+3x₂-x₃+x₄-⁷/₄x₅+⁷/₄x₇ x₁ = 1-x₂+¹/₄x₅-¹/₄x₇ x₈ = 12+x₂-¹/₂x₅+¹/₂x₇ В качестве новой переменной выбираем x₅. 3. Определение новой свободной переменной. Вычислим значения D_i по всем уравнениям для этой переменной: b_i / a_i5 и из них выберем наименьшее: min (15 : 1³/₄ , - , 12 : ¹/₂ ) = 8⁴/₇ Вместо переменной x₆ в план войдет переменная x₅. 4. Пересчет всех уравнений. Выразим переменную x₅ через x₆ x₅ = ⁶⁰/₇+¹²/₇x₂^-4/₇x₃+⁴/₇x₄^-4/₇x₆+x₇ и подставим во все выражения. x₀ = -27-4x₂+x₃-x₄+2¹/₄(⁶⁰/₇+¹²/₇x₂^-4/₇x₃+⁴/₇x₄^-4/₇x₆+x₇)-3¹/₄x₇ x₁ = 1-x₂+¹/₄(⁶⁰/₇+¹²/₇x₂^-4/₇x₃+⁴/₇x₄^-4/₇x₆+x₇)^-1/₄x₇ x₈ = 12+x₂^-1/₂(⁶⁰/₇+¹²/₇x₂^-4/₇x₃+⁴/₇x₄^-4/₇x₆+x₇)+¹/₂x₇ После приведения всех подобных, получаем новую систему, эквивалентную прежней: x₀ = -⁵⁴/₇-¹/₇x₂-²/₇x₃+²/₇x₄-⁹/₇x₆-x₇ x₅ = ⁶⁰/₇+¹²/₇x₂-⁴/₇x₃+⁴/₇x₄-⁴/₇x₆+x₇ x₁ = ²²/₇-⁴/₇x₂-¹/₇x₃+¹/₇x₄-¹/₇x₆ x₈ = ⁵⁴/₇+¹/₇x₂+²/₇x₃-²/₇x₄+²/₇x₆ Полагая небазисные переменные x = (5, 1, 8) равными нулю, получим новый допустимый вектор и значение целевой функции: x = (0, ¹/₇, ²/₇, ^-2/₇, 0, ⁹/₇, 1, 0), x₀ = ^-54/₇ 1. Проверка критерия оптимальности. В выражении для x₀ присутствуют отрицательные элементы. Следовательно, текущий план неоптимален 2. Определение новой базисной переменной. max(0,^-1/₇,^-2/₇,²/₇,0,^-9/₇,-1,0) = ²/₇ x₀ = -⁵⁴/₇-¹/₇x₂-²/₇x₃+²/₇x₄-⁹/₇x₆-x₇ x₅ = ⁶⁰/₇+¹²/₇x₂-⁴/₇x₃+⁴/₇x₄-⁴/₇x₆+x₇ x₁ = ²²/₇-⁴/₇x₂-¹/₇x₃+¹/₇x₄-¹/₇x₆ x₈ = ⁵⁴/₇+¹/₇x₂+²/₇x₃-²/₇x₄+²/₇x₆ В качестве новой переменной выбираем x₄. 3. Определение новой свободной переменной. Вычислим значения D_i по всем уравнениям для этой переменной: b_i / a_i4 и из них выберем наименьшее: min (- , - , 7⁵/₇ : ²/₇ ) = 27 Вместо переменной x₈ в план войдет переменная x₄. 4. Пересчет всех уравнений. Выразим переменную x₄ через x₈ x₄ = 27+¹/₂x₂+x₃+x₆^-7/₂x₈ и подставим во все выражения. x₀ = -7⁵/₇^-1/₇x₂^-2/₇x₃+²/₇(27+¹/₂x₂+x₃+x₆^-7/₂x₈)-1²/₇x₆-x₇ x₅ = 8⁴/₇+1⁵/₇x₂^-4/₇x₃+⁴/₇(27+¹/₂x₂+x₃+x₆^-7/₂x₈)^-4/₇x₆+x₇ x₁ = 3¹/₇^-4/₇x₂^-1/₇x₃+¹/₇(27+¹/₂x₂+x₃+x₆^-7/₂x₈)^-1/₇x₆ После приведения всех подобных, получаем новую систему, эквивалентную прежней: x₀ = 0-x₆-x₇-x₈ x₅ = 24+2x₂+x₇-2x₈ x₁ = 7-¹/₂x₂-¹/₂x₈ x₄ = 27+¹/₂x₂+x₃+x₆-⁷/₂x₈ Полагая небазисные переменные x = (5, 1, 4) равными нулю, получим новый допустимый вектор и значение целевой функции: x = (0, 0, 0, 0, 0, 1, 1, 1), x₀ = 0 Выражение для x₀ не содержит положительных элементов. Найден оптимальный план. x₀ = 0-x₆-x₇-x₈ x₅ = 24+2x₂+x₇-2x₈ x₁ = 7-¹/₂x₂-¹/₂x₈ x₄ = 27+¹/₂x₂+x₃+x₆-⁷/₂x₈ На этом первый этап симплекс-метода завершен. Переходим ко второму этапу. Удаляем переменные с искусственными переменными. x₅ = 24+2x₂ x₁ = 7-¹/₂x₂ x₄ = 27+¹/₂x₂+x₃ Выразим базисные переменные: x₁ = 7^-1/₂x₂ которые подставим в целевую функцию: F(X) = (7^-1/₂x₂) + 2x₂ + 2x₃ или F(X) = 7+³/₂x₂+2x₃ Получаем новую систему переменных. x₀ = 7+³/₂x₂+2x₃ x₅ = 24+2x₂ x₁ = 7-¹/₂x₂ x₄ = 27+¹/₂x₂+x₃ 1. Проверка критерия оптимальности. В выражении для x₀ присутствуют отрицательные элементы. Следовательно, текущий план неоптимален 2. Определение новой базисной переменной. max(0,³/₂,2,0,0) = ³/₂ x₀ = 7+³/₂x₂+2x₃ x₅ = 24+2x₂ x₁ = 7-¹/₂x₂ x₄ = 27+¹/₂x₂+x₃ В качестве новой переменной выбираем x₂. 3. Определение новой свободной переменной. Вычислим значения D_i по всем уравнениям для этой переменной: b_i / a_i2 и из них выберем наименьшее: min (- , 7 : ¹/₂ , - ) = 14 Вместо переменной x₁ в план войдет переменная x₂. 4. Пересчет всех уравнений. Выразим переменную x₂ через x₁ x₂ = 14-2x₁ и подставим во все выражения. x₀ = 7+1¹/₂(14-2x₁)+2x₃ x₅ = 24+2(14-2x₁) x₄ = 27+¹/₂(14-2x₁)+x₃ После приведения всех подобных, получаем новую систему, эквивалентную прежней: x₀ = 28-3x₁+2x₃ x₅ = 52-4x₁ x₂ = 14-2x₁ x₄ = 34-x₁+x₃ Полагая небазисные переменные x = (5, 2, 4) равными нулю, получим новый допустимый вектор и значение целевой функции: x = (3, 0, -2, 0, 0), x₀ = 28 Переменных для включения в новый базис не найдено. Окончательный вариант системы уравнений: x₀ = 28-3x₁+2x₃ x₅ = 52-4x₁ x₂ = 14-2x₁ x₄ = 34-x₁+x₃ Последняя строка содержит отрицательные элементы. Пространство допустимых решений неограниченно. Решения не существует.