Файл: Арутюнян А.Г. Применение математических методов и ЭВМ в народном хозяйстве.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.07.2024
Просмотров: 193
Скачиваний: 0
переменных, которые следует принять в качестве парамет ров управления. При выборе переменных желательно обес печить возможно более простой вид условий и показателя качества. От удачного выбора параметров управления су щественно зависит трудоемкость решения задачи” (см. (92],
стр. 18).
После выбора переменных проводится формализация— математическое моделирование словесно поставленной за дачи. Процесс формализации представляет собой запись функциональных соотношений между переменными и ма тематическое выражение показателя качества. При этом каждое ограничение должно точно отражать соответст вующее условие, сформулированное при словесной поста новке задачи.
При построении математических моделей исследуемых явлений, особенно в тех случаях, когда эти явления изу чаются впервые, не всегда удается сразу сформулировать и записать все условия, которые должны ограничивать область изменений переменных задач.
Следовательно, успех решения реальных задач во мно гом зависит от результатов совместных усилий практиковпоставщиков задач и специалистов по математическому моделированию.
Взависимости от конкретной формы и сложности ма тематической задачи для ее решения либо выбирается один из известных методов, либо разрабатывается новый метод. Оказывается, что не для каждой модели можно разрабо тать конечный или сходящийся метод.
Поэтому при моделировании практических задач не обходимо учесть возможности практической реализуемости разрабатываемой методики решения этих задач. Принимая это положение за основу, в настоящем разделе изучаются задачи математического программирования специальных видов.
Впервой главе рассматриваются задачи параметриче ского линейного программирования, предлагаются алго ритмы решения поставленных задач и приводятся численные примеры. Во второй главе рассматриваются две задачи не линейного программирования (предназначенные для управ ления непрерывным технологическим процессом), не вхо-
221
дящие в класс задач выпуклого программирования, но обладающие свойством выпуклости множества оптималь ных точек. Предлагается также способ применения мето дов параметрического линейного программирования для управления технологическим процессом.
Г Л А В А I
АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ ПАРАМЕТРИЧЕСКОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Формирование целого ряда практических задач по оптимальному проектированию различных систем и их даль нейшему управлению, по планированию отдельных звеньев народного хозяйства и т. п., приводит к линейным мате матическим моделям, где исходные данные не являются абсолютно точными, а в некоторой степени приближенными. Кроме того, если разработанную линейную модель, соот ветствующую определенному физическому или экономи ческому явлению, рассматривать в динамике, то со временем исходные данные могут подвергаться*изменению вследст вие самых разнообразных факторов. Если изменение исход ных данных носит случайный характер, то разработанная линейная модель входит в класс задач стохастического линейного программирования. Если же заранее известна закономерность изменения исходных данных (например, исходные данные являются функциями, зависящими от не которого параметра), то разработанная модель входит в класс задач параметрического линейного программирова ния (ПЛП). Задачи ПЛП в своих простейших постановках впервые изучались С. Гассом и Т. Саати (см. [20]). Ком пактное .описание алгоритмов некоторых специальных за дач ПЛП приведено в книге [22].
В настоящей главе рассматриваются несколько частных задач, которые расширяют круг задач ПЛП и отличаются от уже изученных тем, что в них участвуют векторные параметры. Необходимость изучения подобных задач обу-
222
улавливается тем, что в большинстве случаев в практике на исходные данные влияет не один фактор, а целый ряд различных факторов.
В настоящее время пока задачи ПЛП рассматриваются только в аспекте их практической применяемости при за кономерном изменении исходных данных. Результаты изуче ния параметрических задач показывают, что не при всяких значениях исходных данных задача линейного программи рования устойчива. Оказывается, что область изменения исходных данных разбивается на подобласти так, что во многих случаях даже на соседних подобластях задача ли нейного программирования ведет себя с совершенно раз личной чувствительностью. Простейший пример, показы вающий этот факт, приведен в [22J. Может оказаться, что даже незначительное изменение значений исходных данных приведет к достаточно большому изменению значения це левой функции, а в некоторых случаях и к неразрешимости поставленной задачи. Выявление таких ситуаций имеет большое практическое значение. В этом можно убедиться на следующем простом примере. Предположим, что для составления оптимального (в определенном смысле) плана производственного цеха разработана линейная экономико математическая модель, в которой в качестве исходных данных участвуют хрономегражные данные производитель ностей различных видов оборудования. Может оказаться, что поставленная численная задача или вообще неразре шима (а это противоречит тому, что практически данный цех выполняет определенный, не обязательно оптималь ный, план), или же полученный в результате решения этой задачи план практически не пригоден. Причиной таких ситуаций может быть, например, неточность исходных дан ных (из-за шкал показаний измерительных приборов, или накоплений ошибок при расчетах). Кроме этого, при реше нии численных задач на ЭВМ вследствие ограниченности разрядной сетки ЭВМ в процессе вычислений накапливают ся ошибки, в результате чего полученное решение будет соответствовать не исходной задаче, а в некоторой степени искаженной. Такие ситуации наиболее характерны при при менении конечных (точных) методов линейного програм мирования. Несомненно в таких случаях у производствен-
223
ников будет |
появляться |
чувство подозрения |
и недоверия |
к точности |
достижений |
методов линейного |
программиро |
вания. А всестороннее |
изучение данной практической за |
||
дачи с применением аппарата Ш 1П поможет |
корректиро |
||
вать исходные данные и уточнить модель.
Наконец практика показывает, что область приме нения ПЛП ежедневно расширяется, и ПЛП, с первого взгляда кажущееся уже завершенным, является одним из самых перспективных направлений линейного программи рования.
§ 1. Постановка некоторых задач параметрического линейного программирования
Решение задачи ПЛП в своей самой общей постановке требует чрезмерю сложной схемы вычислительной проце дуры. Следовательно, с практической точки зрения общая задача ПЛП вряд ли найдет применение. Даже в случае численного параметра общая задача ПЛП при определен ных ограничениях решается нелегко. Например, в случае аналитических функций одного (численного) параметра изучение задачи ПЛП на конечном отрезке изменения пара метра требует громоздкого объема вычислений (см. [84]). Это в первую очередь объясняется тем, что отрезки изме
нения параметра, |
на которых задача разрешима, вооб |
ще говоря, могут |
быть изолированными, что приводит |
к большим трудностям в изучении свойств поставленной задачи.
Здесь рассматриваются специальные виды задач ПЛП характер которых позволяет разработать сравнительно простые алгоритмы их решения.
При изучении основных свойств решений и поведения целевой функции задача ПЛП рассматривается в сравни тельно общей форме записи. В общей задаче ПЛП ком поненты векторов условий предполагаются постоянными. Задача ПЛП, в которой один (и только один) из векторов условий зависит от параметра, исследуется отдельно.
1°. Постановка общей задача и определения. Рас смотрим следующую задачу ПЛП. Для каждой пары векто-
224
ров |
Л — (>.„ Х2..... хк), |
|
(i,,..., }iL) построить функцию |
|||
F (Л,"М) = _т ах |
|
|
Щ ~ т а х |
£ ь (М)*. (Л). |
(11.1) |
|
|
Л(А)е°Л |
|
|
X(А)бО-j_] |
|
|
где п — мерное множество G^ определяется условиями: |
||||||
|
£а.,А-ДЛ )*гф ,(Л ), i = 1, 2 ,..., т\ |
( 11.2 ) |
||||
|
|
^ ( А ) ^ 0 , у = 1, 2,..., п. |
(11.3) |
|||
|
Здесь fj(M ) и <|*1(Л )—заданные скалярные функции век |
|||||
торных аргументов, |
ан — действительны^ числа. |
|
||||
|
Для изучения свойств функции F(A, М) введем следую |
|||||
щие |
определения. |
|
|
|
|
|
_ |
Определение |
1. |
Множество |
D /(-мерных векторов |
||
Л — (Х„ Х2,..., Хк), |
для |
которых условия (11.2), (11.3) не |
||||
противоречивы, т. е. |
множество |
G- л-мерных |
векторов |
|||
X (Л)=(дс,(Л), лг(Л ).....* П(А)) непусто, называется множест |
||||||
вом допустимости задачи (11.1)—(11.3). |
|
|||||
_ |
Определение 2. Множество N (/(-{-1)-мерных векторов |
|||||
(Л, M)=(XV Х2.....Хк, pj |
|
jxL), для которых A=(Xj, |
Хг,..., Хк) |
|||
принадлежит непустому множеству D, и функция /[A (A ), М] ограничена сверху на множестве G- допустимых решений системы условий (11.2) и (11.3), называется множеством (или областью) определения функции F ( Л, М).
Определение 3. Если в точке (Л, М) = (Х1( Х2,..., Хк, |Аг,..., (il) множества N функция /( А -(А), М| достигает своего наибольшего значения на базисном решении (или на опорном плане), соответствующем базису B**(Piv Pj2,..., Р\т), то скажем, что ватой точке функция F (Л, М) порождается
базисом Б.
Систему линейно независимых векторов Piv Pj2..... Pim принято называть основой (см. [22], стр. 167), а область изменения параметров (Л, М)=(Х,, Х2,..., Хк, p.r [i.L) из множества N, при котором определяется функция F ( Л, М) — областью оптимальности основы. Так как при этом основа превращается в базис, то на области оптимальности данной основы функция F (Л, М) порождается этим же базисом.
Ввиду того, что один и тот же опорный план может соответствовать различным базисам (вследствие вырожден-
225
15-644
ности данного опорного плана), и в рассматриваемой точ ке (Л, M) = (/.j, >-к, tM.) могут существовать несколько опорных планов (вследствие вырожденности опорного плана двойственной задачи), то ясно, что в дан ной точке функция F { Л, М), вообще говоря, может по рождаться несколькими базисами.
2п. Изучение свойств целевой функции. При опре деленных ограничениях, накладываемых на функции ^ (Л) и
(М) можно четко определить характер области N. Утверждение 1. Если функции ФДЛ) (/=*!, 2,..., т) во
гнуты, то множество О (если оно не пусто) выпукло1.
Доказательство. Пусть |
Л', А " £ 0 , |
т. е. существуют |
||||||
векторы X (А '), |
^ (Л ") £_/?”, |
удовлетворяющие |
условиям |
|||||
(11.2) |
и (11.3) |
в точках Л' |
и Л". Для промежуточных то |
|||||
чек А » а А'-|-(1— а) Л" ( 0 < а < 1 ) |
|
|
|
|||||
определим вектор |
|
|
|
|
|
|
||
|
^ (Л ) = « А (Л ') |
+ |
( 1 - « ) ^ Г П . |
|
(П .4) |
|||
Подставим компоненты этого вектора в систему (11.2): |
||||||||
2 |
а„ JC (А ) = * V; я,,*, (Л ') + ( 1 - « ) |
X |
ап>г, (Л”) as |
|||||
3-1 |
|
J - l |
|
|
|
J--1 |
|
|
|
|
(А ') + (1 - «) ф[ (А ") - - 4ч (А ). |
|
|||||
Аналогично показывается, что эти |
компоненты у д о в |
|||||||
летворяют и условиям |
неотрицательности. |
Значит, Л £D . |
||||||
Утверждение доказано. |
|
|
|
|
|
|||
Из самого |
определения |
множества |
D |
ясно, |
что если |
|||
< ?£ = 0 |
2 для любого Л £ # к , то 0 = 0 . |
Так что, в таких |
||||||
случаях задача (11.1)—(11.3) неразрешима. |
|
|||||||
Обозначим |
через |
О , |
л-мерное множество, определяе |
|||||
мое условиями: |
|
|
|
|
|
|
|
|
|
У ам^ = 0 , |
1=1, 2,..., т, |
|
|
(11.5) |
|||
|
J-I |
|
|
|
|
|
|
|
|
S * J - 1 . |
|
|
|
|
|
( Н . 6 ) |
|
__________ |
Z j ^ O ,/= 1 , 2..... п. |
|
|
(11.7) |
||||
1 Здесь используем определения выпуклых функций и области, при |
||||||||
веденные в [32]. |
|
|
|
|
|
|
|
|
3 Символ 0 означает пустое |
множество. |
|
|
|
||||
226