Примеры решения задач к экзаменационному вопросу 20 (Примеры решения задач к экзаменационным вопросам)

Тема: Методы решения задачи линейного программированияПример №1Дано:f (X ) = 4 x 1 + x 2 → extr- x1 + x 2 ≤ 12 x1 + x 2 ≥ 4x1 , x 2 ≥ 0(1)(2)(3)Решить задачу графически и симплекс методом.Решение:а) Решим задачу графически.1. Для графического решения задачи построим множество допустимых решений, задаваемоеограничениями (1)-(3).Ограничение (1) в задаче определяется прямой − x1 + x 2 = 1 , проходящей через точки:x1x201−10Множество допустимых решений в задаче будет ограничено этой прямой и будет содержать точку(0, 0)T , так как при подстановке координат этой точки в ограничение (1) получается верноенеравенство: −0 + 0 ≤ 1 .Ограничение (2) в задаче определяется прямой 2x1 + x 2 = 4 , проходящей через точки:x102x240Множество допустимых решений в задаче будет ограничено этой прямой и НЕ будет содержатьточку (0, 0)T , так как при подстановке координат этой точки в ограничение (2) получаетсяневерное неравенство: 2 ⋅ 0 + 0 ≥ 4 .Ограничения (3) в задаче задают 1-ю четверть координатной плоскости.Множество допустимых решений включает все точки, в которых ограничения выполняютсяодновременно.

Отметим крайние точки получившегося множества: A, B.2. Построим градиент функции ∇f (X) = (4, 1)T в точке (0, 0)T .3. Построим линию уровня функции f (X) = C , проходящую через точку (0, 0)T . Для этого найдемзначение константы C, подставив координаты точки в целевую функцию: C = 4 ⋅ 0 + 0 = 0 , и затемпостроим прямую 4x1 + x 2 = 0 . Заметим, что построенная прямая перпендикулярна градиенту .Построенная линия уровня не имеет общих точек с множеством допустимых решений.

Используяпараллельный перенос, построим еще одну линию уровня функции, пересекающую множестводопустимых решений, и отметим ее ⊕ .4. Будем искать точку максимума функции как последнюю точку касания линии уровня имножества допустимых решений при параллельном переносе линии ⊕ в направлении градиентафункции. Как видно из чертежа, такой точки не существует, так как множество допустимыхрешений в направлении градиента неограниченное, следовательно, максимума в задаче нет.Будем искать точку минимума функции как последнюю точку касания линии уровня и множествадопустимых решений при параллельном переносе линии ⊕ в направлении, противоположномградиенту функции. Как видно из чертежа, это точка A = (1, 2)T (соответствующая линия уровняизображена штриховой линией).

Таким образом, получено решение задачи поиска минимумафункции:x1* = 1 ,x2* = 2f (X*min ) = 4 ⋅ 1 + 2 = 6 .б) Решим задачу симплекс-методом.Найдем максимум функции. Будем рассматривать задачу:f (X ) = 4 x 1 + x 2 → max- x1 + x 2 ≤ 12 x1 + x 2 ≥ 4x1 , x 2 ≥ 0Подготовим задачу к решению симплекс-методом:Перейдем от задачи в основной постановке к задаче в канонической:f (X ) = 4 x 1 + x 2 + 0 x 3 + 0 x 4 → max- x1 + x 2 + 1 x 3 + 0 x 4 = 12 x1 + x 2 + 0 x 3 - 1 x 4 = 4x1 , x 2 , x 3 , x 4 ≥ 0x 3 , x 4 - дополнительные переменные в задачеВыпишем столбцы при переменных в ограничениях:x1x2 − 1 21 1x3x4 1  00  −1Базис в задаче отсутствует, т.к.

среди выписанных столбцов нет достаточного количествабазисных (столбцов единичной матрицы (2 х 2)).Переходим к М-задаче. Введем во второе ограничение искусственную переменную x 5 ≥ 0 , тогдаполучим новую систему ограничений:- x1 + x 2 + 1 x 3 + 0 x 4 + 0 x 5 = 12 x1 + x 2 + 0 x 3 - 1 x 4 + 1 x 5 = 4x1 , x 2 , x 3 , x 4 , x 5 ≥ 0Выпишем столбцы при переменных в ограничениях:x1x2x3 − 1 21 1 1  0x4x50  −1 0  1Столбцы при переменных x 3 и x 5 образуют единичную матрицу (2 х 2), следовательно, найденначальный базис в задаче.Введем искусственную переменную x 5 в функцию, получим:f (X ) = 4 x 1 + x 2 + 0 x 3 + 0 x 4 - M x 5 → maxОкончательно получаем задачу, подготовленную к решению симплекс-методом:f (X ) = 4 x 1 + x 2 + 0 x 3 + 0 x 4 - M x 5 → max- x1 + x 2 + 1 x 3 + 0 x 4 + 0 x 5 = 12 x1 + x 2 + 0 x 3 - 1 x 4 + 1 x 5 = 4x1 , x 2 , x 3 , x 4 , x 5 ≥ 0Базисные переменные в задаче: в 1-м ограничении - x 3 ,во 2-м ограничении - x 5Начальное базисное решение:x1 = 0x2 = 0x3 =1x4 = 0x5 = 4КоэффициентпересчётаТаблица №14100-MCjCiБпБрx1x2x3x4x5ri0x31-11100-1-Mx54210-1120-M0∆2M+4M+1⊕ -столбец⊕ -строкаРазрешающийэлементБазисное решение, соответствующее таблице №1:x3 =1x1 = 0x2 = 0x4 = 0В исходных переменных x1 , x 2 это решение соответствует точке с координатами (0, 0) .x5 = 4Вычислим симплекс-разности для небазисных переменных: 0   − 1 ⋅   = 4 − (0 − 2M ) = 2M + 4∆1 = 4 − − M  2  0  1 ⋅   = 1 − (0 − M ) = M + 1∆ 2 = 1 −  − M  1 0  0 ⋅   = 0 − (0 + M ) = − M∆ 4 = 0 −  − M   − 1Т.к.

∆1 = max(∆ 1 , ∆ 2 , ∆ 4 ) и ∆1 > 0 , то в базис вводится переменная x 1 , соответствующий этойпеременной столбец – ⊕ -столбец.Вычислим величины ri , как отношения элементов столбца Бр к элементам ⊕ -столбца:14r1 == −1r2 = = 2−12Из базиса выводится переменная x 5 , т.к. ей соответствует минимальная неотрицательнаявеличина r2 , соответствующая ей строка – ⊕ -строка.На пересечении ⊕ -столбца и ⊕ -строки, находится разрешающий элемент R = 2 .Осуществим пересчет таблицы:• запишем коэффициенты функции в верхнюю строку новой таблицы №2;• запишем в новую таблицу №2 новые базисные переменные x 3 и x 1 ;• запишем коэффициенты функции при новых базисных переменных в первый столбец таблицы№2• пересчитаем ⊕ -строку: разделим ⊕ -строку на разрешающий элемент, результат запишем во 2ю строку таблицы №2 – получится N-строка;⊕ -строка (Результат•422111/200-1-1/211/2)/2пересчитаем оставшуюся строку: умножим N-строку на 1-й элемент ⊕ -столбца – это (-1), ивычтем из 1-й строки таблицы №1, результат запишем в 1-ю строку таблицы №2:Строка 1 таблицы №1N * (-1)Результат1-23-1-101-1/23/210101/2-1/20-1/21/2Таблица №24100-MCjCiБпБрx1x2x3x4x5ri04x3x132013/21/210-1/2-1/21/21/2-6-4∆0-102-M-2⊕ -столбецБазисное решение, соответствующее таблице №2:x3 = 3x2 = 0x1 = 2x4 = 0x5 = 0В исходных переменных x1 , x 2 это решение соответствует точке с координатами (3, 0) .Вычислим симплекс-разности для небазисных переменных: 0 3 / 2 = 1 − (0 + 2) = −1∆ 2 = 1 −   ⋅  4 1 / 2  0  − 1 / 2 = 0 − (0 − 2) = 2∆ 4 = 0 −   ⋅  4  − 1 / 2 0  1 / 2  = − M − (0 + 2) = − M − 2∆ 5 = − M −   ⋅  4  1 / 2 Т.к.

∆ 4 = max(∆ 2 , ∆ 4 , ∆ 5 ) и ∆ 4 > 0 , то в базис вводится переменная x 4 , соответствующий этойпеременной столбец – ⊕ -столбец.Т.к. ⊕ -столбец содержит только неположительные элементы, то из базиса нечего вывести, и,следовательно, у задачи нет решения вследствие неограниченности множества допустимыхрешений в направлении градиента.Найдем минимум функции. Будем рассматривать задачу:f (X) = 4 x 1 + x 2 → min- x1 + x 2 ≤ 12 x1 + x 2 ≥ 4x1 , x 2 ≥ 0Перейдем к задаче поиска максимума, для этого умножим функцию на (-1), получим:f (X) = - 4 x 1 - x 2 → max- x1 + x 2 ≤ 12 x1 + x 2 ≥ 4x1 , x 2 ≥ 0Т.к.

данная задача отличается от решенной только коэффициентами функции, воспользуемсярезультатами подготовки задачи для поиска максимума исходной функции, получим:f (X) = - 4 x 1 - x 2 + 0 x 3 + 0 x 4 - M x 5 → max- x1 + x 2 + 1 x 3 + 0 x 4 + 0 x 5 = 12 x1 + x 2 + 0 x 3 - 1 x 4 + 1 x 5 = 4x1 , x 2 , x 3 , x 4 , x 5 ≥ 0Базисные переменные в задаче: в 1-м ограничении - x 3 ,во 2-м ограничении - x 5Начальное базисное решение:x1 = 0x2 = 0x3 =1x4 = 0-4-1x5 = 4Таблица №100-MCjCiБпБрx1x2x3x4x5ri0x31-11100-1-Mx54210-1120-M0∆2M-4M-1⊕ -столбец⊕ -строкаБазисное решение, соответствующее таблице №1:x1 = 0x3 =1x5 = 4x2 = 0x4 = 0В исходных переменных x1 , x 2 это решение соответствует точке с координатами (0, 0) .Вычислим симплекс-разности для небазисных переменных: 0   − 1 ⋅   = −4 − (0 − 2M ) = 2M − 4∆ 1 = −4 − − M  2  0  1 ⋅   = −1 − (0 − M ) = M − 1∆ 2 = −1 −  − M  1 0  0 ⋅   = 0 − (0 + M ) = − M∆ 4 = 0 −  − M   − 1Т.к.

∆1 = max(∆ 1 , ∆ 2 , ∆ 4 ) и ∆1 > 0 , то в базис вводится переменная x 1 , соответствующий этойпеременной столбец – ⊕ -столбец.Вычислим величины ri , как отношения элементов столбца Бр к элементам ⊕ -столбца:14r1 == −1r2 = = 2−12Из базиса выводится переменная x 5 , т.к. ей соответствует минимальная неотрицательнаявеличина r2 , соответствующая ей строка – ⊕ -строка.На пересечении ⊕ -столбца и ⊕ -строки, находится разрешающий элемент R = 2 .Осуществим пересчет таблицы:• запишем коэффициенты функции в верхнюю строку новой таблицы №2;• запишем в новую таблицу №2 новые базисные переменные x 3 и x 1 ;••запишем коэффициенты функции при новых базисных переменных в первый столбец таблицы№2пересчитаем ⊕ -строку: разделим ⊕ -строку на разрешающий элемент, результат запишем во 2ю строку таблицы №2 – получится N-строка;⊕ -строка (Результат•422111/200-1-1/211/2)/2пересчитаем оставшуюся строку: умножим разрешающую строку на 1-й элемент ⊕ -столбца –это (-1), и вычтем из 1-й строки таблицы №1, результат запишем в 1-ю строку таблицы №2:Строка 1 таблицы №1N * (-1)Результат1-23-1-101-1/23/210101/2-1/20-1/21/2Таблица №2-4-100-MCjCiБпБрx1x2x3x4x5ri0x3303/21-1/21/22-4x1211/20-1/21/24∆00-2-M+21⊕ -столбец⊕ -строкаБазисное решение, соответствующее таблице №2:x3 = 3x2 = 0x1 = 2x4 = 0x5 = 0В исходных переменных x1 , x 2 это решение соответствует точке с координатами (3, 0) .Вычислим симплекс-разности для небазисных переменных: 0   3 / 2 = −1 − (0 − 2) = 1∆ 2 = −1 −   ⋅  − 4 1 / 2  0   − 1 / 2 = 0 − (0 + 2) = −2∆ 4 = 0 −   ⋅  − 4  − 1 / 2 0  1 / 2  = − M − (0 − 2) = −M + 2∆ 5 = −M −   ⋅  − 4  1 / 2 Т.к.

∆ 2 = max(∆ 2 , ∆ 4 , ∆ 5 ) и ∆ 2 > 0 , то в базис вводится переменная x 2 , соответствующий этойпеременной столбец – ⊕ -столбец.Вычислим величины ri , как отношения элементов столбца Бр к элементам ⊕ -столбца:32r1 ==2r2 ==43/ 21/ 2Из базиса выводится переменная x 3 , т.к. ей соответствует минимальная неотрицательнаявеличина r1 , соответствующая ей строка – ⊕ -строка.На пересечении ⊕ -столбца и ⊕ -строки, находится разрешающий элемент R = 3 / 2 .Осуществим пересчет таблицы:• запишем коэффициенты функции в верхнюю строку новой таблицы №3;• запишем в новую таблицу №3 новые базисные переменные x 2 и x 1 ;• запишем коэффициенты функции при новых базисных переменных в первый столбец таблицы№3• пересчитаем ⊕ -строку: разделим ⊕ -строку на разрешающий элемент, результат запишем в 1ю строку таблицы №3 – получится N-строка;⊕ -строка (Результат•32003/2112/3-1/2-1/31/21/3) / (3/2)пересчитаем оставшуюся строку: умножим разрешающую строку на 2-й элемент ⊕ -столбца –это (1/2), и вычтем из 2-й строки таблицы №2, результат запишем во 2-ю строку таблицы №3:Строка 2 таблицы №2Разрешающая строка * (1/2)Результат2111011/21/2001/3-1/3-1/2-1/6-1/31/21/61/3Таблица №3-4Ci-1-4Бп-100-MCjБрx1x2x3x4x5ri2012/3-1/31/3-6x210-1/3-1/31/3-41x100-2/3-5/3∆M+5/3Базисное решение, соответствующее таблице №3:x2 = 2x3 = 0x1 = 1x4 = 0x5 = 0В исходных переменных x1 , x 2 это решение соответствует точке с координатами (1, 2) .Вычислим симплекс-разности для небазисных переменных: − 1  2 / 3  = 0 − (−2 / 3 + 4 / 3) = −2 / 3∆ 3 = 0 −   ⋅  − 4   − 1 / 3 − 1   − 1 / 3 = 0 − (1 / 3 + 4 / 3) = −5 / 3∆ 4 = 0 −   ⋅  − 4   − 1 / 3 − 1  1 / 3  = − M − (−1 / 3 − 4 / 3) = − M + 5 / 3∆ 5 = − M −   ⋅  − 4  1 / 3 Т.к.

все симплекс-разности в таблице №3 неположительны, то критерий окончания выполнен.Проанализируем полученное базисное решение. В состав базисных переменных таблицы №3 невходят искусственные переменные, значит, получено решение задачи:x1* = 1x2* = 2x3* = 0x4* = 0x5* = 0 .Это решение единственное, так как строка симплекс-разностей таблицы №3 содержит два (почислу ограничений задачи) нулевых значения.Решение исходной задачи получается отбрасыванием дополнительных и искусственныхпеременных. Ему соответствует точка A = (1, 2) .Ответ:Функция не имеет максимума.Функция имеет минимум в точке A с координатами:x1* = 1 ,x2* = 2 .f (X*min ) = 4 ⋅ 1 + 2 = 6 ..