Файл: Арутюнян А.Г. Применение математических методов и ЭВМ в народном хозяйстве.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.07.2024
Просмотров: 173
Скачиваний: 0
Га |
Р0 |
Л (>) |
Рг |
Р3 |
Р4 |
Номер |
итерации |
||||||
|
19 |
47+9 |
0 |
1 |
11 |
|
Р3 |
17 |
17 |
— 7? |
|
||
Рг |
20 |
- 11/, •5 |
1 |
0 |
|
|
17 |
17 |
17 |
|
|||
|
|
|
2(0) |
|||
|
|
|
|
|
|
|
- |
59 |
— 187—49 |
0 |
0 |
24 |
|
17 |
17 |
17 |
|
|||
|
|
|
||||
- |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
Отсюда |
заключаем, что |
имеющийся базис оптимален |
||||
на луче /.«s — — . В точке |
/.= * — — |
оценка |
вектора Р,(/.) |
|||
1 |
18 |
|
|
18 |
|
|
обращается в нуль, а правее этой точки она станет отри цательной.
Рассмотрим задачу |
на луче |
|
------— . |
В |
интервале |
|||
49 . |
9 |
|
|
|
|
|
|
|
----- — |
-----— единственным положительным элементом |
|||||||
является |
_ ~ ш + 5 |
_ Этот элемент и |
будет |
генеральным. |
||||
Б , „ с |
р п |
Я,(7) |
Р, |
Р3 |
Р 4 |
|
Номер |
|
итерации |
||||||||
|
|
|
|
|
|
|||
Р) |
— 177— 5 |
0 |
— 47—9 |
1 |
57 8 |
|
|
|
— 117+5 |
|
-117+5 |
|
|
||||
— 117+5 |
|
|
|
|||||
|
|
|
|
|||||
/>,(>•) |
20 |
1 |
17 |
0 |
9 |
|
3(1) |
|
— 117+5 |
|
— 117+5 |
|
|||||
— 117+5 |
|
|
|
|||||
- |
— 177+75 |
0 |
187-j 49 |
0 |
—67+33 |
|
|
|
— 117+5 |
|
— 117+5 |
|
|
||||
— 117-15 |
|
|
|
|||||
Выделим теперь отрезок оптимальности полученного |
||||||||
базиса. Базис (Р3, |
РДО ) |
будет допустимым при |
----- :у- |
|||||
290
(общин |
знаменатель остается |
положительным на полуоси |
|
5 . |
. |
.5 |
|
X-g:— |
), а |
правее точки ?. = |
-^у- признак оптимальности |
нарушается. |
Следовательно, |
на отрезке^-----Щ -,----- ~ ] ба |
|
зис остается допустимым и оптимальным. На этом отрезке имеем:
— 17).+ 75
|
|
F (>■)-- |
— IU + 5 |
|
|
|
|
|
|
|
|
|
|
Так как |
правее точки |
) . = -----— базисная |
переменная |
|||
17?, - 5 |
• станет |
отрицательной, |
то |
здесь |
нужно |
|
- 1 1 ).+ |
5 |
|
уточнения оце- |
|||
пользоваться |
методом последовательного |
|||||
нок. Нетрудно |
убедиться, |
что на отрезке ■— |
5 |
5 |
||
— sS/.s£-jy- |
||||||
отрицательными будут следующие элементы первой строки1
,„{/.) = |
— 4) — 9 |
и * ,, (/•) = |
5) — 8 |
. Составим отношения: |
|||||
------------- |
|
|
|||||||
'- v ’ |
- 1 1 ) .+ 5 |
14 ’ |
|
— 11Х + 5 ' |
|
|
|||
18).+49 |
_ |
4Х—!9__ _ |
18А+49 — 6А+33 |
5).—8 |
-6 Х + 33 |
||||
- 11). ,5 |
‘ |
— ПА-|-5 ' |
—4А— 9 |
— 11М -5 |
— 11А+5 |
5А— 8 |
|||
Так как в окрестности точки |
|
, |
5 |
|
|||||
|
> .= |
----- — второе отно |
|||||||
шение |
больше первого, |
то |
генеральным элементом будет |
||||||
*„(>•)« |
-1 1 X 4 5 |
|
|
|
|
|
|
|
|
Преобразуем |
симплексную таблицу: |
|
|||||||
Базис |
Р п |
Л (*) |
Р, |
|
Рз |
Р 4 |
Номер |
||
|
итерации |
||||||||
Л |
|
— 17Х—5 |
0 |
— 4л -9 I |
— I1X+5 |
|
|||
|
5Х—8 |
5Х—8 1 |
|
|
1 |
|
|||
|
|
|
|
54—8 |
|
||||
Л ( ') |
—23 |
1 |
— И |
|
—9 |
4(2) |
|||
5>—8 |
5Х— 8 |
|
|
0 |
|||||
|
|
|
|
54— 8 |
|
||||
|
|
17Х— 87 |
0 |
— 04— 19 |
|
6Х— 33 |
|
||
|
|
5А— 8 |
54— 8 |
|
|
0 |
|
||
|
|
|
|
5)—8 |
|
||||
291
Так как при Х^>-----— имеем - 17/.— 5 < 0 , то неот
рицательность базисной переменной лг4 (Х )д —17>.—5 9KBH^
5А— 8
валентна условию 5/.— 8 <1 0, откуда |
Следователь |
но, имеющийся базис остается допустимым |
на отрезке |
-----^ -*5 >■<-**-. Признак оптимальности также сохраняется
до точки |
Х= |
Значит в интервале |-----|-J функция |
|||
F {>•) определяется |
форулой |
|
|
||
При |
стремлении |
X (слева) к точке |
— ~ базисные |
||
компоненты решения задачи и сама |
функция /Г(Х) неогра- |
||||
ииченно |
возрастают. |
Правее точки |
/. = — |
нарушаются и |
|
допустимость и признак оптимальности. Далее получаем
допустимый базис в точках, лежащих справа от Х = -^-.
В качестве генеральной |
выбираем первую строку. Ясно, |
||
что с выбором второй |
строки, |
мы придем либо к базису |
|
(Р4, Р 2), либо к базису |
(Р4, |
Р3), |
которые заведомо не явля |
ются оптимальными (а, вообще говоря, они могут быть даже недопустимыми). Иными словами, в дальнейшем век тор Р 2(Х) должен обязательно участвовать в базисе. Для того, чтобы не уменьшить оценки векторов условий, снова пользуемся методом последовательного уточнения оценок.
При /._> — |
элементы первой |
строки |
х 12( / . ) = ———— и |
|||||
_ |
11А+5 |
отрицательны. Из отношений |
|
|||||
-^13(л) = —гг—— |
|
|||||||
-0>.— 19 . — 4Х—9 |
_ — 6).— 19 |
„ |
6А—33 |
_ — 11А+5 |
(ЗА—33 |
|||
5А— 8 ' |
SX— 8 |
~ —4Х— 9 |
5Х— 8 |
' |
5Х— 8 |
— 11Х+5 ’ |
||
на некотором |
интервале, |
имеющем |
в качестве |
левой гра |
||||
ницы точку X = |
максимальным является первое. Значит, |
|||||||
элемент х ]2 (Х) будет генеральным. Реализуя симплексное преобразование, получаем следующую таблицу.
292
Базис |
Р0 |
Л(Х) Р3 |
р 3 |
Р4 |
Номер |
||
|
|
|
|
|
|
итерации |
|
|
17а+ 5 |
0 |
и х —5 |
—5Х+8 |
|
||
|
4 4 9 |
4 4 |
9 |
4 4 9 |
|
||
|
|
|
|||||
Л (>) |
19 |
0 |
17 |
|
— 11 |
5(3) |
|
4Х+9 |
4 4 9 |
4 4 9 |
|||||
|
|
|
|||||
|
3 4 4 86 |
0 |
1 8 4 4 9 — 6).— 19 |
|
|||
|
4 4 9 |
4a j-9 |
4Х+9 |
|
|||
|
|
|
|||||
При >.S= — |
полученный базис допустимый. Однако |
6 Х + 1 9 |
вектора РА отрицательна, и в этом столб |
оценка------^ ^ |
це нет ни одного положительного элемента. Следовательно,
функция F (/.) не будет определенной на луче Xs»-g-.
Таким образом, на области ее определения, мы строим функцию F (>.):
59 |
|
^ |
_ |
|
49 |
17 |
при — оо <Г ). |
|
-------- , |
||
|
^ |
|
|
18 ’ |
|
—17Х+75 |
при |
49 |
" " |
5 |
|
—11Х+5 |
|
18 |
17 |
||
17Х—87 |
при |
17 |
|
^ 5 |
|
1 5Х—8 |
|
|
|
||
Приведенный пример иллюстрирует случай, когда мно жество неограниченности целевой функции задачи является лучом. Из разрешимости урезанной задачи следует, что условия поставленной задачи совместны, и функция F (>.) определена для тех значений при которых целевая ли нейная функция ограничена сверху на соответствующем множестве допустимых решений. График функции F (X) на области ее определения показан на рис. 16.1.
293
§7. Применение методов параметрического линейного программирования для определения необходимого
количества реализации случайных величин при решении линейной стохастической задачи
В работе [81] рассматривается задача стохастического линейного программирования со случайным вектором огра ничений. На основе некоторых идей математической ста тистики вопрос определеления необходимого количества реализации случайных величин для решения стохастиче ской задачи с заданной точностью сводится к решению одной задачи ПЛП специального вида. После определения границы доверительных интервалов [аг, ajj возможных реа-
294
лизаций случайных компонентов вектора ограничений, фор мулируется следующая задача.
Найти пару векторов А ', А"£Я™, минимизирующую ли нейную функцию
|
|
|
|
|
|
(17.1) |
при условиях |
|
|
|
|
|
|
F (A ')- F (A " ) = |
e> |
|
(17.2) |
|||
Л' — Л" |
В > |
0, |
|
(17.3) |
||
>>'[, 'Л б К , ®i|, |
г— 1, 2 ..... |
т. |
(17.4) |
|||
Функция /ДА), участвующая в условии (17.2), является |
||||||
решением следующей задачи ПЛП. |
|
|
||||
Построить функцию: |
|
|
|
|
|
|
/r (A) = |
m a xV |
с^дгДЛ), |
|
(17.5) |
||
|
Ж1 j - i |
|
|
|
||
где область |
определяется условиями |
|
||||
Ц CijJTj (A )ss/.,, |
i = 1 , |
2,..., |
т, |
(17.6) |
||
)=i |
|
|
|
|
|
|
л:ДЛ)Э=0, j = |
|
1, 2..... л, |
|
(17.7) |
||
> ч £ К |
*,], i |
- |
1, 2 ,..., т. |
(17.8) |
||
Задача (17.5)—(17.8) является частным видом задачи, изученной нами в параграфе 4 данной главы, с той разни цей, что здесь требуется построить функцию /ДА) на огра ниченном параллелепипеде (17.8). Следовательно, все фак ты, доказанные в параграфе 4 относительно целевой функ ции F(A), остаются справедливыми. Функция (17.5) обладает еще одним характерным свойством: она является моно тонно неубывающей функцией, т. е.
(Л<4) приЛт г=Л<ч. |
(17.9) |
Для решения задачи (17.1)—(17.4) нет необходимости на всем параллелепипеде (17.8) построить функцию /ДА ). На основе конструктивных свойств функции F (Л) доказы-
295
