Ф.П. Васильев - Методы оптимизации (1125241), страница 29
Текст из файла (страница 29)
Известно, что средняя урожайность г-й культуры на знм участке составляет а! центнеров с гектара, а прибыль за один центнер г-й культуры составляет с! рублей. Требуется определить, каку>о площадь на каждом участке следует отвести под каждую из культур, чтобы получить максимальную прибыль, если по плану должно быть собрано не менее й! центнеров 4-й культуры. Обозначим через и! площадь, которую планируется отвести под !'-ю культуру на >'-м участке.
Гогда и,,+...+из=6,, >'=1,,г. (8) 0>кидаемый средний урожай г-й культуры со всех участков равен а>, и>, +... ... + амин, центнеров. Поскольку согласно плану должно быть произведено не менее й! центнеров г-й культуры, то (9) Ожидаемая прибыль за урожай >-й культуры равна с>(а,и>, +... + а, иы), а за урожай всех культур— г с,(а>,и„+... + ахим) = 1(и). (10) '= ! Таким образом, приходим к задаче максимизации функции (10) (или минимизации функции — 7'(и)) при условиях (8), (9) и естественных ограниче- ниях и! > О, г = 1!..., р, >' = 1,..., г. Если умножить соотношения (9) на — 1 и переменные (ив) переобозначить через х',..., х", то придем к задаче вида (1) — (4). Транспортная задача.
Пусть имеется г карьеров, где добывается песок, и р потребителей песка (например, кирпичные заводы). В (-м'карьере ежесуточно добывается а! тонн песка, а т'-му потребителю ежесуточно требуется бз тонн песка. Пусть с! — стоимость перевозки одной тонны песка с г-го карьера >'-му потребителю. Требуется составить план перевозок песка так, чтобы общая стоимость перевозок была минимальной. Обозначим через ии планируемое количество тонн песка из г-го карьера заму потребителю, Тогда с г-го карьера будет вывезено (11) тонн песка, >'-му потребителю доставлено тонн песка, а стоимость перевозок будет равна и! > О, г = 1, ..., Е >' = 1, , р.
(14) В результате получили задачу минимизации функции (13) при условиях (11), (12), (14), которая, очевидно, является частным случаем общей задачи линеиного программирования (1) †(4). К задачам типа (1) †(4) сводятся также и многие другие прикладные задачи технико-экономического содержания, Следует заметить, что приведенные выше примеры задач линейного программирования, вообще говоря, представляют лишь приближенную, упрощенную математическую модель реальных задач. Вполне может оказаться, что принятая математическая модель, обычно составляемая на основе приближенных данных о реальном моделируемом явлении (объекте, процессе), не охватывает какие-либо важные существенные сторонь! исследуемого явления и приводит к результатам, существенно расходящимся с реальностью.
В этом случае математическая модель должна быть изменена, доработана с учетом вновь поступившей информации, а получаемые при анализе совершенствованной модели данные должны снова и снова критически сопоставляться с реальными данными и использоваться для выяснения границ применимости модели. Математическая модель лишь при высокой степени адекватности моделируемому явлению может быть использована для более глубокого анализа явления и проникновения в его сущность, для выработки целенаправленного управления. Практика показала, что линейные модели, приводящие к задачам вида (1)-(4), вполне пригодны для исследования многих реальных явлений, или для их анализа могут быть использованы теория и методы линейного программирования.
Линейное программирование является одним из наиболее изученных разделов теории экстремальных задач с достаточно богатым арсеналом методов. Ниже мы увидим, что задачи линейного программирования нередко используются в качестве вспомогательных во многих методах решения более сложных нелинейных задач минимизации, 3. Из общей задачи линейного программирования обычно выделяют так называемую каноническую задачу: 7(х) = (с, х) — ! 1п1; х Е Х = (х Е Е": х > О, Ах = 6), (15) получающуюся из задачи (5), (6) при >и = О, 1', = (1, 2,..., и). Задача (15) привлекательна тем, что при ее исследовании, разработке методов ее решения можно пользоваться хорошо известной из линейной алгебры теорией систем линейных' алгебраических уравнений.
Замечательно также и то, что методы, созданные для решения канонической задачи (15), нетрудно модифицировать и применять для решения общей задачи линейного программирования (5), (6). Дело в том, что задача (5), (6) оказывается сама равносильна некоторой канонической задаче.
Покажем это. 4 Ф.п. Васильев 98 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Для того, чтобы легче было понять последующие построения, прежде всего заметим, что любое действительное число а можно представить в виде разности двух неотрицательных чисел: а = а+ — а, где ач = шах~О; а) > О, а =шах(0; — а) > О. Отсюда следует, что вектор х, =(х,',..., хг ) можно представить в виде разности неотрицательных векторов: х,= з, — гг, з, =!пах(0; х,) >О, гг=шах(0; — х,) >О, (16) 1 где операция взятия максимума проводится покоординатно: г, = (г,, ..., з,"'), з,' = шах(0; х,'), з, =(л,',..., згч), 4 = !пах(0; — х,'), У =1,..., пг. Далее, заметим, что ограничения Ах < 6 типа неравенств можно записать в виде ограничений типа равенств Ах + е = 6, добавив сюда неравенство е > 0: ясно, что точка х будет решением неравенства Ах < 6 тогда и только тогда, когда (х, е) — решение системы Ах+ е = 6, е > О.
Отсюда следует, что вводя переменную е = 6, — Апх, — Аых, > О, (17) ограничение А„х, + А „х < 6, с учетом (16) можно представить в равносильном виде А и тч + А м хг + е = А и х, + А н з, + ( — А н) гг + е = Ь„е )~ 0 Ограничение Аг,х, + А„т = 6, с учетом (16) запишем в виде Аг,х, + Агггг+ ( — Агг)аз + Ое = Ьг. Учитывая эти соображения, в пространстве переменных ю = (хп зп г„е), х Е Е'г г Е Я'ч, з, Е Еъ, е Е Е"', рассмотрим следующую каноническую 1 задачу: д(ге) = (с„х,) + (сг, з,) + ( — сг, гг) + (О, е) -+ !п1, гв Е Иг, (18) И' = (ш = (х„хп хг1 е): Апх, + Аыг, + ( — А1г)з, + 1е = 6„ А„х, + А„г, + ( — Агг)зг = Ь„гв > О), (19) где 1 — единичная матрица размера т, х тп Оказываетсн, задачи (5), (6) и (18), (19) обе одновременно имеют или не имеют решение, причем, зная какое-либо решение одной из этих задач, нетрудно получить решение другой задачи. Точнее, справедлива следующая Т е о р е м а 1. Задачи (5), (6) и (18), (19) равносильньь т.
в.: 11 множества Х и Иг оба пусты или нгпусты одновременно; 2) если Х ф О, И' ф О, то ?. = д„, гдв 7; = !и! 7(и), д, = 1п1 д(г6); 3) множества решений Х„= (и Е Х; 1(х) = 1'„), И'", = (ге Е И~; д(ге) = ,) этих задач оба пусты или нвпусты одновременно, причем если х, = (х „т „) Е Х„, то и„= (хи, з1„з„, е,) Е И'„, где аы = |пах(0; х „), Д о к а з а т е л ь с т в о. Учитывая связи (16),(1?) между переменными х„хг, зп х„е и определения (6), (19) множеств Х, И' заключаем, что если точка х = (х„х ) Е Х, то ш = гв(х) = (хп з! — — шах(0; х,), зг = =!пах(0; — х ), и=6,— Апх,— Анх) е Иг. И обратно, если ге=(х„зп а„е)е е Иг, то х = х(гв) = (х„х, = г, — гг) е Х.
Отсюда ясно, что лиоо оба множе- $ !. ПОСТАНОВКА ЗАДАЧИ 99 ства Х и И' пусты, либо оба непусты одновременно. Данее, из определений функций 1(х), д(и), ю(х), х(гл) следуют тождества Г(х) = д(ге(х)), д(гв) = ?(х(и)), гх, и. (20) 1(х) = (с, х) — > !и1, х Е Х = [х > 0; Ах < 6), (21) получающуюся из общей задачи (5), (6) при т = в, 1 =(1, 2,..., и). Это объясняется тем, что в приложениях большое число лйнейных математических моделей изначально естественным образом записывается в виде задачи (21)(см., например, задачу (7)), Следует также отметить, что задача (21) весьма удобна для геометрических интерпретаций, делающих наглядными многие понятия и методы линейного программирования.
Если ввести дополнительные переменные е = (е', , е™) посредством соотношений е=Ь-Ах, е>0, (22) то задачу (21) в пространстве Е + переменных з =(х, е) можно записать в канонической форме: д(з)=(а,з)- !п1, зЕ4 (23) В=(з=(х,е)>0, Сз=Ах+1 е=Ь), где д = (с, О) Е Я" ' ", С = (А, 1„), 1 — единичная матрица размера т х т. Из теоремы 1 следует, что задачи (21), (23) равносильны, и зная решение х„Е Х„задачи (21) по формуле (22) нетрудно пааучить решение задачи (23) , = (х„е, = 6 — А х,), и обратно, если з, = (х„, е„) Е л„то х, Е Х„.
С другой стороны, каноническую задачу (15) нетрудно записать в форме сновной задачи. В самом деле, если ограничении типа равенств Ах = 6 аменить на равносильную систему двух неравенств: А х < 6, А х > 6, то г о з 4 ДопУстим, что 7'„= — со. Тогда сУществУет последовательность (хь): хь Е е Х, й =1,2,..., такая, что (1(хь))- 1, = — оо. Положим и, =и(х„), й = = 1,2,....
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
