RulTO-3 (1013558), страница 2
Текст из файла (страница 2)
ей по строке соответствует минимальнаянеотрицательная величина r2 , соответствующая ей строка – Z-строка.r1 =1= −1−1r2 =На пересечении Z-столбца и Z-строки, находится разрешающий элемент R = 3 .Осуществим пересчет таблицы:• запишем коэффициенты функции в верхнюю строку новой таблицы №3;• запишем в новую таблицу №3 новые базисные переменные x 2 x1 ;•запишем коэффициенты функции при новых базисных переменных в первый столбецтаблицы №3Пример выполнения этапа №3, 2010 г.Лунева С.Ю. Методические указания к РГР по ТО (ТО и ЧМ)•пересчитаем Z-строку: разделим Z-строку на разрешающий элемент, результатзапишем во 2-ю строку таблицы №3 – получится разрешающая строка;Z-строка (31Результат•стр.93100-1-1/311/3)/3пересчитаем оставшуюся строку: умножим разрешающую строку на коэффициентпересчета - 1-й элемент Z-столбца – это (-1), и вычтем из 1-й строки таблицы №2,результат запишем в 1-ю строку таблицы №3:Строка 1 таблицы №21-1110Разрешающая строка * (-1)-1-101/3-1/3Результат2012/31/3Таблица №3Ci3-1БпБрx2x121∆-1300Cjx1010x2100x32/3x41/31/3-2/3ri-1/3-7/3Базисное решение, соответствующее таблице №3:x2 = 2x1 = 1x3 = 0x4 = 0В исходных переменных x 1 , x 2 это решение соответствует точке с координатами (1, 2) .Вычислим симплекс-разности для небазисных переменных: 3 2/3 = 0 − (2 + 1 / 3) = −7 / 3∆ 3 = 0 − ⋅ −1−1/3 3 1 / 3 ∆ 4 = 0 − ⋅ = 0 − (1 − 1 / 3) = −2 / 3 − 1 1 / 3 Т.к.
все симплекс-разности в таблице №3 неположительны вычисления закончены.Проанализируем полученное базисное решение. В состав базисных переменных таблицы№3 не входят искусственные, значит получено решение задачи:x1* = 1x2* = 2x3* = 0x4* = 0Это решение единственное, т.к строка симплекс-разностей таблицы №3 содержит два (почислу ограничений задачи) нулевых значения.А в исходных переменных – это точка B = (1, 2) .Пример выполнения этапа №3, 2010 г.Лунева С.Ю. Методические указания к РГР по ТО (ТО и ЧМ)стр.10Найдем минимум функции. Будем рассматривать задачу:f (X ) = − x1 + 3x 2 → min− x1 + x 2 ≤ 12 x1 + x 2 ≤ 4x1 , x 2 ≥ 0Перейдем к задаче поиска максимума, для этого умножим функцию на (-1), получим:f (X ) = x 1 − 3x 2 → max− x1 + x 2 ≤ 12 x1 + x 2 ≤ 4x1 , x 2 ≥ 0Т.к. данная задача отличается от решенной только коэффициентами функции,воспользуемся результатами подготовки задачи для поиска максимума исходнойфункции, получим:f (X ) = x 1 − 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)Таблица №11-300CjCiБпБрx1x2x3x4ri0x31-1110-10x44210121-300∆Z-столбецБазисное решение, соответствующее таблице №1:x3 = 1x4 = 4x1 = 0x2 = 0Пример выполнения этапа №3, 2010 г.Z-строкаЛунева С.Ю.
Методические указания к РГР по ТО (ТО и ЧМ)стр.11Вычислим симплекс-разности для небазисных переменных: 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 , соответствующийэтой переменной столбец – Z-столбец.Вычислим величины ri , как отношения элементов столбца Б p к элементам Z-столбца:4=22Из базиса выводится переменная x 4 , т.к.
ей по строке соответствует минимальнаянеотрицательная величина r2 , соответствующая ей строка – Z-строка.r1 =1= −1−1r2 =На пересечении Z-столбца и Z-строки, находится разрешающий элемент R = 2 .Осуществим пересчет таблицы:• запишем коэффициенты функции в верхнюю строку новой таблицы №2;• запишем в новую таблицу №2 новые базисные переменные x 3 x1 ;• запишем коэффициенты функции при новых базисных переменных в первый столбецтаблицы №2• пересчитаем Z-строку: разделим Z-строку на разрешающий элемент, результатзапишем во 2-ю строку таблицы №2 – получится разрешающая строка;Z-строка (42Результат•2111/20011/2)/2пересчитаем оставшуюся строку: умножим разрешающую строку на коэффициентпересчета, - 1-й элемент Z-столбца – это (-1), и вычтем из 1-й строки таблицы №1,результат запишем в 1-ю строку таблицы №2:Строка 1 таблицы №11-1110Разрешающая строка * (-1)-2-1-1/20-1/2Результат303/211/2Таблица №2Ci01БпБрx33x12∆1-300Cjx1010x23/2½0x31x41/21/2-1/2ri0-7/2Пример выполнения этапа №3, 2010 г.Лунева С.Ю.
Методические указания к РГР по ТО (ТО и ЧМ)стр.12Базисное решение, соответствующее таблице №2:x3 = 3x1 = 2x2 = 0x4 = 0В исходных переменных x 1 , x 2 это решение соответствует точке с координатами ( 2, 0) .Вычислим симплекс-разности для небазисных переменных: 0 3/ 2 = −3 − (0 + 1 / 2) = −7 / 2∆ 2 = −3 − ⋅ 1 1/ 2 0 1 / 2 = 0 − (0 + 1 / 2) = −1 / 2∆ 4 = 0 − ⋅ 11/2 Т.к. все симплекс-разности в таблице №2 неположительны вычисления закончены.Проанализируем полученное базисное решение. В состав базисных переменных таблицы№2 не входят искусственные, значит получено решение задачи:x1 * = 2x2* = 0x 3* = 3x4* = 0Это решение единственное, т.к строка симплекс-разностей таблицы №2 содержит два (почислу ограничений задачи) нулевых значения.А в исходных переменных – это точка C = ( 2, 0) .Ответ:Функция имеет максимум в точке B с координатами:x 1* = 1x *2 = 2f (X *max ) = −1 + 3 ⋅ 2 = 5Функция имеет минимум в точке C с координатами:x1* = 2x *2 = 0f (X *min ) = −2 + 3 ⋅ 0 = −2Пример выполнения этапа №3, 2010 г..