Методы оптимизации и распределения ресурсов на основе задач линейного программирования

Подобные методы широко применимы в производстве, транспорте, организации процессов, в обучении, руководстве персоналом и др. К числу наиболее известных задач, решаемых этим методом, относятся задача о назначениях, транспортная задача и другие.

Задача о назначениях и распределении работ является частным случаем транспортной задачи,

В которой приняты следующие допущения: число поставщиков m равно числу потребителей n; запасы каждого поставщика a_j = 1; заявки каждого потребителя b_j= 1; каждый поставщик может поставлять грузы только одному потребителю; каждый потребитель может получать груз только от одного поставщика.

Если сумма запасов A у поставщика равняется сумме всех заявок B потребителей, то такую транспортную задачу называют сбалансированной; если A ≠ B, то задача является несбалансированной, и ее математическая модель может иметь вид:

_{m n}

F= ∑ ∑ c_ij x_ij → min

^{i=1 j=1}

_{n ____}

∑ x_ij ≤ a_{j; j} = 1,m;

ⁱ⁼¹

_{m ____}

∑ x_ij ≥ b_j; ; i= 1,n

^j=1

x_ij ≥0;

Знак равенства в ограничениях для запасов a_j означает, что объем груза, вывозимый от любого

i-го поставщика по заявкам всех потребителей, не может превышать имеющегося у него запаса, при этом часть запаса груза может оставаться не вывезенной. Аналогично знак неравенства в ограничениях для заявок b_j означает, что груз, получаемый j– м поставщиком, должен быть не меньше заявки, но превышение заявки при этом допускается.

Модель сбалансированной задачи является частным случаем модели несбалансированной задачи.

Методы многопараметрической оптимизации в процессах планирования, управления и принятия решений.

Любой вид производства или сферу деятельности можно охарактеризовать двумя основными параметрами:

Объемом выпуска продукции Об, определяемым различными показателями (валовой, реализованной, чистой нормативной продукцией и др. или просто в рублях) и ее качеством К. На практике обычно стремятся к увеличению как выпуска продукции, так и к повышению ее качества, то есть переходят к решению многопараметрических задач.

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

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

Первая постановка Об = f(к₃):Вторая постановка K=f (Об₃):

_{n n}

Об = ∑ c_j x_j → max K = ∑ S_j x_j → max_;

^{j=1 j=1}

_{n n}

K = ∑ S_j x_j ≥ K₃ ; Об = ∑ c_j x_j ≥ Об₃

^{j=1 j=1}

_{n n}

∑ a_ij x_j ≤ b_i ∑ a_ij x_j ≤ b_i;

^j=1 ___ ___ ^j=1 ___ ___

d_j ≤ x_j ≤ D_j; j = 1, n; i = 1, m d_j ≤ x_j ≤ D_j; j = 1, n; i = 1, m

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

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

Таблица 1. Исходные данные для выбора лучшего варианта системы.

Параметры системы	Вариант системы
Q, штук в минуту
C, руб

Решение: Интегральный критерий должен обеспечивать операции с параметрами и учет относительной важности каждого параметра с помощью коэффициентов веса. Улучшение желательных параметров должно увеличивать значение критерия, а рост нежелательных параметров – снижать его значения. В качестве критерия можно принять целевую функцию, которая может быть записана следующим образом:

_{Qi Ci}

K_i = a₁ ×— - a₂ × —, где a_1, a_{2 –} коэффициент веса;

^{Qh Ch}

Q_h и С_h – нормирующие значения производительности Q и стоимости C системы.

Таким образом, критерий Ki увеличивается при повышении производительности и уменьшении стоимости сравниваемых вариантов. Следовательно лучшим является вариант, для которого значение K будет наибольшим, т.е max K = max {K₁, K₂, K₃, K₄}.

Для определения критерия в качестве нормирующих значений принимаем: Q_h = Q_max = 60;

C_h = C_max = 500. Определим значение критерия Ki для трех основных ситуаций, при которых а) важна лишь производительность (a₁=1, a₂=0); б) производительность и стоимость одинаково важны (a₁= 0,5, a₂=0,5) в) важна лишь стоимость (a₁= 0, a₂=1).

Значения K_i применимые к выделенным ситуациям и четырем сравниваемым вариантам системы, приведены в таблице 2, откуда следует, что наибольшее значение критерия зависит не только от параметров вариантов, но и от принятых коэффициентов веса.

Таблица 2. Решение примера при трёх случаях.

Ситуация	весовые коэффициенты	Варианты систем
a1	a2
			0,33	0,5		0,83
	0,5	0,5	0,666	-0,15		0,22
			-0,2	-0,8	-1	-0,4

Для ситуации 1 лучшим оказывается вариант 3, для ситуации 2-вариант 1, для ситуации 3 – вариант 1 (вариант 2 в каждой из трех рассмотренных ситуаций будет худшим).

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

2.4. Задачи линейного программирования в оперативном управлении производством и принятии решений.

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

Пример: Пусть предприятием выпускается продукция четырех видов П1-П4 с использованием для этого ресурсов, виды и нормы расхода по которым, а также уровень получаемой от их реализации прибыли приведен в таблице 3. Необходимо получить вариант оптимального плана производства по критерию максимума прибыли.

Таблица 3 Исходные данные задачи плана производства.

Элемент модели	Вид продукции	Располагаемый ресурс
П1	П2	П3	П4
Ресурсы: трудовые
сырье
оборудование
Прибыль с единицы продукции плана
План	x1	x2	x3	x4

Решение: Математическая модель может быть записана в следующем виде:

F= 60x₁ + 70x₂ + 120x₃ + 130x₄ → max;

x₁+x₂+x₃+x₄ ≤ 16;

6x₁+5x₂+4x₃+3x₄≤ 110

4x₁+6x₂+10x₃+13x₄≤100

x_j≥0; j=1,4

При решении данной системы неравенств на ЭВМ получим следующий оптимальный план производства видов продукции: x₁= 10; x₂= 0; x₃ =4; при этом величина прибыли составляет F=1320.

Рассмотрим типовые примеры нахождения решения данной (и всех подобных) задач.

Переменные x₁ x₂ x₃ ...., называются основными. Если от данной системы неравенств перейти к системе уравнений, то в каждое неравенство необходимо добавить по одной дополнительной переменной yi, i=1,m.

Т.е система примет вид:

F= 60x₁ + 70x₂ + 120x₃ + 130x₄ → max;

x₁+x₂+x₃+x₄₊ y₁ =16

6x₁+5x₂+4x₃+3x₄ + y₂ =110;

4x₁+6x₂+10x₃+13x₄+y₃ = 100;

x_j≥0; j=1,4; yi ≥ 0, i= 1,3

Перепишем систему уравнений в следующем виде:

F=0 – (- 60x₁ – 70x₂ – 120x₃- 130x₄) → max;

y₁= 16-(x₁+x₂+x₃+x₄);

y₂= 110-(6x₁+5x₂+4x₃+3x₄ );

y₃=100 – (4x₁+6x₂+10x₃+13x₄ );

x_j≥0

Эту систему можно представить в виде симплекс – таблицы (табл 4), составляемой следующим образом: целевую функцию и базисные переменные, находящиеся в уравнениях слева, запишем в первый столбец таблицы; свободные переменные, заключенные в скобки, вынесем в первую строку таблицы, а в остальные столбцы запишем свободные члены и коэффициенты перед свободными переменными (симплекс – таблицы служат основой для решения задач линейного программирования). В этой таблице переменные являющиеся свободными (x₁x₂x₃x₄) равны нулю (по определению свободных переменных). Тогда базисные переменные (y₁ y₂ y₃), а также целевая функция F равны свободным членам, т.е y₁= 16, y₂= 110, y₃=100, F=0.

Таблица 4 Симплекс таблица

величина	свободный член	Вид продукции
x1	x2	x3	x4
F		-60	-70	-120	-130
y1
y2
y3

Решение является допустимым, если в симплекс- таблице в столбце свободных членов все значения, относящиеся к базисным переменным (y₁ y₂ y₃), являются не отрицательными; оптимальное решение связано с минимумом или с максимумом целевой функции F, определяется по двум признакам: а) целевая функция имеет минимальное значение, если решение является допустимым (т.е свободные члены являются не отрицательными) и все элементы в строке целевой функции (свободный член при этом не учитывается) являются отрицательными; б) целевая функция при этом равняется свободному члену. Таким образом по таблице 4 можно сделать вывод, что нами получено оптимальное решение для случая минимизации целевой функции (действительно, если x₁+x₂+x₃+x₄ =0, значит, никакая продукция не выпускается и прибыль F=0).

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

Применительно к нашей задаче симплекс- таблица, полученная после второй итерации, приобретет вид таблицы 5, из которой видно, что в столбце свободных членов все элементы положительные, следовательно, решение является допустимым. В строке целевой функции все элементы также положительные, следовательно, это решение является оптимальным при максимизации целевой функции. При этом оптимальным планом является x₁ =10, x₃=6 (базисные) x₂=x₄=0 (свободные); F=1320.

Таблица 5 Симплекс-таблица после второй итерации

величина	свободный член	Вид продукции
y1	x2	y3	x4
F
x1		5/3	2/3	-1/6	-1/2
x2		-23/3	-1/3	1/3
x3		-2/3	1/3	1/6	3/2

Понятие о двойственности решений.

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

Пример: Пусть заданна следующая исходная модель задачи:

F=4x₁+5x₂+9x₃→max;

X₁+x₂+2x₃≤1.6; (а)

7x₁+5x₂+3x₃≤ 25. (б)

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

1) каждому i –му ограничению исходной задачи, соответствует переменная двойственной задачи, называемая двойственной переменной, обозначаемая Z _i. В данной системе ограничению (а) соответствует переменная Z₁

а ограничению (б) Z₂ .

2) Каждой переменной исходной задачи соответствует ограничение двойственной задачи;т.к в данной системе имеется три переменные x₁ x₂ x₃, то двойственная задача должна иметь три ограничения.

3) Матрица коэффициентов при двойственных переменных в ограничениях двойственной задачи является транспонированной матрицей коэффициентов при переменных состоящих в ограничениях. Для данной задачи получим:

4) Если в исходной задаче ограничения имеют знаки неравенств типа меньше (≤), то в двойственной они изменяются на противоположные типа больше (≥).

5) Правые части ограничений в двойственной задаче равняются коэффициентам при переменных в исходной задаче, а коэффициенты при двойственных переменных в целевой функции в двойственной задачи равняются правым частям ограничений исходной задачи.

6) Максимизация целевой функции исходной задачи заменяется минимизацией целевой функции двойственной задачи. Таким образом, получим:

Fg= 16 z₁+26z₂ → min;

z₁+7z₂≥4;

z₁+5z₂≥5;

2z₁+3z₂ ≥ 9;

z_i ≥ 0; i = 1,2

Важным свойством двойственной задачи является то, что max F = min Fg, при этом

_m

max F = ∑ b_i z_i.

^I=1

Таким образом, двойственная переменная оценивает влияние изменения каждого вида ресурса на целевую функцию.

Вопросы для самоконтроля по главе

1. Какие три компонента должна включать любая задача оптимизации?

2. Что называют допустимым решением задачи?

3. Какую транспортную задачу называют сбалансированной?

4. Какими двумя основными параметрами можно охарактеризовать любой вид производства или сферу деятельности?

5. По какому принципу составляются симплекс – таблицы?