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