XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 12
Текст из файла (страница 12)
Таблица 2.5 Определите объемы производств продукции каждого вида, при которых прибыль предприятия будет наибольшей. Ответ: объем производства продукции вида А равен 12, объем производства продукции вида В равен 18, прибыль предприятия равна 1080. (3.2) А, '( — А,У,) 1 ! еК (3.4) (3.5) (3А) АУ=В, з. симплекс-метод В этой главе рассмотрен общий метод решения задач линейного программирования, известный как симплекс-мепьод. Процесс решения любой задачи линейного программирования симплекс-методом имеет итерационный характер: однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор, пока не будет найдено оптимальное реиьение. Информация, которую можно получить с использованием симплекс-метода, не ограничивается оптимальным решением.
Симплекс-метод позволяет дать экономическую интерпретацию оптимального решения и провести анализ математической модели на чувствительность. 3.1. Основные утверждения линейного программирования В 2.2 доказано, что задача линейного программирования может быть представлена в стандартной форме (2.5) и записана в матричном виде (2.11). При этом всегда можно считать, что система линейных алгебраических уравнений (2.6), входящая в (2.5), является базисной и Ь < Ф. В (2.11) система линейных алгебраических уравнений (2.6) представлена в виде где А= (оы) Е Мь1ч(К), Й5А= Ь < 1Ч, У= (уь ... уи), В = = (А ." д.ь) .
Не теряя общности рассуждений, первые Ь столбцов аь матрицы А далее можем считать базисными. В этом случае переменные уь, и = 1, Ь, называют базисными, а переменные 3.1. Основные утверждения линейного программирования 83 уь, й = 1+1, 1Ч вЂ” свободными переменными модели" (2.11). Таким образом, если аь=(о1ь ...
ссс,ь), 1=1,И; Аь=(а1 .. аь)ЕМъ(К); Уь=(у1 " уь); т Ал=(аь+ь ... аж)ЕМь,н-ь(К); У,=(уь+1 ... уа1), то матричное уравнение АУ = В может быть преобразовано к виду АьУь+ А,У, = В. (3.3) Отсюда находим Уь = Аь '( — АлУа) Таким образом, для любого У, Е К'ч ~ вектор является решением уравнения АУ = В, а при выполнении усло- Вия У > Оа1 он является допустимым решением, что непо- средственно следует из (2.11). В частности, при У, = Оы ь, согласно (3.4), решение уравнения АУ = В принимает вид Это решение называют базисным реиьением соответствующей задачи линейного программирования, а решение при У > Оь1 — допустимььм базисным реиьением.
Следует отметить, что в общем случае выбор базисных ,столбцов матрицы А не является единственным. Значит, выбор базисного решения не является однозначным. 'Эти термины — синонимы терминов „базисное неизвестное" и „свободное неизвестное" в курсе линейной алгебры (1Ч). 3. СИМПЛЕКС-МЕТОД 84 з4+хз(5, 1,5х4+хз (6, х4>0, хз>0. Согласно (2.11), Рис. 3.1 Пример 3.1.
Пусть для некоторой задачи линейного программирования множество С допустимых решений описывается ограничениями Для перехода к стандартной форме записи рассматриваемой задачи линейного программирования вводим новые управляемые переменные яз, я4 и, сохраняя старые обозначения, приходим к множеству Я допустимых решений задачи (2.5), которое задается ограничениями х4+зз+хз — — 5, 1,5я4+зз+х4 =6, хь)0, Й=1,4. А = (а1 нз аз а4) = , В = А так как К8А = 2, то для определения всех базисных решений из столбцов аь матрицы А составим всевозможные пары, которые могут быть базисными, и представим их матрицами: А4 — — (а4 аг)=~ ~, Аз=(а4 оз)=~ АЗ=(а4 а4)се ~ !, А4 — (ая аэ)= ~ Ал —— (оз а4) = ~ ), Ае — — (аз а4) = ~ Непосредственной проверкой убеждаемся в том, что ~А,~ ~ 0 при любом 3 = 1,6. Таким образом, любые два различных столбца матрицы А являются базисными и в рассматриваемом случае можно построить шесть базисных решений.
3Л. Основные утверждения линейного программирования 85 т т Пусть Ал = А4. Тогда Уь = (х4 хз), У = (хз я4) 6 05 -15 1 6 3 т и, согласно (3.5), базисное решение У4 = (2 3 0 0) . Аналогично находим и другие базисные решения: Уз — — (4 0 1 О), тэ се (5 О О - 3~2)', Ул = (О 6 -1 0)', У, = (О 5 О Ц', Уя = т Й (О 0 5 6) . При этом базисные решения Уы Уз, Уз, Ув явля1отся допустимыми базисными решениями. Если обратиться к геометрическому изображению множества С допустимых решений, то можно заметить (рис. 3.1), цто каждому допустимому базисному решению соответствует сноя вершина многоугольника ГО, являющегося границей множества С: первые две компоненты допустимого базисного ре'щения — координаты соответствующей вершины многоуголь44ика ГО. Таким образом, базисному решению У4 соответствует вершина Е, базисному решению Уз — вершина Н, базисному реШению Ул — вершина .Е, а базисному решению Уе — вершина Д, расположеннзл в начале координат.
-„ф 3.1. Основные утверждения линейного программирования 87 86 3. СИМИДЕКС-МЕТОД Прежде чем переходить к дальнейшим рассуждениям, напомним некоторые понятия: а) выпуклой комбинацией векторов Хь, й = 1, т, называют линейную комбинацию Л1Х1+...+Л Х этих векторов, коэффициенты Ль которой удовлетворяют условиям Ле > О, й=1,т, ~Ль=1; ' я=1 б) множество С С К" называют выпуклым, если наряду с любыми двумя элементами этого множества ему принадлежит и их произвольная выпуклая комбинация, т.е. для любых Х1, Хо б С и любого числа Л Е (О, Ц выполняется условие ЛХ1 + (1 — Л) Хз б С; (3.6) в) точку Хо выпуклого множества С называют крайней тонкой этого мнозкества, если не существует двух различных Х1, Хг б сл, ДлЯ котоРых Хо = ЛХ, + (1 — Л)Хз, 0 < Л < 1.
(3.7) Теорема 3.1. Если множество Я= (У ЕК~: АУ =В, У > Ол1) (3.8) допустимых решений задачи (2.11) линейного программирования в стандартной форме не является пустым, то зто множество содержит допустимое базисное решение. Пусть ае, й = 1,11', — столбцы матрицы А Е М1.ы(К) и т У = (У1 " У О ... 0) б Я вЂ” допустимое решение, т.е. аууу — — В; у1 >О, у'=1,в; у =О, у=я+1,М. (3.9) 1=1 Заметим, что для точек Х1, Хз б К~ множество всевозможных их выпуклых комбинаций представляет собой отрезок, соединяющий эти точки.
Определение крайней точки выпуклого множества можно сформулировать так: точка Х е С является крайней для множества С, если она не является внутренней ни для какого отрезка, целиком лежащего в С. Согласно определению допустимого базисного решения, нужно доказать, что среди неотрицательных координат вектора У содержится не более Ь ненулевых. В соответствии с принятыми допущениями Кя А = Ь.
Поэтому, если столбцы а;, 1 = 1, л, являются линейно независимыми, то рассматриваемое допустимое решение — допустимое базисное решение, так как в < Е. Если столбцы а, 1 = 1, л, являются линейно зависимыми, то существуют коэффициенты Л., такие, что ~~1 Лупу —— с1Ь, ~ !Л1! > О. 1=1 Последнее неравенство означает, что среди коэффициентов Л, 7' = 1, л, есть по крайней мере один ненулевой. Обозначив его ЛЫ выразим столбец ав матрицы А через столбцы а1, ..., аь 1, аь+1, ..., а,: 1ВЯ Используя это представление столбца ае, преобразуем первое из равенств (3.9) к следующему: ~~) (у — — ~уь)а = В. ь Всегда можно считать, что среди действительных чисел Л,, у = 1, л, есть хотя бы одно положительное, так как уравнения ~~1 Л а =с1ь и 1=1 ~(-Л )а = Оь ,-1 уя, уу — = пп'и —, Л„уе./ Л,' эквивалентны. Пусть,У С 1,1, 2,..., л) — совокупность индексов у, для которых Л > О.
Если номер й выбрать так, что 3.1. Основные утверждения линейного программирования 89 3. СИМПЛЕКС-МЕТОД 88 и, как следствие, то значения гл ч ут — ~ — ') уй~ .1 = 1~ в~ 3 Ф "1 1 Ь,) 0 у=й илн 1=в+1,Ю, будут неотрицательными. Таким образом, 11 — (у1 " уж) Е Я и допустимое решение У имеет строго положительных координат по крайней мере на одну меньше, чем допустимое решение У.
Продолжая рассуждать аналогичным образом, в конце концов придем к допустимому решению, у которого количество положительных координат не превосходит Ь = К8 А. ~в Теорема 3.2. Множество Ч (3.8) допустимых решений является выпуклым. ° Ф Пусть У1, Уэ 6 Я, т.е. АУь = В и Уь > Ол1, и = 1,2. Если 0 < Л < 1 и Х = ЛУ1 + (1 — Л) Уэ, то Х > Ол1 и АХ = ЛАУ1 + + (1 — Л)АУз = ЛВ+ (1 — Л)В = В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
