RulTO-3 (1013558)
Текст из файла
Лунева С.Ю. Методические указания к РГР по ТО (ТО и ЧМ)стр.1Этап №3Методы решения задачи линейного программированияДано:f (X ) = − x1 + 3x 2 → extr− x1 + x 2 ≤ 12 x1 + x 2 ≤ 4x1 , x 2 ≥ 0(1)(2)(3)а) Решить задачу графическиАлгоритм графического решения задачи1. Построить множество допустимых решений, задаваемое ограничениями.2. Построить градиент целевой функции в точке с координатами (0, 0) .3. Построить линию уровня целевой функции, проходящую через точку с координатами(0, 0) .4. Если требуется найти максимум целевой функции, переносить, используяпараллельный перенос, построенную линию уровня функции в направлении градиентадо последнего касания с множеством допустимых решений.
Точка (точки) касания максимум.Если требуется найти минимум целевой функции, аналогично переносить построеннуюлинию уровня функции в направлении противоположном градиенту до последнегокасания с множеством допустимых решений. Точка (точки) касания - минимум.Решение:Для графического решения задачизадаваемое ограничениями (1)-(3).построиммножестводопустимыхрешений,Ограничение (1) в задаче определяется прямой − x 1 + x 2 = 1 , проходящей через точки:x1x201-10Множество допустимых решений в задаче будет ограничено этой прямой и содержатьточку (0, 0) , т.к при подстановке координат этой точки в ограничение (1) получаетсяверное неравенство: − 0 + 0 ≤ 1Ограничение (2) в задаче определяется прямой 2 x1 + x 2 = 4 , проходящей через точки:x102x240Пример выполнения этапа №3, 2010 г.Лунева С.Ю. Методические указания к РГР по ТО (ТО и ЧМ)стр.2Множество допустимых решений в задаче будет ограничено этой прямой и содержатьточку (0, 0) , т.к при подстановке координат этой точки в ограничение (2) получаетсяверное неравенство: 2 ⋅ 0 + 0 ≤ 4Ограничения (3) в задаче задают 1-ю четверть координатной плоскости.Отметим крайние точки получившегося множества: O, A, B, C.Построим градиент функции ∇f ( X) = ( −1,3) T в точке с координатами (0, 0)Построим линию уровня функции f (X ) = C , проходящую через точку с координатами(0, 0) .
Для этого найдем значение константы C , подставив координаты точки в целевуюфункцию: C = −0 + 3 ⋅ 0 = 0 , и затем построим прямую − x 1 + 3x 2 = 0 .Пример выполнения этапа №3, 2010 г.Лунева С.Ю. Методические указания к РГР по ТО (ТО и ЧМ)стр.3Будем искать точку максимума функции как последнюю точку касания линии уровняфункции и множества допустимых решений в направлении градиента функции. Как видноиз чертежа, это точка B = (1, 2) . Таким образом, получено решение задачи поискамаксимума функции:x 1* = 1x *2 = 2f (X *max ) = −1 + 3 ⋅ 2 = 5Будем искать точку минимума функции как последнюю точку касания линии уровняфункции и множества допустимых решений в направлении противоположном градиентуфункции✸). Как видно из чертежа, это точка C = ( 2, 0) . Таким образом, получено решениезадачи поиска минимума функции:x1* = 2x *2 = 0f (X *min ) = −2 + 3 ⋅ 0 = −2✸)Для поиска минимума можно перемещать линию уровня функции в направлении градиента до первойточки касания с множеством допустимых решений.Пример выполнения этапа №3, 2010 г.Лунева С.Ю.
Методические указания к РГР по ТО (ТО и ЧМ)стр.4б) Решить задачу симплекс-методом (найти максимум и минимум)Алгоритм подготовки задачи к решению симплекс-методом1. Симплекс-метод ищет максимум функции. Если требуется найти минимум, умножитьцелевую функцию на (-1) и перейти к задаче поиска максимума.2. Правые части ограничений должны быть ≥ 0. Если правая часть ограничения < 0,умножить его левую и правую части на (-1) и изменить знак ограничения напротивоположный.3. Привести задачу к каноническому виду - перейти от задачи с ограничениями типанеравенств к задаче с ограничениями типа равенств, вводя, если это необходимо, вкаждое ограничение дополнительную переменную.Замечание: Если ограничение представляет собой неравенство типа « ≤ »дополнительная переменная вводится с коэффициентом 1, если это неравенство типа« ≥ » дополнительная переменная вводится с коэффициентом (-1).Ввести дополнительные переменные в целевую функцию с коэффициентами равными 0.4. Выписать столбцы коэффициентов при переменных в ограничениях.
Если средивыписанных столбцов имеется m (по числу ограничений) базисных столбцов - столбцовединичной матрицы размерности m x m , перейти к п. 6.5. Если нужное число базисных столбцов не найдено перейти к решению M-задачи:• дописать недостающие столбцы искусственно;• поставить им в соответствие искусственные переменные;• переписать ограничения с учетом искусственных переменных;• ввести искусственные переменные в целевую функцию с коэффициентами6равными ( − M ) , где M - очень большое положительное число, например 10 .6. Выписать переменные при базисных столбцах - эти переменные базисные. Записатьначальное базисное решение: базисные переменные равны правым частям ограничений,в которые они входят, все остальные переменные равны 0.Алгоритм вычислений с помощью симплекс-таблиц1. Составить таблицу №1.2.
Выписать базисное решение. Вычислитьпеременных по формуле: ∆ j = C j − C iБ ⋅ A jсимплекс-разностидлянебазисныхПеременная, которой соответствует в столбце максимальная положительная симплексразность, вводится в базис. Соответствующий столбец пометим – Z .3. Высчитать величины ri по формуле: ri =БpiZi.Переменная, которой соответствует в строке минимальная неотрицательная величина ri ,выводится из базиса. Соответствующую строку пометим - Z . Элемент, стоящий напересечении Z -столбца и Z -строки – разрешающий элемент - R .Пример выполнения этапа №3, 2010 г.Лунева С.Ю.
Методические указания к РГР по ТО (ТО и ЧМ)стр.54. Построить новую таблицу, пересчитав предыдущую.•Пересчет таблицыЗаполнить в новой таблице: строку коэффициентов функции, столбец Б п и столбецС iБ .•Пересчитать Z -строку, содержащую разрешающий элемент и записать в новуютаблицу под тем же номером по формуле:новая строка = старая строка / RПолученная строка – разрешающая.•Пересчитать все остальные строки таблицы и записать их под теми же номерами вновую таблицу по формуле:новая строка K = старая строка K – (разрешающая строка) * КПересчета,здесь КПересчета – элемент, стоящий на пересечении строки K и Z -столбца в старойтаблице.5. Повторить процедуру 2-4 до тех пор, пока все симплекс-разности не станут ≤ 0.6. Проанализировать последнее полученное базисное решение.Замечания по процедуре счёта№1.
Каждая таблица соответствует точке пересечения ограничений на графике, причемпока в базисе есть искусственные переменные – это точки вне множества допустимыхрешений.№2. В каждой таблице при текущих базисных переменных должны стоять столбцыединичной матрицы.№3. Столбец Б p должен всегда содержать только неотрицательные элементы.Замечания по анализу результатов счёта№1. Если в процессе решения оказалось, что в базис вводится некоторая переменная(существует симплекс-разность > 0), но среди элементов Z -столбца нет ни одногоположительного, значит, задача не имеет решения вследствие не замкнутости областидопустимых решений.№2.
Если в таблице, соответствующей решению задачи, в строке симплекс-разностейсодержится нулей больше, чем ограничений, значит, задача имеет бесконечноемножество решений, одно из которых найдено.№3. Если при решении M-задачи найдено решение (все симплекс-разности ≤ 0), но всоставе базисных переменных сталась искусственная переменная не равная 0, тоисходная задача не имеет решения вследствие несовместности ограничений.Пример выполнения этапа №3, 2010 г.Лунева С.Ю.
Методические указания к РГР по ТО (ТО и ЧМ)стр.6Решение:Найдем максимум функции. Будем рассматривать задачу:f (X ) = − x1 + 3x 2 → max− x1 + x 2 ≤ 12 x1 + x 2 ≤ 4x1 , x 2 ≥ 0Подготовим задачу к решению симплекс-методом.В задаче требуется найти максимум, правые части ограничений неотрицательны.Перейдем от задачи в основной постановке к задаче в канонической. Т.к. обаограничения – неравенства типа « ≤ », введем в каждое ограничение дополнительнуюпеременную с коэффициентом 1:f (X) = − x1 + 3x 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 = 4x 3 ≥ 0, x 4 ≥ 0 - дополнительные переменные в задачеВыпишем столбцы при переменных в ограничениях:x1x2x3 − 1 2 1 11 0базисныйстолбецx40 1базисныйстолбецБазис в задаче есть, т.к. среди выписанных столбцов есть 2 базисных (столбцыединичной матрицы (2 х 2)).Окончательно получаем задачу, подготовленную к решению симплекс-методом:f (X) = − x1 + 3x 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 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0Базисные переменные в задаче: в 1-м ограничении - x 3 ,во 2-м ограничении - x 4Начальное базисное решение:x1 = 0x2 = 0x3 = 1x4 = 4В исходных переменных x 1 , x 2 это решение соответствует точке с координатами (0, 0) .Пример выполнения этапа №3, 2010 г.Лунева С.Ю.
Методические указания к РГР по ТО (ТО и ЧМ)стр.7РазрешающийэлементТаблица №1-1300CjCiБпБрx1x2x3x4ri0x31-111010x4421014∆-1300Z-строкаZ-столбецБазисное решение, соответствующее таблице №1:x3 = 1x4 = 4Коэффициентпересчетаx1 = 0x2 = 0Вычислим симплекс-разности для небазисных переменных: 0 − 1∆1 = −1 − ⋅ = −1 − (0 + 0) = −10 2 0 1 ∆ 2 = 3 − ⋅ = 3 − (0 + 0) = 3 0 1 Т.к. ∆ 2 = max( ∆1 , ∆ 2 ) и ∆ 2 > 0 , то в базис вводится переменная x 2 . Соответствующийэтой переменной столбец – Z-столбец.Вычислим величины ri , как отношения элементов столбца Б p к элементам Z-столбца:1r1 = = 11r2 =4=41Из базиса выводится переменная x 3 , т.к.
ей по строке соответствует минимальнаянеотрицательная величина r1 , соответствующая ей строка – Z-строка.На пересечении Z-столбца и Z-строки, находится разрешающий элемент R = 1 .Осуществим пересчет таблицы:• запишем коэффициенты функции в верхнюю строку новой таблицы №2;• запишем в новую таблицу №2 новые базисные переменные x 2 x 4 ;••запишем коэффициенты функции при новых базисных переменных в первый столбецтаблицы №2пересчитаем Z-строку: разделим Z-строку на разрешающий элемент, результатзапишем в 1-ю строку таблицы №2 – получится разрешающая строка;Z-строка (Результат11-1-11111Пример выполнения этапа №3, 2010 г.00)/1Лунева С.Ю.
Методические указания к РГР по ТО (ТО и ЧМ)•стр.8пересчитаем оставшуюся строку: умножим разрешающую строку на коэффициентпересчета - 2-й элемент Z-столбца – это (1), и вычтем из 2-й строки таблицы №1,результат запишем во 2-ю строку таблицы №2:Строка 2 таблицы №1Разрешающая строка * (1)Результат4132-1311001-1101Таблица №2-1300CjCiБпБрx1x2x3x4ri3x2x41-1110-1330-111∆20-300Z-строкаZ-столбецБазисное решение, соответствующее таблице №2:x2 =1x4 = 3x1 = 0x3 = 0В исходных переменных x 1 , x 2 это решение соответствует точке с координатами (0, 1) .Вычислим симплекс-разности для небазисных переменных: 3 − 1∆1 = −1 − ⋅ = −1 − (−3 + 0) = 20 3 3 1 ∆ 3 = 0 − ⋅ = 0 − (3 + 0) = −3 0 − 1Т.к. ∆1 = max( ∆1 , ∆ 3 ) и ∆1 > 0 , то в базис вводится переменная x1 , соответствующийэтой переменной столбец – Z-столбец.Вычислим величины ri , как отношения элементов столбца Б p к элементам Z-столбца:3=13Из базиса выводится переменная x 4 , т.к.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
