Математическая модель задачи

Минимизировать

                                                                  (4.35)

при условиях

,                                                                               (4.36)

;                                                                                  (4.37)

;                                                                                  (4.38)  

.                                                                                  (4.39)

    Ограничения модели характеризуют:

(4.36) – балансы распределения сырья по каждому сырьевому району;

(4.37) – балансы удовлетворения потребителей в сырье в каждом пункте
производства;

(4.38) – балансы производства и распределения продукции в каждом
пункте;

(4.39) – балансы удовлетворения потребностей в готовой продукции
каждого потребителя.

    В модели (4.36) – (4.39) комплексно решается проблема размещения предприятий с учётом их связей и с пунктами снабжения сырьём, и с пунктами потребления готовой продукции.

Для задачи выполнено условие баланса  – всё сырьё полностью перерабатывается, спрос всех потребностей удовлетворяется.

Задача решается по методу «фиктивной диагонали». Предприятия по производству продукции на первом этапе выступают потребителями сырья, на втором – поставщиками готовой продукции. Причём их мощности определяются из решения задачи. Задача решается в таблице 4.4.

Таблица 4.4 – Метод «фиктивной диагонали»

		Пункты производства				Пункты потребления
		А1	А2	...	Аm	B1	B2	…	Bn
Пункты произ- водства сырья	Q1	C11	C12		C1m	M	M		M
	Q2	C21	C22	I	C2m	M	M	II	M
	Qp	Cp1	Cp2		Cpm	M	M		M
Пункты произ- водства проду- кции	А1	0	M		M	C11’	C12’		C1n’
	А2	M	0	III	M	C21’	C22’	IV	C2n’
	Аm	M	M	M	0	Cm1’	Cm2’		Cmn’

Таблица 4.4 состоит из четырёх блоков. В 1-м блоке отражаются связи поставщиков сырья с перерабатывающими предприятиями. Во втором блоке – связи поставщиков сырья с потребителями готовой продукции. Поскольку потребителям необходима готовая продукция, эти связи запрещаются тарифами М → + ∞, что обеспечивает условие оптимальности для соответствующих клеток таблицы на всех этапах решения. Третий блок образуется строками и столбцами, относящимися к обрабатывающим предприятиям. Продукция перевозится потребителю, а не другому обрабатывающему предприятию, поэтому связи предприятий друг с другом блокируются запретительными тарифами М. При любом расположении блоков в таблице такие клетки будут представлять диагональ соответствующего блока. Ставя здесь нулевые тарифы, мы «разрешаем» сюда поставки, они будут означать размер неиспользованной мощности соответствующего предприятия. Поскольку на самом деле поставки, указанные в этой диагонали, не осуществляются, они фиктивные, а сама диагональ называется фиктивной. В четвёртом блоке отражаются связи пунктов производства продукции с пунктами потребления этой продукции.

Далее задача решается по методу потенциалов. При нахождении первоначального плана заполняется 4-й блок, затем «фиктивная» диагональ, затем 1-й блок.

Если в задаче допускаются прямые связи поставщиков сырья с потребителями готовой продукции, запретительные тарифы М в соответствующих клетках третьего блока снимаются и ставятся реальные тарифы C_rj.

Глава 5. Целевое программирование

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

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

Одним из возможных направлений реализации подобного рода задач и явилась разработка в начале 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.

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