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