XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 17
Текст из файла (страница 17)
1(хг,кг) = Зх4+4хг -+ шах; х4+ хг (20, — хг+4хг < 20, кг >10, хг)5, к43~0, хг)0, уу = 10 — У4 + ув, Ув = 5 — Уг + Ув. Таким образом, 'Р— 15 + У1 + Уг — Ув — ув. Для задачи (3.25) начальное базисное решение может быть найдено с использованием приема, рассмотренного в начале зтого параграфа. Ненулевые компоненты зтого решения имеют вид В силу неотрицательности переменных модели (3.25) и специфики целевой функции ~р вспомогательной задачи линейного программирования ее оптпид4адьное решение будет соответствовать значению 3г= О, т.е.
в оптимальном решении компоненты, соответствующие искусственным переменным модели, будут нулевыми. Таким образом, если в оптимальном решении ы* 6 Й вспомогательной задачи линейного программирования вычеркнуть нулевые компоненты, соответствующие искусственным переменным модели (3.25), то полученный вектор У будет не только принадлежать множеству допустимых решений Я в (3.24), но и являться базисным допустимым решением исходной задачи, которое можно использовать в качестве начального.
Отметим, что если оптимальное значение цедееой функции вспомогательной задачи не равно нулю, то, как нетрудно заметить, множество допустимых решений исходной задачи пусто. Пример 3.9. Рассмотрим задачу линейного программиро- вания 3.3. ахождеине допустимого оаэисного решения в стандартной форме имеющую следующии вид. В рассматриваемом случае 14 = (1 2) 1 = О, 1 = 3 4 Вводим искусственные переменные модели уг, ув и записываем цспомогательную задачу линейного программирования в стаидартной форме: Для Вспомогательной задачи в качестве начального базисного решения можно взять ы = (О 0 20 20 0 0 10 5), тогда базис- ными переменными будут уз, У4, уг, ув. Вспомога гательную задачу линейного программирования будем решать с использованием сил4пдекс-уаабли .
Н лац. озтому, согласно 3.2 ( . 7), базисные переменные уг, ув, входящие в целевую функцию у, выражаем через свободные переменные: 119 118 3. СИМГ1ЛЕКС-МЕТОД Таблица 8.8 Таблица 8.8 Базисные переменные Итерация Значение У1 Уз У4 Уб Уб 0 0 0 0 — 1 0 0 -1 20 20 10 5 1 — 1 1 0 Уз У4 Ут Ув -1 — 1 0 0 1 1 3 4 15 0 1 0 — 1 0 — 1 0 0 — 1 10 30 10 5 0,1 0 4 1 0 0 1 — 1 1 1 0 Уз У4 У1 Ув 5 — 30 О 1 0 4 0 — 1 3 0 0 0 0 0 1 0 0 1 5 10 10 5 — 1 — 1 1 — 4 1 0 0 1 1 1 -1 4 — 1 0 0 — 1 Уз У4 У1 Уз — 1 — 1 — 3 — 4 0 -50 0 0 0 0 Порядок заполнения симплекс-таблиц вспомогательной за.
дачи и приемы работы с ними те же, что и в случае основной задачи (см. пример 3.5). Но для удобства дальнейших вычислений в симплекс-таблицы вспомогательной задачи линейного программирования введем еще одну строку, соответствующую целевой функции Г основной задачи линейного программирования (3.26). С зтой строкой будем проводить те же вычисления, что и обычно (т.е. на каждой итерации получать нули на месте пересечения строки со столбцами новых базисных переменных), не обращая внимания на значения симплекс-разностей небазисных переменных до того момента, пока р не примет нулевого значения.
Симплекс-таблицы, отражающие поиск оптимального решения для вспомогательной задачи (3,27), представлены в табл. 3.8. З.З. Нахождение допустимого базисного решении Итак начальное базисное решение для задачи линейного т программирования (3.26) имеет вид У = (10, 5, 5, 10, О, 0) и в преобразованном варианте Г' = 50+ Зуб+ 4ув. В табл. 3.9 приведены симплекс-таблицы, отражающие процесс нахождения оптимального решения для (3.26). Начальная симплекстаблица основной задачи получается из симплекс-таблицы вспомогательной задачи (см. табл, 3.8) вычеркиванием столбцов, соответствующих искусственным переменным ут и ув, и строки, соответствующей целевой функции р вспомогательной задачи. т Оптимальному решению У* = (12 8 0 0 2 3) соответствует значение целевой функции Г" =68.
Решая рассмотренную задачу линейного программирования графическим методом, можно непосредственно убедиться в том, что ее оптимальное решение Х" = (12 8) . Ф 121 3.4. Анализ на чувствительность з. сиМплякс-МетОД 120 1(хыхг) = Зхг +2хг — + шах; 2хг+хг < 2, Зх, +4хг > 12, хг >О хг>0 Таблица 3.10 Зуг+2уг -+ шах; 2уг + Уг + Уз = 2, Зу, + 4уг - У4 = 12, уь > О, /с = 1, 4, Рис. 3.6 Пример 3.10.
Рассмотрим следующую задачу линейного программирования: (рис. 3.6) или в стандартной форме: где уг — хг уг — хг, а уз и У4 — новые переменные. О хг= 2 4хг=12 В рассматриваемом случае в обозначениях (2.1) 1г = ( ), 1 = 111 12 = ю, 1з — †(2). Вводим искусственное переменное модели ув и записываем вспомогательную задачу линейного программирования в стандартной форме: чг(уь".,Ув) = — ув -+ шах; 2уг+ уз+ уз = 2, Зу, + 4уг — У4+ у, = 12, уь > О, /с = 1, 5.
Для вспомогательной задачи начальное базисное решение т имеет вид ьг = (О 0 2 0 12), бззисными переменными являются уз, уя, а целевую функцию ~р можно представить следующим образом: у = — 12+ Зуг + 4уг — У4. Дальнейшее решение вспомогательной задачи представлено в табл. 3.10.
Вспомогательная задача линейного программирования имеет оптимальное решение ьг*= (О 2 0 0 4) . В данном случае рассматриваемая задача не имеет допустимых решений, так как оптимальное значение целевой функции у вспомогательной задачи отлично от нуля. 3.4. Анализ на чувствительность В 2.1 показано, что для любой практической задачи ликейкого программирования при известном оптпимальном решении целесообразно проводить анализ на чуастпвипгельноспгь. С приемами проведения этого анализа мы ознакомились, применяя геометпричесний мепгод решения задач линейного программирования (см. примеры 2.2, 2.3).
В общем случае приемы, используемые при проведении анализа задач линейного программирования на чувствительность при известном оптимальном решении, весьма просты, хотя и отличаются некоторой 123 3.4. Анализ на чувствительность 3. СИМПЛЕКС- МЕТОД 122 Таблица 3.11 Базис- ные пере- менные Ите- ра- ция Значение У6 Уе Ут 15 120 100 1 2 15 1 3 10 У6 Уе 0 О 25/3 32О(3 20/3 1/3 5/3 2/3 4/5 33/5 1/5 2/3 13/3 1(3 О -1/15 1 -2/15 0 1/15 Уз Уе У6 †2/3 9/5 4/3 5/3 0 -11/15 5/12 — 13/12 7/12 5/6 — 7/6 1/6 125/12 455/12 55/12 -1/12 5/12 1/12 5/4 — 33/4 — 1/4 (3.28) -1/6 -ПО5(Г2 О 11/12 0 — 9/4 0 -7/12 5/7 — 6(7 2/7 50/7 325/7 55/7 -5/7 13/7 12/7 10/7 — 61/7 — 3/7 -1(7 4/7 1/7 Ут Уе Уз уь>0, /6=1,7, -З/7 -695/7 0 0 — 11/7 0 — 5/7 -13/7 громоздкостью. Для их иллюстраций обратимся к следующей задаче распределения ограниченных ресурсов.
Пример 3.11. Рассмотрим задачу линейного программи- рования /(х„х„х„х4) =4х, +5х, +9хз+11х4-+ тпах; хт+ хз+ хз+ х4 < 15, 7х, + 5хз+ Зхз+ 2х4 < 120, Зхт+ 5х2+ 10хз+ 15х4 < 100 хь > О, /6 = 1, 4 которая в стаандартной форме имеет вид 4У1 + 5У2 + 9уз + 11У4 -+ шах; ут + У2 + Уз + У4 + Уз = 15, 7У1 + 5 уз + 3 уз + 2У4 + ув = 120, ЗУт + 5У2 + 10Уз+ 15У4+ Ут = 100, г у, = хь /т = 1,4, а У5, ув, ут — новые переменные. Решение задачи с использованием симплекс-тпаблиц представлено в табл. 3.11. Оптимальному решению 1" = (50/7 0 55/7 0 0 325/7 0) соответствует значение целевой функции / = б95/7.
При этом базисными переменными в задаче (3.28) при последней итерации симплекс-мепьода являются ут, уз, ув, а свободными переменными — уз, У4 У5 Ут. Проводя анализ задачи линейного программирования на чувствительность при известном оптимальном решении, прежде всего определяют диапазоны допустимых изменений коэффициентов при переменных в целевой функции /'. При этом под допустпимыми изменениями понимают такие изменения этих коэффициентов, при которых оптпимальный базис рассматриваемой задачи линейного программирования (т.е.
базис при последней итерации симплекс-метода, соответствующий оптимальному решению) остается оптимальным. Пример 3.12. Продолжим рассмотрение задачи линейного программирования в стандартной форме (3.28). Предположим, что коэффициенты при переменных модели в целевой функции стали другими: /(у„у„уз,у4) = (4+6~)у~+ (5+02)у + (9+гз)у~+ (11+64)У4. Чтобы на нулевой итерации ведущим элементном симплекстпаблицы оставалось число 15 (см. табл. 3.11), должно выполняться условие 0 < 11+64 — — и ах(4+6„5+62, 9+6„11+64), приводящее к системе неравенств 64 > 11 64 гз > — 2, 64 62 > †, 64 61 > — 7. (3.29) 125 3.4.
Анална на чувствнтельнвсть 124 3 СИМПЛЕКС-МЕТОД или, что то же самое, В этом случае на первой итерации симплекс-разности равны: 9+5с2-с4 4+Зсз с4 5+Зсз — 2са — — ~4 О, О, О, Таким образом, чтобы на первой итерации ведущим элементом симплекс-таблицы оставалось число 4/5 (см. табл. 3. 11), должно выполняться условие 9+ 5с2 — са 0( 5 9+5я2 — с4 4+Зсз — с4 5+Зсз — 2~4 -11 — ~а =шах 5 3 ' 15 с4 — 5с2 < 9, 2с4+ 15с2 — 15с2 > — 7, 7с4+ 15с2 — 15сз > — 2, 4са — 15с, < 28. (З.зо) Если числа сы й = 1, 4, удовлетворяют неравенствам (3.29), (3.30), то на второй итерации симплекс-разности будут равны: О, ( — 1 — 5с2 + бс2 — а4)/6, (11 — 5с2 + 12сз — 7с4)/12, О, ( — 9 — 5с2+с4)/4, О, ( — 7+с2 — с4)/12).
Число 7/12 будет ведущим элементом симплекс-таблицы (см. табл. 3.11), если 0< 11 — 5с2 + 12сз — 7с4 Шак(пз, нэ, Ь ~т) 12 где 11 — 5с2+ 12сз — 7с4 приводящее к системе неравенств — 1 — 5с2+ 6с2 — са н2 6 — 9 — 5с2+с4 дз —— 12 — 7+ Я1 — Я4 12 1 5с2 — 12сз+ 7с4 < 11, 5с2 — 12с2+ 12сз — 5с4 > — 13, 5с2 + бсз — 5с4 > — 19, с1 2сз+с4 < 3 (3.31) 5с2 — 7с2+ 2сз ) — 3, 5с2 — 12сз+ 7с4 ~ (11, 10с2 — Зсз ) 13, с2 — с2 (~ 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
