<<
>>

12.2. Аналитический метод решения задач параметрического программирования

Алгоритм решения задачи в общей форме состоит из двух частей.

Фиксируем значение t из заданного промежутка, допустим самое меньшее t = а. Тогда в целевой функции все коэффициенты станут постоянными.

Решаем полученную задачу симплекс-методом и находим вершину, в которой Za достигает максимума.

Определяем все значения параметра для которых максимум достигается в той же вершине. Найденный интервал исключаем из заданного отрезка [а, Р]. Для оставшегося интервала снова решаем задачу, т. е. переходим к п.1 алгоритма. Так продолжаем до тех пор, пока не будет разделен на частичные интервалы весь отрезок[а, Р].

Проанализируем пункты алгоритма более подробно.

1. Полагая t = а, целевая функция принимает вид:

п

Za= I (су +dja)Xj.

М

Составляем первую симплекс-таблицу, добавляя две строки: для коэффициентов Cj и dj (табл. 12.1):

Таблица 12.1

Форма симплекс-таблицы для решения задачи параметрического программирования Свободный

Базисный Свобод-ные члены хь х2у... хп хп + 1 •• хп + т хп + 1 aij 1

1 1 хп + т <>т 1 Za 0 -(сх + dxa) ...

(сп + dna) 00... 0 Zt - СЬ - С2... 00... 0 - d{, - d2... ~dn 00... 0

В строке Za табл. 12.1 в каждом столбце фактически будет стоять одно число, равное Cj + djCL. В последних двух строках записаны индексы линейной формы Z, для произвольного параметра t.

Обычным симплекс-методом находим оптимальный план, причем этим же преобразованиям подвергаются элементы двух последних строк. В итоге получаем данные табл. 12.2.

Необходимо отметить, что в табл. 12.2 столбцы, соответствующие базисным переменным, являются нулевыми (т. е. содержат 1 на пересечении ^-столбца и ^-строки, а остальные нули).

Поскольку план, полученный в табл. 12.2, оптимален, все коэффициенты Za строки неотрицательны:

(Pj + <7/0 > 0.

После этого переходим ко второму пункту алгоритма.

Надо выделить интервал времени в котором максимум Z, достигается в той же вершине. Иными словами, надо найти такие значения t, для

Общий вид оптимального плана Свободный

Базисный Свободные члены хь х2, ... хп —Х„ + 1 ... хп + т Х\ *s

хп + т Ъ\ h 1

1

1

1 Za P+Qa рх + qxa ... рп + qnа Рп + т + Яп + та А p Р\... Рп Рп + т Q Qn Яп + т

которых план, полученный в табл. 12.2, будет оставаться оптимальным. План оптимален, если все коэффициенты функции Zt будут неотрицательны:

px+qxt> О

p2+q2t>0 (12.3)

pn+qnt> 0.

Столбцы, соответствующие базисным переменным, можно не рассматривать. Из решения полученной системы неравенств можно найти интересующий нас интервал.

Рассмотрим несколько случаев:

а) Пусть все коэффициенты qj > 0,j = 1 ,п. Тогда t > -Pj/qp па-раметр t, удовлетворяющий системе (12.3), определяется выраже

IL Я]

нием />тах

. Верхняя граница для t стремится к +

Таким образом, окончательно

.El я І

cq =max

(12.4)

В интервале (12.4) целевая функция достигает максимума в той же вершине.

б) Пусть все коэффициенты qj < 0, тогда из (12.3) имеем t < < —pj/qj. Для того чтобы значение t удовлетворяло всей системе

с \

Нижняя граница для t

(12.3), необходимо положить /ьтіп стремится к — поэтому V

qj

а{ = -оо(/ < min {-pj/qj) = а2. (12.5)

в) Пусть среди элементов qj имеются как положительные, так и отрицательные числа.

Разделив неравенства системы (12.3) на две группы соответственно знакам fy, получаем два интервала (12.4) и (12.5), объединяя эти интервалы, получим

ах = max (-Pj/qj) < t < min (-pJq)= a2.

(12.6)

Qj >0 qj < 0

г) Если qj — 0, то соответствующий коэффициент функции будет неотрицательным при любом /, поэтому на такой столбец можно не обращать внимания.

Сравниваем полученный интервал (cq; а2) с заданным [а, Р]. Независимо от значения аь левой границей первого интервала бу-дет а, так как щ больше а быть не может.

Если а2 > Р, то весь отрезок попадает внутрь интервала [а1? а2], и задача решена. Для любого значения параметра t є [а, Р] максимум Zt достигается в одной и той же вершине

а

іа2.

Если а2 < Р, то найденный интервал исключаем из рассмотрения и решаем задачу для оставшегося интервала (а2, р). Для этого полагаем t — а2 и заменяем строку Za строкой Za2. За разрешающий столбец в новой таблице выбираем тот, по которому определено значение t — а2 (в этом столбце на пересечении с Z^-строкой находится элемент, равный нулю). Если нули находятся в нескольких столбцах, то за разрешающий можно брать любой из них.

Для найденного решения снова определяем интервал изменения параметра t и т. д. Если в разрешающем столбце не окажется положительных элементов, задача на оставшемся интервале не имеет решения.

Пример 12.2. Решить задачу параметрического программиро-вания

2xi +3x2 +*3

3*! +2^2 ~2х3<3;

4х!+2х2+х3 <4; xj>О у=Г3;

Z, = + (1+/)х2 + (6 - 2/)х3 -> шах; /е[1; 8].

Решение

Приведем задачу к виду, допускающему применение алгоритма, и найдем выражение целевой функции при /=7 (левый конец за-данного промежутка):

2xi + 3x2 + х3 + Х4

Зхі+х2~2хз+ Х5 + Хб=3;

4xj + 2x2 + *3 + х6 = 4;

Z! = Xj + 2х2 + 4х3 -> max.

Составим первую симплекс-таблицу с дополнительными строч-ками для функции Zt и выполним преобразование симплекс-таблицы для решения задачи (табл. 12.3—12.4).

Таблица 12.3 0 1 2 4 0 0 0 \ Сво- \ бод- \ные БаД зис-\ ные \ св. ч *2 *3 х4 *5 ч 2 х4 1 2 3 1 0 0 *5 3 3 1 -2 0 1 0 Ч 4 4 2 1 0 0 1 zt 0 -1 -2 -4 0 0 0 zt 0 0 -1 -6 0 0 0 0 -1 -1 2 0 0 0

0 1 2 4 0 0 0 \ Сво- \ бод- \ ные

БаД зис- \ ные \ св. ч *2 *3 *4 *5 *6 X *3 1 2 3 1 1 0 0 *5 5 7 7 0 2 1 0 *6 3 2 -1 0 -1 0 1 4 7 10 0 4 0 0 6 12 17 0 6 0 0 -2 -5 -7 0 -2 0 0 Таблица 12.5 0 1 2 4 0 0 0 \ Сво- \ бод- \ ные

БаД зис- \ ные \ св. ч *2 *з *4 *5 ч 2 *3 1 Ш 3 1 1 0 0 5 7 7 0 2 1 0 *6 3 2 -1 0 -1 0 1 Z\2/5 6/5 0 1/5 0 6/5 0 0 zt 6 12 17 0 6 0 0 1 -2 -5 -7 0 -2 0 0

0 1 2 4 0 0 0 \ Сво- \ бод- \ ные БаД св.

ч х2 *з х4 х5 *6 зис- \ ные \ 1/2 1 3/2 1/2 1/2 0 0 3/2 0 -7/2 -7/2 -3/2 1 0 ч 2 0 -4 -1 -2 0 1 Z\2/5 6/5 0 1/5 0 6/5 0 0 Z 0 0 -1 -6 0 0 0 1/2 0 1/2 5/2 1/2 0 0

В табл. 12.4 получено оптимальное решение, так как все коэффициенты Zj-строки неотрицательны — х = (0; 0; 1; 0; 5; 3). Определим интервал для в котором оптимальное решение будет в той же вершине. Так как все qj < 0 (табл. 12.4), то согласно (12.5) а{ = —а2 = 12,5.

Для нашего случая а{ = 1 (левый конец заданного отрезка). Таким образом, на отрезке [1; 12/5] решение будет в точке х = (0; 0,1; 0; 5; 3). Исключаем найденный отрезок из рассмотрения и решаем задачу для оставшегося отрезка [12/5; 8]. Для этого, полагая t = 12/5, вычисляем для него строку Z12/5. В первом столбце получим нуль; остальные коэффициенты Z12/5 строки положительны, а другие элементы остаются прежними (табл. 12.5). За разрешающий столбец в табл. 12.5 выбираем тот, по которому определено значение t = а2. Если нули находятся в нескольких столбцах, то за разрешающий можно брать любой из них. Новый план х = (1/2; 0; 0; 0; 3/12; 0) оптимален, так как в строке Z12/5 нет отрицательных элементов (практически элементы строки ^72/5 остались без изменения).

В последней строке табл. 12.6 все q: > 0, поэтому согласно (табл. 12.6) а{ = 12/5, а2 = +<*>; t є [12/5; 8]. Таким образом, заданный промежуток разбился на два; при t = 12/5 оптимальное значение достигается в обеих вершинах и в любой точке, являющейся их выпуклой линейной комбинацией

А = \{А{ + Х2А2; >0; Х2> 0; Х{ + Х2 = 1.

Задачи

Решить графическим методом

Zt = (2 + 2t)xx + (4 - 2t)x2 max;

Xj + x2 < 6;

x2<4; 2xx + x2 < 10; X! > 0; x2 > 0; te [1; 15].

Z, = 4x!. + (2 + 0x2 —> max; 2xx - 5X2 < 10; Xj + x2 < 5; —xx + x2 < 4; 4xx + 5X2 < 40; Xj > 0; x2 > 0; te [0; 8].

Решить аналитически

Z, = (1 + t)xx + (2 - t)x2 + (2 - Зґ)х3 + (1 - 2Ґ)Х4 max; Xj + x2 + 2x3 — x4 < 5; xx + 2X2 + x4 < 7; XJ + x3 + 2X4< 3; Xj > 0; у = 1,4; t e [1; 20].

Z, = (10 - 10/)xj + (9 + t)x2 + (7 - 2/)x3 -> max; Xj + x2 < 5; 2xx + x3 < 7; Xj + 2X2 + 3x3 < 3; xy>0;y = 1,3; te [1; 10].

Zt = txx + (1 + ґ)х2 —» max; -3xx + 4X2 < 12; 4xj + x2 < 8; xx > 0; x2 > 0; te [1; 7].

Глава 13

<< | >>
Источник: Бережная Е.В., Бережной В.И.. Математические методы моделирования экономических систем: Учеб. пособие. — 2-е изд., перераб. и доп. — М.: Финансы и статистика,2006. - 432 е.. 2006

Еще по теме 12.2. Аналитический метод решения задач параметрического программирования:

  1. 1.2.2. Методы решения задачи обнаружения «цели»
  2. 2.3 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
  3. 3.1. Методы решения образовательных, развивающих и воспитательных задач
  4. 7.3. Графическое решение задачи линейного программирования
  5. 7.6. Методы нахождения опорного решения задачи линейного программирования
  6. 7.7. Экономическая интерпретация решения задачи линейного программирования
  7. 10.4. Многоцелевые задачи линейного программирования
  8. 12.2. Аналитический метод решения задач параметрического программирования
  9. § 65. Симплекс-метод решения задач линейного программирования, М-метод
  10. § 66. Двойственные задачи .линейного программирования и решение их двойственным симплексным методом
  11. Графический метод решения задач
  12. Агошков, Валерий Иванович. Методы решения задач математической физики:, 2002
  13. § 8.5. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
  14. § 1.6. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
  15. 2.1. Численный метод решения многокритериальной задачи дискретного нелинейного программирования