Турчак Л.И. Основы численных методов. Под ред. В.В.Щенникова (1987) (1095857), страница 32
Текст из файла (страница 32)
До спх пор прп рассмотрении задач оптимизации мы пе делали никаких предположений о характере целевой функции и виде ограничений. Важным разделом математического программирования является линейное проерал1ла~ровпние, изучающее задачи оптимизации, в которых целевая функция является линейной функцией проектных параметров, а ограничения задаются в виде линейных уравнений п неравенств. Стандартная (каноническая) постановка задачп линейного программирования формулируется следующим образом: найти значения переменных х„х„..., х„, которые: 1) удовлетворяют системе линейных уравнений ПИХг + П~гхг +... + Пг„Х„= бгг Пггхг+ П гХг+... + Пг„Х = Ог, (6Л5) Ятгхг+ П»;гхг+ ° ° ° + П Х11 = Оп ~ Гл О т!Гтодьт опти~шзлцип 100 2) являются ноотрпцательпымп, т. е.
(6.16) 3) обеспечивают наименьшее значенпе линейной целевой функции 1(хо х2~ ° ° ~ хп) = со+ с1х~ + с2х2 +... + спхя. (6.17) Ма галан Вяаа первч» ~ вт р ~я ~ ~ в~таз Первая Вторая 1.10 0,70 0.80 1.00 0З0 1."0 Р е ш е н и е. Обозначим через х„х,, х, количество товара, который нужно деставить с первой базы соответственно в первый, второй и третий магазины, а через х„х„-, х, количество товара, который нужно доставить со второй базы в те же магазины. Эти значения в соответствии с исходными данными должны удовлетворять следующим условиям: х, +х,+х.
= 12, х,+х„.+х,. = 15, х,+х,=8, х +х;=9, х,+х, =10, (6.18) Всякое решение системы уравнений (6.15), удовлетворяющее системе неравенств (6.16), называется допусти.- мым реисепием. Допустимое решение, которое минимизирует целевую функцию (6.17), называется оптимал,иным решением. 1'ассмотрим пример задачи линейного программирования (транспортную задачу). Пример. Автобаза обслуживает три овощных магазина, причем товар доставляется в магазипы из двух плодоовощных баз. Нужно спланировать перевозки так, чтобы их общая стоимость была минимальпой. Введем исходные данные. Ежедневно вывозится с первой базы 12 т товара, со второй 15 т.
Прп зтом завозится в первый магазин 8 т, во второй 9 т, в третий 10 т. Стоимость перевозки 1 т товара (в рублях) с баз в магазины дается следующей таблицей: Я 4. ЗАДАс1И С ОГРАНИЧЕНИЯ»МИ ".91 Первые два уравнения этой системы описывают количество товара, которое иеооходпмо вывезти с первой и второй баз, а три последних — сколько нужно завезти товара в каждый магазин. К данной системе уравнений нужно добавить систему неравенств х» ~ О, 1 = 1, 2, ..., 6, (6.19)' которая означает, что товар обратно с магазинов на базы не вывозится, Общая стоимость перевозок с учетом при- веденных в таблице расценок выразится формулой ~ = 0.8х, + 1.1х.
+ 0,9х. + х, + 0.7х, + 1.2х,. (6.20) Таким образом, мы пришли к тиипчноп задаче линейного программирования: найти оптпмальные значения проектных параметров х» (1 = 1, 2, ..., 6), удовлетворяющих условиям (6.18), (6.19) и минимизирующих обшую стоимость перевозок (6.20). Из анализа системы уравнений (6.18) следует, что только первые четыре уравнения являются независимыми, а последнее можно получить из ~Их (путем слотенпя первого и второго уравнений и вычитания из этой суммы третього и четвертого уравнений). Поэтому фактически имеем систему х, +х2+хз='12, х, + х, + х. = 15, х,+х; =8, х2+ х5 9 ° (6.21) х,=12 — х,— х„ х,=8 — х„ х,=9 — х„ хе = х»+ х~ — 2.
(6,22)' Поскольку в соответствии с (6.19) все проектные параметры должйы быть неотрицательны, то с учетом (6.22) Число неизвестных на два больше числа уравнений, поэтому выразим через х, и х, все остальные неизвестные. Получим Гл. 6. метопы оптимизАции И2 получим следующу1о систему неравенств: х,~О, х,>0, 12 — х,— х,~О, 8 — х, ~0, 9 — х,~0, х,+х,— 2~0. (6.23)' Эти неравенства можно записать в более компактном виде: 0<х, <8, О~х,~9, 2<х,+х,(12. (624) Данная система неравенств описывает все допустимые решения рассматриваемой задачи.
Среди всех допустимых значений свободных параметров х, и Х', ну1кно найти оптимальные, минимизирующие целевую функцию ~. Формула (6.20) для иее с учетоъ1 соотношений (6,22) принимает вид ~ = 22.7 + 0.1х, + 0.7х,. (6.25)' Отсюда следует, что стоимость перевозок растет с увеличением значений хо х2', поэтому нужно взять их наименьшие допустимые значения. В соответствии с (6.24) Рис.
35. Схема перевозок х,+х,> 2; примем х, +х, =2. Исключая один из параметров, например х„получим х, = 2 — х,, Тогда / = 24Л вЂ” 0.6х,. Очевидно, что стоимость перевозок 1 будет минимальной, если величина х, примет наиболыпее зпачеппе в рамках сделанного ограничения (х,+х~=2). Таким оптимальным будет значение х, = 2. Тогда х, = О, а опти- 5 4.
ЗАДАЧИ С ОГРАНИЧЕНИЯМИ 193 мальные значения остальных проектных параметров можно найти по формулам (6.22): хю = 10, х, = 6, хю = 9, х, =О. В этом случае минимальная оощая стоимость перевозок / равна 22.9 р. На рис. 35 показана схема доставки товаров, соответствующая полученному решению. Числа указывают количество товара (в тоннах).
3. Геометрический метод. Областью решения линейного неравенства с двумя переменными пю + а~х~ + п~хю ~~ 0 (6.26) Рис, 36. Выпуклая (С0 и невыпуклая (бю) области Областью решений системы неравенств является пересечение конечного числа полуплоскостей, описываемых каждым отдельным неравенством.
Это пересечение представляет собой многоугольную область 6, Она может быть как ограниченной, так и неограниченной и даже пустой (если система неравенств противоречива) . Область решений С обладает важным свойством выпуклости. Область называется выпуклой, если произвольные две ее точки можно соединить отрезком, целиком принадлежащим данной области. На рис. 36 показаны выпуклая область С~ и певыпуклая область С,.
В области С, две ее произвольные точки Л, и В, можно соединить отрезком, все точки которого принадлежат обла- является полуплоскость. Для того чтобы определить, какая из двух полуплоскостей соответствует этому неравенству, нужно привести его к виду х, > Йх, + о илп х, < Йх, + о. Тогда искомая полуплоскость в первом случае расположена выше прямой а, + а,х, + а,х, = О, во втором — ниже нее. Если а, = О, то неравенство (6.26) имеет вид аю+ а,х, > 0; в этом случае получим либо х, ~ Ь вЂ” правую полуплоскость, либо х, < Ь вЂ” левую полуплоскость. Гл.
6. мктоды ОптимизАции с,+ с~~,+ с,т,=С. (6.27) При параллельном переносе этой прямой в положительном направлении вектора нормали п(со с,) линейная функция ~ будет возрастать, а при переносе прямой в противоположном направлении — убывать. Предположим, что прямая, записанная в виде (6.27), при параллельном переносе в положительном направлении вектора и первый раз встретится с областью допустимых решений С в некоторой ее вершине, при этом значение целевой функции равно С„и прямая становится опорной.
Тогда значение С, будет минимальным, поскольку дальнейшее движение прямой в том же направлении приведет к увеличению значения ~, сти С,. В области С~ можно выбрать такие две ее точки А~ и В„что не все точки отрезка А,В, принадлежат области 62. Опорной прямой называется прямая, которая имеет с ооластью по крайней мере одну общую точку, при этом вся область расположена по одну сторону от этой прямой. На рис. 36 показаны две опорные прямые 1, и 1~, т.
е. в данном случае опорные прямые проходят соответственно через вершину многоугольника и через одну нз его сторон. Аналогично можно дать геометрическую интерпретацию системы неравенств с тремя переменными. В этом случае каждое неравенство описывает полупространство, а вся система — пересечение полупространств, т. е. Многогранник, который также обладает свойством выпуклости. Здесь опорная плоскость проходит через вершину, ребро или грань многогранной области.
Основываясь на введенных понятиях, рассмотрим геометрический метод решения задачи линейного программирования. Пусть задапы линейная целевая функция ~ = с, + с,х, + с,х, двух независимых переменных, а также некоторая совместная система линейных неравенств, описывающих область решений О. Требуется среди допустимых решений (х„т,) е= С найти такое, при котором линейная целевая функция ~ принимает наименьшее значение.
Положим функцию / равной некоторому постоянному значению С: ~=с.+ с,х, + с..х. = С. Это значение достигается в точках прямой, удовлетворяющих уравнению у 4 злдАчи с ОГРАничениями 195 Если в задаче оптимизации нас интересует максимальное значение целевой функции, то параллельный перенос прямой (6,27) осуществляется в направлении, противоположном и, пока она не станет опорной. Тогда вершина многоугольника С, через которую проходит опорная прямая, будет соответствовать максимуму функции ~. При дальнейшем переносе прямой целевая функция будет убывать.
Таким образом, оптимизация линейной целевой функции на многоугольнике допустимых решений происходит в точках пересечения этого многоугольника с опорными прямыми, соответствующими данной. целевой функции. При этом пересечение может быть в одной точке (в вершине многоугольника) либо в бесконечном множестве точек (на ребре многоугольника) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
