RulTO-3 (Правила выполнения РГР для заочников)

Лунева С.Ю. Методические указания к РГР по ТО (ТО и ЧМ)стр.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  11  0базисныйстолбецx40 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) = −10  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) = 20  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 , т.к.