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

правую сторону линии X = Xt должны получить на соседнем прямоугольнике уже имеющуюся таблицу).

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

все прямоугольники ЛД и соответствующие коэффициенты выражения вида (13.9). Конечность процесса следует из конечности числа всевозможных базисов.

Заметим, что для решения задачи (13.Г )—(13.3') мож­ но было бы пользоваться алгоритмом Б. В. Финкельштейна (см. [84]), введением в него несущественных изменений в связи с параметром |х (например, выбором направления S), но нецелесообразно для решения таких простейших задач, как задача (13.1')—(13.3'), применять громоздкий (с точки зрения объема вычислений и логической сложности струк­ туры схемы) алгоритм, разработанный для решения более сложных задач.

Блок-схема изложенного здесь алгоритма приведена на стр. 250 и 251.

Пример: для каждой пары чисел X, ц построить функцию

F (/., у.) = тах |(3 — 2ji) х . + (2 4- р )х 2 + (1 — 2р.) х3),

о х

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

Для решения поставленной задачи решаем соответст­ вующую расширенную задачу:

для каждой пары X, ц построить функцию

249

Блок-схема решения двухпараметрической задачи.

Начало

250

Продолжение блок-схемы решения двухпараметрической задачи.

251

Построим исходную симплексную таблицу и применим изложенный выше алгоритм.

252

—>.— 123*0,

—Х+1Э*0.

253

§ 4. Решение задачи параметрического программирования с вектором ограничений, линейно зависящим от параметра

Если функции <pj V-\I) постоянные, а ф, (Л) — линейные функции от Л, то задача (11.1)—(11.3) принимает доста­ точно простой вид. В данном параграфе рассмотрим именно такую задачу, с дополнительным предположением, что за­ дача задана в канонической форме. Последнее предполо­ жение, разумеется, не меняет постановку вопроса, так как в случае линейности функций ф|(Л) основные конструктив­ ные свойства целевой функции и области ее определе­ ния (введенные в параграфе 1 для задачи (11.1)—(11.3)) легче распрастраняются на задачи, заданные в канонической форме. Более того, эти свойства здесь показываются до­ вольно проще, и имеется возможность более ясно пред­ ставить как вид целевой функции, так и область ее опре­ деления.

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

255

Для каждого А £ /? к построить функцию

где область G -Q R" определяется условиями:

является выпуклым многогранным множеством, определяю­ щимся системой линейных неравенств. Функция F (А ) на каждой подобласти является линейной финкцией, а на общей грани соседних многогранников—непрерывной. Ины­ ми словами, F (А ) является кусочно-линейной непрерывной

показать и непосредственно, пользуясь основными принци­ пами теории двойственности линейного программирования.

Приведем описание алгоритма решения задачи (14.1)— (14.3).

Не нарушая общности, можно предположить, что если для данного i 8ik = 0 при £ = 1, 2,..., К то обеспечена неотрицательность коэффициента S^k’+i- Если для данного i 5ik = 0 при й = 1 , 2,..., К, то обеспечена неотрицатель­ ность свободного члена Ь{ (при необходимости соответст­ вующее уравнение системы условий (14.2) умножается на

256