Пример выполнения этапа №3 РГР (Примеры выполнения РГР (все в одном архиве))

Образец выполнения этапа №3 РГРРасчетно-графическая работапо курсу «Теория оптимизации и численные методы».Выполнил студент группы 04-206 Иванов И.И.Вариант №1Задание:Вариант #1f (X) = − x1 + 3x 2 → extr− x1 + x 2 ≤ 1Этап №3. Тема: Методы решения ЗЛПЗадание:а) Найти максимум и минимум в задачеграфически.б) Найти максимум и минимум в задачесимплекс-методом2x1 + x 2 ≤ 4x1 , x 2 ≥ 03. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯПример 3а).Дано:f (X) = − x1 + 3x 2 → extr− x1 + x 2 ≤ 1 ,(1)2x1 + x 2 ≤ 4 ,(2)x1 , x 2 ≥ 0 .(3)Найти решение задачи графически.Решение:1. Для графического решения задачи построим множество допустимых решений, задаваемоеограничениями (1)-(3).Ограничение (1) в задаче определяется прямой − x1 + x 2 = 1 , проходящей через точки:x1x201−10Множество допустимых решений в задаче будет ограничено этой прямой и будет содержать точку(0, 0)T , так как при подстановке координат этой точки в ограничение (1) получается верноенеравенство: −0 + 0 ≤ 1 .Ограничение (2) в задаче определяется прямой 2x1 + x 2 = 4 , проходящей через точки:x1x20420Множество допустимых решений в задаче будет ограничено этой прямой и будет содержать точку(0, 0)T , так как при подстановке координат этой точки в ограничение (2) получается верноенеравенство: 2 ⋅ 0 + 0 ≤ 4 .Ограничения (3) в задаче задают 1-ю четверть координатной плоскости.1Образец выполнения этапа №3 РГРМножество допустимых решений включает все точки, в которых ограничения выполняютсяодновременно.

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

Таким образом, получено решение задачи поиска максимума функции:x1* = 1 ,x*2 = 2 ,f (X*max ) = −1 + 3 ⋅ 2 = 5 .Будем искать точку минимума функции как последнюю точку касания линии уровня и множествадопустимых решений при параллельном переносе линии ⊕ в направлении, противоположномградиенту функции. Как видно из чертежа, это точка C = (2, 0)T (соответствующая линия уровняизображена штриховой линией). Таким образом, получено решение задачи поиска минимумафункции:x1* = 2 ,x*2 = 0 ,f (X*min ) = −2 + 3 ⋅ 0 = −2 .3Образец выполнения этапа №3 РГРПример 3б).Дано:f (X) = − x1 + 3x 2 → extr− x1 + x 2 ≤ 1 ,(1)2x1 + x 2 ≤ 4 ,(2)x1 , x 2 ≥ 0 .(3)Найти решение задачи симплекс-методом.Решение:Найдем максимум функции. Будем рассматривать задачу:f (X) = − x1 + 3x 2 → max− x1 + x 2 ≤ 1 ,2x1 + x 2 ≤ 4 ,x1 , x 2 ≥ 0 .Подготовим задачу к решению симплекс-методом.1.-2. В задаче требуется найти максимум, правые части ограничений неотрицательные.3.

Приведем задачу к каноническому виду. Так как первое ограничение – неравенство типа « ≤ »,введем в него дополнительную переменную с коэффициентом 1. Так как второе ограничение –неравенство типа « ≤ », введем в него дополнительную переменную с коэффициентом 1.Дополнительные переменные введем в целевую функцию с коэффициентами, равными нулю.f (X) = − x1 + 3x 2 + 0 ⋅ x 3 + 0 ⋅ x 4 → max− x1 + x 2 + 1 ⋅ x 3 + 0 ⋅ x 4 = 1 ,2x1 + x 2 + 0 ⋅ x 3 + 1 ⋅ x 4 = 4 ,x1 , x 2 ≥ 0 ,x 3 ≥ 0, x 4 ≥ 0 - дополнительные переменные.4. Выпишем столбцы при переменных в ограничениях:x1x2x3 − 1 2 1  11  0базисныйстолбецx40 1базисныйстолбецБазис в задаче есть, так как среди выписанных столбцов есть два базисных (столбцов единичнойматрицы размеров (2 х 2)). Перехода к M-задаче не требуется.6.

Окончательно получаем задачу, подготовленную к решению симплекс-методом:f (X) = − x1 + 3x 2 + 0 ⋅ x 3 + 0 ⋅ x 4 → max4Образец выполнения этапа №3 РГР− x1 + x 2 + 1 ⋅ x 3 + 0 ⋅ x 4 = 1 ,2x1 + x 2 + 0 ⋅ x 3 + 1 ⋅ x 4 = 4 ,x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0 .Базисные переменные в задаче: в 1-м ограничении- x3,во 2-м ограничении - x 4 .Остальные переменные: x1 , x 2 - свободные.Начальное базисное решение:x3 = 1 ,x1 = 0 ,x4 = 4 ,x2 = 0 .В исходных переменных x1 , x 2 это решение соответствует точке (0, 0)T .Проведем вычисления с помощью симплекс таблиц.Разрешающийэлемент RТаблица №1−1300CiББпБрx1x2x3x4Cjri0x31−111010x4421014∆−1300⊕ -строка⊕ -столбецВычислим симплекс-разности для небазисных переменных:  0   −1 ∆1 = −1 −    ,    = −1 − (0 + 0) = −1 ,  0  2 Коэффициентпересчёта КП  0   1 ∆ 2 = 3 −    ,    = 3 − (0 + 0) = 3 .  0   1 Так как ∆ 2 = max(∆1 , ∆ 2 ) , и∆ 2 > 0 , то в состав базисных вводится переменная x 2 ,соответствующий этой переменной столбец – ⊕ -столбец (разрешающий столбец).Вычислим величины ri как отношения элементов столбца Бp к соответствующим элементам14⊕ -столбца: r1 = = 1,r2 = = 4 .11Из базиса выводится переменная x 3 , так как ей соответствует минимальная неотрицательнаявеличина r1 , соответствующая ей строка – ⊕ -строка (разрешающая строка).На пересечении ⊕ -столбца и ⊕ -строки находится разрешающий элемент R = 1 .5Образец выполнения этапа №3 РГРОсуществим пересчет таблицы:• запишем коэффициенты функции в верхнюю строку новой таблицы №2;• запишем в новую таблицу №2 базисные переменные x 2 и x 4 ;••запишем коэффициенты функции при базисных переменных в первый столбец таблицы №2;пересчитаем ⊕ -строку: разделим ⊕ -строку на разрешающий элемент, результат запишем в1-ю строку таблицы №2 – получится строка N;⊕ -строка (11Результат•−1−1111100) / (R = 1)пересчитаем оставшуюся строку: умножим строку N на коэффициент пересчета – это 2-йэлемент ⊕ -столбца, равный 1, и вычтем из 2-й строки таблицы №1, результат запишем во 2-юстроку таблицы №2:Строка 2 таблицы №1Строка N * (КП = 1)Результат4132−1311001−1101Таблица №2−1300CjCiББпБрx1x2x3x4ri3x21−1110−10x4330−111∆20−30⊕ -строка⊕ -столбецБазисное решение, соответствующее таблице №2:x2 = 1 ,x1 = 0 ,x4 = 3 ,x3 = 0 .В исходных переменных x1 , x 2 это решение соответствует точке (0, 1)T .Вычислим симплекс-разности для небазисных переменных:  3   −1 ∆1 = −1 −    ,    = −1 − (−3 + 0) = 2 ,  0  3   3  1 ∆3 = 0 −    ,    = 0 − (3 + 0) = −3 .  0   −1 Так как ∆1 = max(∆1 , ∆3 ) , и∆1 > 0 , то в состав базисных вводится переменнаяx1 ,соответствующий этой переменной столбец – ⊕ -столбец (разрешающий столбец).Вычислим величины ri как отношения элементов столбца Бp к соответствующим элементам13⊕ -столбца: r1 = = −1,r2 = = 1 .−136Образец выполнения этапа №3 РГРИз базиса выводится переменная x 4 , так как ей соответствует минимальная неотрицательнаявеличина r2 , соответствующая ей строка – ⊕ -строка (разрешающая строка).На пересечении ⊕ -столбца и ⊕ -строки находится разрешающий элемент R = 3 .Осуществим пересчет таблицы:• запишем коэффициенты функции в верхнюю строку новой таблицы №3;• запишем в новую таблицу №3 базисные переменные x 2 и x1 ;••запишем коэффициенты функции при базисных переменных в первый столбец таблицы №3;пересчитаем ⊕ -строку: разделим ⊕ -строку на разрешающий элемент, результат запишем во2-ю строку таблицы №3 – получится строка N;⊕ -строка (31Результат•3100−1−1/311/3) / (R = 3)пересчитаем оставшуюся строку: умножим строку N на коэффициент пересчета – это 1-йэлемент ⊕ -столбца, равный (−1), и вычтем из 1-й строки таблицы №2, результат запишем в1-ю строку таблицы №3:Строка 1 таблицы №2Строка N * (КП = −1)Результат1−12−1−1010111/32/30−1/31/3Таблица №3−1300Cjx21x32/3x41/3riCiБ3БпБрx22x10−1x1110−1/31/3∆00−7/3−2/3Базисное решение, соответствующее таблице №3:x2 = 2 ,x4 = 0 ,x1 = 1 ,x3 = 0 .В исходных переменных x1 , x 2 это решение соответствует точке (1, 2)T .Вычислим симплекс-разности для небазисных переменных: 3   2 / 3 ∆3 = 0 −    ,   = 0 − (2 + 1/ 3) = −7 / 3 ,−1−1/3  3  1/ 3  ∆4 = 0 −    ,   = 0 − (1 − 1/ 3) = −2 / 3 .  −1 1/ 3  Так как все симплекс-разности в таблице №3 неположительные, вычисления закончены.Проанализируем полученный результат: так как при решении не использовались искусственныепеременные, то получено решение задачи:7Образец выполнения этапа №3 РГРx1* = 1 ,x2* = 2 ,x3 * = 0 ,x4* = 0 .Это решение единственное, так как строка симплекс-разностей таблицы №3 содержит два (почислу ограничений задачи) нулевых значения.Решение исходной задачи получается отбрасыванием дополнительных переменных: x1* = 2 ,x 2 * = 0 .

Ему соответствует точка B = (1, 2)T .Найдем минимум функции. Будем рассматривать задачу:f (X) = − x1 + 3x 2 → min− x1 + x 2 ≤ 1 ,2x1 + x 2 ≤ 4 ,x1 , x 2 ≥ 0 .Перейдем к задаче поиска максимума, умножив функцию на (−1):f (X) = x1 − 3x 2 → max− x1 + x 2 ≤ 1 ,2x1 + x 2 ≤ 4 ,x1 , x 2 ≥ 0 .Так как данная задача отличается от решенной только коэффициентами функции, воспользуемсярезультатами подготовки задачи для поиска максимума исходной функции:f (X) = x1 − 3x 2 + 0 ⋅ x 3 + 0 ⋅ x 4 → max− x1 + x 2 + 1 ⋅ x 3 + 0 ⋅ x 4 = 1 ,2x1 + x 2 + 0 ⋅ x 3 + 1 ⋅ x 4 = 4 ,x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0 .Базисные переменные в задаче: в 1-м ограничении- x3,во 2-м ограничении - x 4 .Остальные переменные: x1 , x 2 - свободные.Начальное базисное решение:x3 = 1 ,x1 = 0 ,x4 = 4 ,x2 = 0 .В исходных переменных x1 , x 2 это решение соответствует точке (0, 0)T .Проведем вычисления с помощью симплекс таблиц.8Образец выполнения этапа №3 РГРТаблица №11−300CjCiББпБрx1x2x3x4ri0x31−1110−10x4421012∆1−300⊕ -строка⊕ -столбецВычислим симплекс-разности для небазисных переменных:  0   −1  ∆1 = 1 −    ,    = 1 − (0 + 0) = 1 , 0  2   0   1 ∆ 2 = −3 −    ,    = −3 − (0 + 0) = −3 .  0   1 Так как ∆1 = max(∆1 , ∆ 2 ) , и ∆1 > 0 , то в состав базисных вводится переменнаяx1 ,соответствующий этой переменной столбец – ⊕ -столбец (разрешающий столбец).Вычислим величины ri как отношения элементов столбца Бp к соответствующим элементам14⊕ -столбца: r1 = = −1,r2 = = 2 .−12Из базиса выводится переменная x 4 , так как ей соответствует минимальная неотрицательнаявеличина r2 , соответствующая ей строка – ⊕ -строка (разрешающая строка).На пересечении ⊕ -столбца и ⊕ -строки находится разрешающий элемент R = 2 .Осуществим пересчет таблицы:• запишем коэффициенты функции в верхнюю строку новой таблицы №2;• запишем в новую таблицу №2 базисные переменные x 3 и x1 ;••запишем коэффициенты функции при базисных переменных в первый столбец таблицы №2;пересчитаем ⊕ -строку: разделим ⊕ -строку на разрешающий элемент, результат запишем во2-ю строку таблицы №2 – получится строка N;⊕ -строка (Результат•422111/20011/2) / (R = 2)пересчитаем оставшуюся строку: умножим строку N на коэффициент пересчета – это 1-йэлемент ⊕ -столбца, равный (−1), и вычтем из 1-й строки таблицы №1, результат запишем в1-ю строку таблицы №2:Строка 1 таблицы №1Строка N * (КП = −1)Результат1−23−1−101−1/23/21010−1/21/29Образец выполнения этапа №3 РГРТаблица №2−1300Cjx23/2x31x41/2riCiБ0БпБрx33x101x1211/201/2∆00−7/2−1/2Базисное решение, соответствующее таблице №2:x3 = 3 ,x2 = 0 ,x1 = 2 ,x4 = 0 .В исходных переменных x1 , x2 это решение соответствует точке (2, 0)T .Вычислим симплекс-разности для небазисных переменных:  0  3 / 2∆ 2 = −3 −    ,   = −3 − (0 + 1/ 2) = −7 / 2 ,  1   1/ 2    0  1/ 2  ∆4 = 0 −    ,   = 0 − (0 + 1/ 2) = −1/ 2 .  1  1/ 2  Так как все симплекс-разности в таблице №2 неположительны, вычисления закончены.Проанализируем полученный результат: так как при решении не использовались искусственныепеременные, то получено решение задачи:x1 * = 2 ,x2* = 0 ,x3 * = 3 ,x4* = 0 .Это решение единственное, так как строка симплекс-разностей таблицы №2 содержит два (почислу ограничений задачи) нулевых значения.Решение исходной задачи получается отбрасыванием дополнительных переменных: x1* = 2 ,x 2 * = 0 .

Ему соответствует точка C = (2, 0)T .Ответ:Функция имеет максимум в точке B с координатами:x1* = 1 ,x*2 = 2 ,f (X*max ) = −1 + 3 ⋅ 2 = 5 .Функция имеет минимум в точке C с координатами:x1* = 2 ,x*2 = 0 ,f (X*min ) = −2 + 3 ⋅ 0 = −2 .10.