Комплексные задачи

7.2. Рассмотрим следующую задачу ЛП.

Максимизировать z = Зхх + 2х2

при ограничениях

х, 4- 2х2 < 6, 2х, +хг<8, -хх+х2<1, х х2>0.

Найдите оптимальное решение этой задачи (можно применить программу TORA). Затем, используя информацию, представленную в симплекс-таблице с оптимальным решением, определите второе (по отношению к абсолютному оптимуму) наилучшее решение (т.е. крайнюю точку пространства решений). Проверьте ответ, решив эту задачу графически. (Подсказка. Искомая крайняя точка будет смежной с точкой, соответствующей оптимальному решению.)

7.3. Интервальное программирование. Рассмотрим следующую задачу ЛП.

Максимизировать z = {СХ L < АХ < U, X > 0},

где L и U - вектор-столбцы констант. Определим вектор Y > 0, такой, что АХ + Y = U. Покажите, что исходная задача эквивалентна следующей.

Максимизировать z = {СХ AX + Y= U,0<Y<U-L,X>0}. Используя показанный прием, решите следующую задачу ЛП.

Минимизировать z = 5х, - 4х2 + 6х,

при ограничениях

20 < х, + 1х2 + Зж3 < 46, 10 < Зх, - х2 + х3 < 20, 18< 2хх + Зх2-х3<35, xvx2, х3>0.

7.4. Рассмотрим следующую целочисленную задачу ЛП, где переменные принимают только значения 0 и 1.

Минимизировать z = {СХ АХ < b, X = (0, 1)}.

Предположим, что известна верхняя граница целевой функции zmili. Введем ограничение

min max {p(b - АХ) + (z, - СХ)} > О,

где ц> 0. Это ограничение не нарушает ни одного из ограничений исходной задачи. Покажите, что определение из этого ограничения фактически сводится к решению исходной задачи ЛП. (Совет. В данном случае условие целочисленности X = [0, 1] эквивалентно непрерывному ограничению 0 < X < 1. Сформулируйте двойственную задачу.)

7.5. В задаче 7.2 оптимальным решением является хх = 10/3, х2 = 4/3 и г = 38/3. Как будет изменяться оптимальное значение целевой функции в зависимости от параметра 6, если положить хх = 10/3 4- 0 (на параметр 0 не налагаются ограничения в знаке)?

Предположим, что оптимальное решение задачи ЛП представлено следующим образом.

Максимизировать z = с0 - (г, - с;)х]

при ограничениях

х, = х - o:irr;, i = 1, 2,т, все jc, и х > О,

где - множество индексов небазисных переменных. Предположим, что на текущую базисную переменную х, = х налагается ограничение х. > dt, где

dt - наименьшее целое, большее х]. После введения этого ограничения

оцените верхнюю границу оптимального значения целевой функции. Повторите процедуру оценки верхней границы при наложении ограничения xt < et, где е, - наибольшее целое, меньше х .

Рассмотрим следующую задачу линейного программирования.

Минимизировать z = (10i - 4) х, + {At - 8) х2 при ограничениях

2хх + 2х2 + х3 = 8, Axl + 2x2 + xi = 6-2t, x], х2, Х3, х4 О,

где -оо < t < оо. С помощью параметрического анализа получены следующие результаты:

при -°° < t < -5 оптимальный базис: В = (Р Р4), при -5 < t < -1 оптимальный базис: В = (Р Р2), при -1 < t < 2 оптимальный базис: В = (Р2, Р3).

Найдите все критические значения параметра t при t > 2.

ГЛАВА 8

ЦЕЛЕВОЕ ПРОГРАММИРОВАНИЕ

Модели линейного программирования, рассмотренные в предыдущих главах, предполагали оптимизацию только одной целевой функции. Но возможны ситуации, когда в модели присутствует несколько (возможно, конфликтующих между собой) целевых функций. Например, честолюбивый политик может пообещать уменьшение национального долга и, одновременно, снижение ставок налогов. В таких ситуациях иногда невозможно найти единственное решение, оптимизирующее все конфликтующие целевые функции. Поэтому нужно искать компромиссное решение, учитывающее важность каждой целевой функции.

В этой главе представлены методы целевого программирования (многокритериальной оптимизации)1 для решения задач линейного программирования с несколькими целевыми функциями. Основное назначение этих методов- преобразование исходной задачи с несколькими целевыми функциями в задачу ЛП с одной целевой функцией. После решения преобразованной задачи получаем так называемое эффективное решение, поскольку может не существовать оптимального решения, доставляющего оптимум всем частным целевым функциям исходной задачи.

8.1. ФОРМУЛИРОВКА ЗАДАЧИ ЦЕЛЕВОГО ПРОГРАММИРОВАНИЯ

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

Пример 8.1.1

Файрвилл - небольшой городок, в котором проживает около 20 тысяч жителей. Предположим, городской совет разрабатывает ставки местного налогообложения. Ежегодная база налогообложения недвижимости составляет 550 миллионов долларов. Ежегодная база налогообложения розничных и оптовых продаж составляет 35 и 55 миллионов долларов соответственно. Ежегодное потребление городом бензина оценивается в 7,5 миллионов галлонов. Городской совет планирует разработать систему налоговых ставок, основанную на перечисленных базах налогообложения и учитывающую следующие ограничения и требования.

1 Задачи целевого программирования являются только подклассом задач, решаемых методами многокритериальной оптимизации. Подходы и методы, применяемые в многокритериальной оптимизации, отнюдь не исчерпываются теми методами, которые описаны в этой главе (см. список литературы в конце главы). - Прим. ред.