Файл: Арутюнян А.Г. Применение математических методов и ЭВМ в народном хозяйстве.pdf

Если при переходе используется метод последователь­ ного улучшения плана, и при a > a t обнаружится признак неограниченности, то при помощи анализа элементов столб­ ца, показывающего признак неограниченности, определя­ ется эта область. Очевидно (в силу утверждения 6 пара­ графа 1, примененного к однопараметрической задаче), область неограниченности может быть как конечным интер­ валом, так и лучом. Если эта область — конечный интервал,

метод последовательного уточнения оценок и обнаружи­

Из изложенного ясно, что каждая область изменения параметра я, на которой функция <р(я) порождается одним и тем же базисом, является отрезком, если ее' границы (в предыдущем и в текущем шагах) определены неравенствами (16.6) или (16.8). Но если верхняя граница рассматриваемой области определяется неравенством (16.7), то данная об­ ласть представляет собой открытый справа интервал

я,), так как 'f* («) —♦+ ° ° ПРИ л~ — 0- Аналогичный резуль­ тат получается при определении правой границы области неограниченности. Значит, область неограниченности функ­ ции <р(я) может быть:

а) пустой; б) точкой;

в) открытым или полуоткрытым конечным интервалом; г) конечным отрезком;

д) лучом с начальной точкой или без нее.

За м е ч а н и я . 1. Так как на одной и той же области

изменения параметра я функция <р(я) может порождаться несколькими базисами, то может показаться, что <р(я) не является однозначной. Однако, если в каждой точке рас­ сматривать соответствующую числовую задачу линейного программирования, можно сразу убедиться в том, что мак­ симальное значение целевой функции этой задачи—единст-

283

ских задач не приведет к вторичному попаданию в область, рассмотренную на предыдущих шагах. Для этого выбира­ ется достаточно малое число 5 > 0 и рассматривается за­ дача на гиперплоскости

дой из которых некоторая основа является оптимальным базисом, и фиксируются по одной внутренней точке из каж дой такой области.

Если гиперплоскость (16.9) не содержит ни одной точки допустимости, то в полупространстве (16.1) задача нераз­ решима. Может оказаться, что гиперплоскость (16.9) це­ ликом содержится в области неограниченности функции /Г(Л). В этом случае увеличивается s и рассматривается другая гиперплоскость вида (16.9).

перплоскости по направлению нормали невозможно выйти из области неограниченности, то полупространство

к

I “Ъ -Хкт-И,1^к^= — е

к=1

является областью неограниченности функции /Г(Л). Отсюда видно, что если гиперплоскость (16.9) принад­

лежит к области неограниченности ^(Л ), то достаточно исследовать однопараметрическую задачу, исходя из не­ которой точки этой гиперплоскости. Если при движении по направлению нормали из данной точки можно попасть в область определения функции ср(а), то следует последова­ тельно рассматривать области на гиперплоскости вида (16.9) при е = е', где «' определяется из условия конечности функ­ ции <р(а). В противном случае (т. е., если по данному на­ правлению не попадаем в область определения у (а)), полу­ пространство (16.1) является областью неограниченности

'( Л ) .

235

A 2“j~j3,S2, должно быть не более одной критической точки. Если на этом отрезке имеется более одной критической точ­ ки, то существует нерассмотренная область Nu содержащая эти критические точки на граничных гиперповерхностях.

Отметим, наконец, что предположение разрешимости урезанной задачи не ограничивает общности алгоритма, так как вместо задачи (11.11')—(11.13') можно рассматри­ вать соответствующую расширенную задачу, разрешимость которой обеспечивается.

Блок-схема решения задачи (11.11) — (11.13) приведена на стр. 287, 288.

Пример. Для каждого действительного X построить функцию

F (X) = max (4л:, -J- 2*, + * , — * 4), •

£>\

где множество Dx определяется условиями:

(3 — X) л:, -J- 3* 2 + 4х3— * 4 = 8 ,

Соответствующая урезанная задача сформулируеся сле­ дующим образом.

Максимизировать линейную функцию

/ , = 2* 2 4- * 3 — * 4

при условиях

3* 2 4~ 4* 3— *4 = 8 , 5* 24* -*з 4" 2* 4 — 7,

* 2 3 * 0, * 33 =0, * 43 *0 .

286

Блак<хема решения задачи ПЛП с вектором условий, линейно зависящим от параметра

Начало

287

Продолжение блок-схемы

288

Для решения урезанной задачи воспользуемся М-ме- тодом. При решении урезанной задачи в текущую симплекс­ ную таблицу включается вектор условий Р,(>-) без учета его оценки. Генеральный элемент будем отмечать жирным пря­ моугольником. Правее таблицы заполняем номер итерации решения урезанной задачи, а в скобках, рядом с этим номе­ ром,— номер итерации исходной параметрической задачи.