Постановка задачи
Целевое программирование (ЦП) — это относительно новая концепция, развивающая идеи линейного программирования (ЛП) и призванная помочь в разработке управленческих решений в условиях многих целей. Как известно, одним из условий, при которых задача оптимального планирования может быть сформулирована и решена в рамках ЛП является наличие единого, четко сформулированного и количественно определенного критерия оптимальности плана в виде целевой функции. Обычно это минимум затрат или максимум прибыли. Но практика хозяйственной деятельности показывает, что это не единственные, а порой и не самые главные цели, которые приходится ставить и решать, планируя работу на перспективу. В ЛП предусматривается возможность объединения нескольких целей в одну, но в этом случае цели должны измеряться в одних и тех же единицах ( например, в рублях). В реальной жизни цели настолько разнообразны, а порой и противоречивы, что свести их в одну не всегда представляется возможным. Это цели и престижа фирмы, и охраны окружающей среды, и налаживания международных связей, и организация грамотной логистики и грузоперевозок, и поддержания определенного социально-психологического климата в коллективе и т.д., которые и в отдельности измерить не просто.
Одним из возможных направлений реализации подобного рода задач и явилась разработка в начале 60-х годов идей целевого программирования.
Ясно, что в условиях многих целей и ограниченности ресурсов не все цели могут быть достигнуты. В ЦП предусматривается такая возможность и для ее отражения вводится новый тип переменных, показывающий степень отклонения достигнутого уровня целей от желаемого (запланированного). Такие переменные будем называть отклонениями. Не следует смешивать их с балансовыми переменными, рассматриваемыми в ЛП. Балансовые переменные в ЛП показывают, на сколько правая часть ограничения отличается от левой, а переменные-отклонения в ЦП -степень недо- или перевыполнения конкретной цели. Кроме этих особенностей ЛП И ЦП отличаются конструкцией целевых функций. Если в ЛП непосредственно максимизируется или минимизируется одна конкретная цель, то в ЦП минимизируются отклонения между желаемыми и достигнутыми в пределах ограничений по ресурсам уровнями многих целей. Отсюда и роль отклонений. Если в ЛП балансовые переменные являются вспомогательными, то в ЦП отклонения играют решающую роль и формируют целевую функцию.
В условиях многих целей, их сложности и противоречивости, а так же ограниченности ресурсов, одни цели могут быть достигнуты за счет других. А это приводит к необходимости установления определенной иерархии целей так, чтобы цели нижнего приоритета выполнялись бы при условии реализации целей высшего приоритета. А поскольку возможна ситуация, когда не все цели могут быть достигнуты, то ЦП реализует алгоритм достижения возможного (удовлетворительного) уровня многих целей. Этим оно отличается от ЛП, в котором получают оптимальное решение для одной цели.
Для установления приоритетности целей, отклонения в целевой функции ЦП взвешиваются при помощи специальных коэффициентов. Каждая цель формируется при помощи целевого ограничения, включающего отклонения от этой цели. Кроме целевых ограничений, модель задачи ЦП может содержать обычные, системные ограничения. Поскольку отклонения от цели могут быть двоякими, то для каждой цели обычно вводят по две отклоняющих переменных, показывающих недо- и перевыполнение цели (обозначаются d- и d+).
Как уже отмечалось, будучи сформулированной, задача ЦП может быть решена методами, используемыми идеей ЛП. Не следует задачи ЦП отождествлять с многокритериальными задачами или с задачами векторной оптимизации. Это особые разделы математического программирования, которые здесь не рассматриваются.
Рассмотрим реализацию основных идей и методов решения задач ЦП на примере.
Пример 1. Предположим, что для производства двух видов продукции фирма расходует два вида ресурсов. Известны нормы расхода каждого вида ресурса на производство единицы каждого вида продукции, объемы имеющихся ресурсов и прибыль от реализации единицы каждого вида продукции. Используя прошлый опыт и цели, стоящие перед фирмой на ближайшую перспективу, руководство фирмы ставит перед собой следующие цели в порядке их приоритетности:
1. Получить не менее 30 ед. прибыли.
2. По возможности максимально использовать ресурс 1 вида.
3. Желательно не перерасходовать ресурс 2 вида.
4. Обеспечить контрактную поставку продукции 2 вида не менее 7 единиц.
Для формулировки модели задачи предположим, что прибыль от реализации единицы продукции равна соответственно 7 и 6 единиц, расход 1ресурса на выпуск единицы каждого продукта равен 2 и 3 единицы, соответственно, а объем 1 ресурса равен 12 единиц. Для 2 ресурса соответственно 6 и 5, и 30 единиц.
Составим модель задачи ЦП.
Основные неизвестные модели: Хi — объем производства продукции 1 вида; X2 — второго.
Целевые ограничения:
По прибыли: 7x1+6x2+d1—-d1+=30 слева записан объем прибыли с учетом недовыполнения 1-й цели (d1-) или ее перевыполнения (d1+ ). Если цель будет недовыполнена, то величина недовыполнения (d1-) будет больше нуля (d1—>0) а перевыполнения (d1+) равна нулю (d1- = 0). И наоборот, в случае перевыполнения цели d1+>0, a d1—=0.
Если цель будет выполнена в точности, то d1+ = d1- = 0. В любом случае, по крайней мере одна из этих переменных будет равна нулю. Поскольку первая по приоритетности цель предусматривает получение не менее 30 ед.прибыли. то в целевой функции будем минимизировать недовыполнение, т.е. для этой цели, Z = P1d1-, где Р1 — весовой коэффициент.
Второе целевое ограничение: 2x1+3x2+d2—-d2+=12, где d2— и d2+
соответственно недо- и перевыполнение 2-й цели. Для максимизации использования 1-го вида ресурса будем минимизировать d2-, следовательно, на этом этапе Z=P1d1—+P2d2, причем P1>>P2 (P1 много больше P2).
Третье целевое ограничение: 6x1+5x2+d3—-d3+=30 и для реализации 3-й цели будем минимизировать d3+ , следовательно, Z = P1d— + P2d2— + P3d3+ + P4d4—.
Для реализации 4-й цели необходимо произвести продукции 2-го вида не менее 7 ед.,,следовательно, целевое ограничение примет вид: x2+d1—-d1+=7, а целевая функция: Z = P1d— + P2d2— + P3d3+ + P4d4—
где P1>>P2>>P3>>P4
Окончательно имеем: минимизировать общее отклонение Z = P1d— + P2d2— + P3d3+ + P4d4—
при условии, что
X1, X2, d1-, d1+ >=0
