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

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

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

Образец выполнения этапа №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.

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

Тип файла PDF

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

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

Список файлов учебной работы