Турчак Л.И. Основы численных методов. Под ред. В.В.Щенникова (1987) (1095857), страница 33
Текст из файла (страница 33)
В заключение вернемся к рассмотренной ранее транспортной задаче (см. и. 2). На рис. 37 изображен многоугольник АВСВЕг' допустимых решений. Он получен как пересечение полу плоскостей, описываемых неравенствами (6.23) . Опорная прямая 1, соответствует уравнению (6.25) прп ~ = 22.9. Точка А пересечения опорной г г прямой с многоугольником решений дает минимум цедевой функ- Ю ции. При дальнейшем параллель- Р' .т, ном переносе этой прямой вверх р 37 О- ис.. ола ать яопу- можем попасть в точку Й (опор- стииых решений ная прямая 1,) и получить максимум целевой функции. 4.
Симплекс-метод. Рассмотренный геометрический метод решения задач линейного программирования достаточно прост и нагляден для случая двух и даже трех переменных. Для большего числа переменных применение геометрического метода становится невозможным. Правда, мы видели, что оптимальные значения целевой функции достигаются на границе области допустимых решений. Поэтому в случае и неизвестных (и~3) можно построить и-мерный многогранник решений, найти его вершины и вычислить значения целевой функции в этих точках. Наименьшее среди полученных значений можно принять за искомое, а координаты соответствую- 13Ф Гл. з.
методы Оптимизлции (6.28) ср + с1х1 + сзх~ + ° + сдхд щей нерп1ины — за оптимальные значепи51 проектных параметров. Однако решение задачи линейного программирования не так просто, как может показаться на первый взгляд. Слон1пость состоит в том, что количество проектных параметров в реальных задачах (особенно в экономических) может достигать сотен и даже тысяч. При этом число вершин многогранника 6 может быть настолько большим, что перебор вершин и вычисление в них значений целевой функции приведет к такому объему вычислений, который практически невозможно осуществить в течение разумного времени даже с помощью ЗВМ.
Одним из методов, позволяющих эффективно решать подобные задачи, причем с гораздо меньшим числом операций, является симплекс-метод. Симплексом называется простейший выпуклый многогранник при данном числе измерений. В частности, при и = 2 — произвольный треугольник, и = 3 — произвольный тетраэдр.' Идея симплекс-метода состоит в следующем. Примем в качестве начального приближения координаты некоторой вершины многогранника допустимых решений и найдем все ребра, выходящие из этой вершины. Двигаемся вдоль того ребра, по которому линейная целевая функция убывает. Приходим в новую вершину, находим все выходящие из нее ребра, двигаемся по одному из них и т. д.
В конце концов мы придем в такую вершину, движение из которой вдоль л1обого ребра приведет к возрастанию целевой функции. Следовательно, минимум достигнут, и координаты этой последней вершины принимаются в качестве оптимальных значений рассматриваемых проектпых параметров. Отметим, что (поскольку 5 — линейная функция, а многогранник выпуклый) данный вычислительный процесс сходится к решению задачи, причем за конечное число шагов 5с.
В данном случае их число порядка и, т. е. значительно меньше числа шагов в методе простого перебора вершин, где Й может быть порядка 2". Пусть задача линейного программирования состоит в том, что нужно найти такие неотрицательные значения проектных параметров х„х~, ..., х, которые минимизируют линейную целевую функцию э 4. ЗЛДЛЧП С ОГРЛННЧЕН11Я.11и системы линейных при заданн ых ограни чепиях в виде уравнений аих~ + а гх~ +... + а ~Х а~~х~ + а~гхг+ ° ° ° + а~,х = 62, (6.29) ° ° ° ° в ° а,х,+атх.,+...+ат„х„= й .
Если в качестве ограничений заданы неравенства, то их можно преобразовать в равенства путем введения дополнительных неотрпцательных переменных, которые называются балансовыми. Например, имея некоторое неравенство а,х, + а,х, +... + а„х„~ Ь, можно всегда ввести новую переменную х„+, ~ О такую, что после ее прибавления к левой части данного неравенства получим равенство а,х, + а,х, +...+а х +х +,= Ь. Будем считать, что все уравнения системы (6.29) линейно независимь1, т.
е. ни одно из нпх нельзя получить как линейную комоинацию других; В противном случае линейно зависпмь1е уравнения можем отбросить. И кроме того, эта система совместна, т. е. среди уравнений системы нет противоречивых. Ясно, что при этих предположениях число уравнений т меньше числа переменных и, поскольку при т = и система (6.29) имеет единственное решение, что исключает всякую оптимизацию; при т) п не выполняются сделанные выше предположения.
Выразим первые т переменных х„х„..., х через остальные с помощью уравнений (6.29): Х! р, + Ч1, т+1Хт+1 + д1, т+2Хт+2 + ° ° ° + Д1цХа1 Х2 р2+ д2, т+1Хт+1+ я2, т+2хт+2+ ° + я2лХа~ (6.30) Хт Рт + Дт, т+1хт~-1 + Дт, т+2хт+2 + ° ° + ЯтиХтц р;= О, г=1, 2, ..., т. Переменные х„х„..., х называются базисными, а вектор (х„х„..., х ) — базисом; х +„х +~, ..., х„— свободные переменные. Используя соотношения (6.30), можно выразить линейную целевую функцию (6,28) через свободные пере- Гл. 6. методы оптимизАции 198 менные: 1=~о+А+,хт,, +... + Й„х„. (6,31) Процесс оптимизации начнем с го (опорного) решения, например ниях свободных переменных.
Тогда некоторого начальнопри нулевых значеполучим О, ..., х„=О. (6.32) х,=р„..., х,.=р, х +,= При этом базисные переменные, вычисляемые по формулам (6.30), равны х = р, + 71,т+1х,1, ~=1, 2, ..., т. (6.34) (и Если все коэффициенты д; +, неотрицательны, то х +, можно увеличивать неограниченно; в этом случае не существует оптимального решения задачи. Однако на практике такие случаи, как правило, не встречаются. Обычно среди коэффициентов д~ +, имеются отрицатель- При этом целевая функция (6.31) принимает значение у<о> у Дальнейшее решение задачи симплекс-методом распадается на ряд этапов, заключающихся в том, что от одного решения нужно перейти к другому с таким условием, чтобы целевая функция не возрастала.
Это достигается выбором нового базиса и значений свободных переменных. Выясним, является ли опорное решение (6.32) оптимальным. Для этого проверим, можно ли уменьшить соответствующее этому решению значение целевой функции ~= 4 при изменении каждой свободной переменной. Поскольку х; ~ О, то мы можем лишь увеличивать их значения. Если коэффициенты д +„..., - д„в формуле (6,31)' неотрицательны, то при увеличении любой свободной переменной х +„..., х„целевая функция не может уменьшиться. В этом случае решение (6.32) окажется оптимальным. Пусть теперь среди коэффициентов формулы (6.31) хотя бы один отрицательный, например д +, ( О. Это означает, что при увеличении переменной х +, целевая функция уменьшается по сравнению со значением 4, соответствующим решению (6.32). Поэтому в качестве нового опорного выбирается решение прп'следующих значениях свободных параметров: х„,+, = х~.,1, х,„+, — — О, ..., х~ = О, (1) (6,33) У 4 ЗАДАЧИ С ОГРАНИЧЕНИЯМИ 199 ные, а это влечет за собой угрозу сделать некоторые переменные х; в (6.34) отрицательными ' из-за большого (1) значения хт+1 Следовательно, переменную х +, можно увеличивать лишь до тех пор, пока базисные переменные остаются неотрицательными.
Это и является условием (1) выбора значения хт+1 Его можно записать в виде р(+ д; +,х„+, ЪО, ~ = 1, 2, ..., т. (6.35) (1) Среди всех отрицательных коэффициентов д; +~ найдем наибольший по модулю. Пусть его значение равно ~, а соответствующее ему значение р; равно Р. Тогда из (6.35) получим максимально возможное значение пере(1) меннон х +, на данном шаге оптимизации: хт(., — — — РЯ (Р < О, Д < 0), и новое опорное решение запишем в виде Р Р х = р1 4'1,т+1 ° ° 1 хт = рт (7т,т-(-1 (6,36) хт+1= <~~ хт+2=0, ° ° .,хи=О. Новая целевая функция при этих значениях проектных параметров равна 1 = 4 — Г~т+1 —. (6.37) Полученное значение целевой функции (") меньше предыдущего, поскольку в данной формуле второй член правой части больше нуля (И +, < О, (~ < О, Р ~ 0). На этом заканчивается первый шаг оптимизации. Теперь нужно сделать второй шаг, используя аналогичную процедуру.
Для этого необходимо выбрать новый базис, принимая в качестве базисных переменных параметры х„..., х,. „х +,. После второго шага мы лиоо. найдем новые оптимальные значения переменных и соответствующее им значение целевой функции ((") = ~(", либо покажем, что решение (6.36) является оптимальным. В любом случае после конечного числа шагов мы придем к оптимальному решению. Еще раз подчеркнем, что в отличие от метода перебора симплекс-метод дает возможность вести поиск целенаправленно, уменьшая на каждом шаге значение целевой функции. В качестве примера, иллюстрирующего симплекс-метод, рассмотрим задачу об использовании ресурсов, гл.
6. мктодьг ОптимизАции 4х, + 5х, 300, 2х,+ х.~100; 2х,+Зх, -160. (6.38) Полная стоимость запланированной к производству про- дукции выражается формулой (6.39) ~= 10х, + 12х,. Таким образом, мы имеем задачу линейного программирования, которая состоит в определении оптимальных значений проектных параметров х„х., являющихся целымн неотрицательными числами, удовлетворяющих линейным неравенствам (6.38) и дающих максимальное значение линейной целевой функции (6.39). Вид сформулированной задачи не является каноническим, поскольку условия (6.38) имеют вид неравенств, а не уравнений. Как уже отмечалось выше, такая задача может быть сведена к канонической путем введения дополнительных переменных х„х„х~ по количеству ограничений-неравенств (6.38).
При этом выбирают эти переменные такими, чтобы при их прибавлении к левым частям соотношений (6.38) неравенства превращались в равенства. Тогда ограничения примут вид 4х, + 5х, + х. = 300, 2х, + х~+х.=100, 2х,+Зх,+х, =160, (6.40) 5. Задача о ресурсах. В распоряжении бригады имеются следующие ресурсы: 300 кг металла, 100 м' стекла, 160 чел.-ч (человеко-часов) рабочего времени.
Бригаде поручено изготовлять два наименования изделий — А и Б. Цена одного изделия А 10 р., для его изготовления необходимо 4 кг металла, 2 м' стекла и 2 чел.-ч рабочего времени. Цена одного изделия Б 12 р., для его изготовления необходимо 5 кг металла, 1 м' стекла и 3 чел.-ч рабочего времени. Треоуется так спланировать объем выпуска продукцип, чтобы ее стоимость была максимальной. Сначала сформулируем задачу математически. Обозначим через х, и х, количество изделий А и Б, которое необходимо запланировать (т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
