Постановка задачи

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

Одним из возможных направлений реализации подобного рода задач и явилась разработка в начале 60-х годов прошлого столетия идей целевого программирования.

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

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

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

Не следует путать задачи ЦП с многокритериальными задачами или с задачами векторной оптимизации. Это особые разделы математического программирования, которые здесь не рассматриваются.

Рассмотрим реализацию основных идей и методов решения задач ЦП на примере.

Пример 5.1. Предположим, что для производства двух видов продукции фирма расходует два вида ресурсов. Известны нормы расхода каждого вида ресурса на производство единицы каждого вида продукции, объёмы имеющихся ресурсов и прибыль от реализации единицы каждого вида продукции. Используя прошлый опыт и цели, стоящие перед фирмой на ближайшую перспективу, руководство фирмы ставит перед собой следующие цели в порядке их приоритетности:

1. Получить не менее 30 ед. прибыли.

2. По возможности максимально использовать ресурс 1-го вида.

3. Желательно не перерасходовать ресурс 2-го вида.

4. Обеспечить контрактную поставку продукции 2-го вида не менее 7 единиц.

Решение. Для формулировки модели задачи предположим, что прибыль от реализации единицы продукции равна соответственно 7 и 6 единиц, расход 1-го ресурса на выпуск единицы каждого продукта равен 2 и 3 единицы соответственно, а объём 1-го ресурса равен 12 единиц. Для 2-го ресурса эти показатели соответственно равны 6, 5 и 30 единиц.

Составим модель задачи ЦП.

Основные неизвестные модели: х₁ – объём производства продукции первого вида; х₂ – второго вида.

Целевые ограничения:

По прибыли: 7х₁ + 6х₂ + d₁^- – d₁⁺ = 30; слева записан объём прибыли с учётом недовыполнения (d₁^-) или перевыполнения (d₁⁺) 1-й цели. Если 1-я цель будет недовыполнена, то величина недовыполнения (d₁^-) будет больше нуля (d₁^- > 0), тогда величина перевыполнения (d₁⁺) будет равна нулю (d₁⁺ = 0). И наоборот, в случае перевыполнения цели d₁⁺ > 0, а d₁^- = 0. Если цель будет выполнена в точности, то d₁⁺ = d₁^- = 0. В любом случае по крайней мере одна из этих переменных будет равна нулю. Поскольку первая по приоритетности цель предусматривает получение не менее 30 ед. прибыли, то в целевой функции будем минимизировать недовыполнение, т.е. для этой цели в целевой функции будет слагаемое P₁d₁^-, где P₁ – весовой коэффициент.

Второе целевое ограничение имеет вид: 2x₁ + 3x₂ + d₂^- – d₂⁺ = 12, где d₂^- и d₂⁺ соответственно недо- и перевыполнение 2-й цели. Для максимизации использования 1-го вида ресурса будем минимизировать d₂^-, следовательно, на этом этапе Z = P₁d₁^- + P₂d₂^-, причём P₁ >> P₂ (P₁ значимо больше P₂).

Третье целевое ограничение: 6x₁ + 5x₂ + d₃^- – d₃⁺ = 30 и для реализации 3-й цели будем минимизировать d₃⁺, следовательно, на этом этапе формирования целевой функции будем иметь Z = P₁d₁^- + P₂d₂^- + P₃d₃⁺.

Для реализации 4-й цели необходимо произвести продукции 2-го вида не менее 7 ед., следовательно, целевое ограничение примет вид:

x₂ + d₄^- – d₄⁺ = 7, а целевая функция – Z = P₁d₁^- + P₂d₂^- + P₃d₃⁺ + P₄d₄ ^-, где P₁ >> P₂ >> P₃ >> P₄ .

Окончательно имеем: минимизировать общее отклонение

Z = P₁d₁^- + P₂d₂ ^- + P₃d₃⁺ + P₄d₄^-

при условии, что

7x₁ + 6x₂ + d₁ ^- – d₁⁺ = 30;

2x₁ + 3x₂ + d₂ ^- – d₂⁺ = 12;

6x₁ + 5x₂ + d₃ ^- – d₃⁺ = 30;

x₂ + d₄ ^- – d₄⁺ = 7;

x₁, x₂, d_i^-, d_i⁺ ³ 0.

Это и есть модель задачи ЦП.