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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Тема: Методы решения задачи линейного программированияПример №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 ..

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов вопросов/заданий