Хакимзянов Чубаров Воронина печатные лекции часть 2 (973558), страница 9
Текст из файла (страница 9)
21, б. Поскольку этаобласть является многоугольником, то линейная функция (5.6) можетдостигать своего максимального значения только в его вершинах a, b,c, d или e. Непосредственными вычислениями убеждаемся, что это будет вершина a. Таким образом, максимальное вознаграждение f = 790получается при плане перевозокx1 = 10;x2 = 0;x3 = 60,x4 = 50.(5.8)Ясно, что использованный здесь прием определения наибольшегозначения целевой функции путем сравнения ее значений во всех предварительно определенных вершинах многоугольной области Q допустимых значений трудно реализовать для задач со многими складами86и многими потребителями, поскольку в общем случае Q является многогранником, его граница представляет собой довольно сложный объект в многомерном пространстве, координаты вершин которого определить не просто.
На следующем примере попытаемся пояснить какможно обобщить предложенный метод решения задачи.Пример 5.2. Со складов I и II с запасами a1 = 70, a2 = 50 потребителям A и B с потребностями b1 = 80 и b2 = 60 доставляется некотораяпродукция, при этом единица привезенной со склада I продукции продается в пункте A за 8 у. е., а в пункте B — за 5 у.
е. Продукция сосклада II продается в пункте A за 6 у. е., а в пункте B — за 4 у. е. (см.рис. 22, а). Необходимо определить оптимальный (с точки зрения продавцов) план перевозок (x1 , x2 , x3 , x4 ), при котором будет достигнутамаксимальная выгода от продаж:f = 8x1 + 4x2 + 5x3 + 6x4 → max .(5.9)Область допустимых значений переменных xi (i = 1, 2, 3, 4) задаетсяв этой задаче следующей системой ограничений:x1 + x4 ≤ 80,x2 + x3 ≤ 60,(неполное удовлетворениепотребителей)AIx1708x3706504x380x4505x286x10IIx4IIAI80(5.10)B60III20аx25u4v0B60бРис. 22.
Схемы постановки задач: а — о получении максимальнойвыгоды от продаж; б — задачи с фиктивным складом87x1 + x3 = 70,x2 + x4 = 50,(полный вывоззапасов )(5.11)xi ≥ 0,i = 1, 2, 3, 4.(неотрицательностьобъемов продаж)(5.12)Решение этой задачи можно получить также, как и в предыдущемпримере, переходом с помощью равенств (5.5) к целевой функцииf (x1 , x2 ) = 650 + 3x1 − 2x2 ,(5.13)которую требуется максимизировать на пятиугольнике, изображенномна рис. 21, б. Вычисляя значения функции (5.13) в вершинах этого многоугольника, убеждаемся, что максимальное значение f = 780 достигается в вершине c, что соответствует оптимальному решениюx1 = 70;x2 = 40;x3 = 0,x4 = 10.(5.14)Приведем теперь алгоритм, которым можно воспользоваться для решения задачи в общем случае большого числа поставщиков и потребителей. Рассмотренные в примерах 5.1, 5.2 задачи называются открытыми по той причине, что в них не соблюдается баланс запасови потребностей: наблюдается дефицит, нехватка запасов.
В общем алгоритме вначале происходит переход к закрытой задаче, в которой этотбаланс соблюдается. В нашей задаче для этого достаточно ввести фиктивный склад III с запасом продукции a3 = 20, равным дефициту (нарис. 22, б фиктивный склад изображен прямоугольником с штриховымконтуром), и фиктивные объемы u и v вывоза продукции с этого склада.Считается, что продукция с этого склада «продается» в пунктах потребления по цене 0 у. е., поскольку этого товара фактически не существует.Тогда целевая функция будет иметь тот же вид (5.9), а система четырехограничений (5.10), (5.11) трансформируется в систему пяти уравненийотносительно шести неизвестных (см.
обозначения рис. 22, б):x1 + x4 + u = 80,x2 + x3 + v = 60,x1 + x3 = 70,x2 + x4 = 50,u + v = 20.(полное удовлетворениепотребителей)(полныйвывоззапасов )(5.15)Требуется среди неотрицательных решений системы уравнений (5.15)найти то, которое доставляет максимальное значение линейной функции (5.9).88Если бы у нас была закрытая задача с m складами и n потребителями, то система типа (5.15) содержала бы (m + n) уравнений относительно (mn) неизвестных. Оказывается, что такая система может бытьприведена к виду, в котором (m + n − 1) неизвестных выражаются черезостальные, причем свободные члены этих выражений неотрицательны.В нашем случае мы можем на основе системы (5.15) написать, например, следующие выражения:x1 = 10 + x2 + v,x3 = 60 − x2 − v,x4 = 50 − x2 ,u = 20 − v.(5.16)Неизвестные x1 , x3 , x4 , u, находящиеся в левой части системы (5.16),называются базисными, остальные — x2 и v — свободными.
С учетомвыражений (5.16) целевую функцию (5.9) также можно представитьчерез свободные переменные:f = 680 + x2 + 3v.(5.17)Полагая теперь все свободные переменные равными нулюx2 = 0,v = 0,(5.18)получаем значения базисных переменныхx1 = 10,x3 = 60,x4 = 50,u = 20(5.19)и значение f = 680. Полученное допустимое решение (5.18), (5.19) служит начальным приближением при поиске оптимального решения с помощью итерационного симплекс-метода [28].Первое итерационное приближение ищется путем перехода к другим базисным переменным с таким расчетом, чтобы значение функции f увеличилось.
Из выражения (5.17) следует, что значение f можно увеличить, если увеличить значения свободных переменных x2 и v.В простейшем варианте симплекс-метода увеличивают значение однойиз свободных переменных, а остальные не меняют. Оставим v = 0, а значение x2 увеличим, но так, чтобы значения базисных переменных нестали отрицательными числами. Из выражений (5.16) следует, что значение x2 может быть увеличено до 50 (но не более, иначе x4 станет89отрицательным).
Итак, возьмем x2 = 50. Тогда получим новое допустимое решениеx1 = 60,x2 = 50,x3 = 10,u = 20,x4 = 0,v = 0.(5.20)Этому решению соответствуют базисные переменные x1 , x2 , x3 , u (положительные компоненты решения (5.20)) и свободные переменные x4 ,v (нулевые компоненты решения (5.20)), при этом f = 730, т. е. значениецелевой функции на решении (5.20) действительно стало больше, чемна начальном приближении (5.18), (5.19).Для поиска следующего итерационного приближения нужно на основе системы (5.15) выписать выражения новых базисных переменныхчерез новые свободные:x1 = 60 − x4 + v,x2 = 50 − x4 ,x3 = 10 + x4 − v,u = 20 − v(5.21)и новое выражение для целевой функции (5.9):f = 730 − x4 + 3v.(5.22)Из последнего выражения следует, что увеличить значение функции fмы можем за счет увеличения только свободной переменной v.
Поэтому,оставив x4 = 0, из системы (5.21) получаем, что максимальным значением v может быть v = 10 (не более, иначе x3 станет отрицательным).В результате получаем новое итерационное приближениеx1 = 70,x2 = 50,u = 10,v = 10,x3 = 0,x4 = 0(5.23)и соответствующее ему значение f = 760.Для новых базисных переменных x1 , x2 , u, v и целевой функцииполучаем выраженияx1 = 70 − x3 ,x2 = 50 − x4 ,(5.24)u = 10 − x4 + x3 ,v = 10 + x4 − x3 ,f = 760 − 3x3 + 2x4 .(5.25)Видно, что значение целевой функции можно увеличить до f = 780,заменив в решении (5.23) x4 = 0 на положительное значение x4 = 1090(больше нельзя, так как при x4 > 10 формулы (5.24) дают отрицательное значение для переменной u).
Соответствующее допустимое решениеимеет видx1 = 70,x2 = 40,x4 = 10,v = 20,x3 = 0,u = 0.(5.26)Перейдем к следующему шагу итерационного процесса. Для новыхбазисных переменных x1 , x2 , x4 , v имеем выраженияx1 = 70 − x3 ,x2 = 40 + u − x3 ,x4 = 10 − u + x3 ,v = 20 − u,(5.27)а целевая функция запишется через свободные переменные какf = 780 − x3 − 2u.(5.28)Отличие от предыдущих итерационных шагов заключается в том,что теперь увеличение значений свободных переменных x3 и u ведет нек увеличению, а к уменьшению значений целевой функции, т. е. максимальное значение f может достигаться только при x3 = 0, u = 0.
Темсамым, решение (5.26) окончательное, и на этом шаге итерационныйпроцесс завершается. Значение v = 20 фиктивной переменной v означает, что в пункте B будет наблюдаться недопоставка соответствующегообъема.Заметим, что полученное на последнем шаге решение (5.26) совпало с решением (5.14), полученным (благодаря простоте рассматриваемой задачи) непосредственно, в «лоб». Будет ли и в общем случаесимплекс-метод сходиться к оптимальному решению, и получим ли мыоптимальное решение за конечное число шагов или это бесконечныйитерационный процесс? При решении нашей задачи мы взяли в качестве начального приближения допустимое решение (5.18), (5.19).
А есливзять другое, придем ли мы опять к тому же оптимальному решениюили выйдем на другое? Получим ли результат за разумное время и непроизойдет ли «зацикливания» алгоритма с периодическим повторением промежуточных решений без выхода на окончательное, оптимальноерешение? А как влияют на сходимость ошибки округления при вычислениях на компьютере? Хватит ли оперативной памяти для размещениявсех данных большой задачи? Таким образом, на рассмотренном примере мы видим, что при разработке алгоритмов численного решения91сложных задач возникает множество специфичных вопросов и проблем,требующих глубокого изучения. Эти и подобные проблемы рассматриваются в обязательных курсах «Вычислительные методы линейной алгебры», «Методы вычислений», «Исследование операций» и др.5.2.
В рассмотренных задачах имелась одна целевая функция, которую требовалось максимизировать на допустимом множестве решений. На практике очень часто возникают многокритериальные задачи:имеетсявектор-функцияцелей(критериев,показателей)f (x) = (f1 (x), f2 (x), . . . , fn (x)) и требуется выбрать наиболее выгодныйвариант решения x = (x1 , x2 , . . . , xl ) из области Q допустимых решений, на котором все критерии достигают своего максимального значения. В большинстве случаев невозможно указать решение, приводящеек оптимальным значениям всех критериев одновременно, так как онизачастую соответствуют достижению противоречивых целей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
