И условии неотрицательности
x j ³ 0 ( j =1,n) |
(23) |
3.2.3 Задача о смесях
В пищевой промышленности возникает проблема составления рабочих смесей на основе исходных материалов, которые обеспечивали бы получение конечного продукта, обладающего определенными свойствами. К этой группе задач относятся задачи о выборе диеты, составления кормового рациона в животноводстве, составления смесей сырья для получения средневзвешенных показателей и т.п.
Высокий уровень затрат на сырье и необходимость повышения эффективности производства выдвигает на первый план следующую задачу: получить продукцию с заданными свойствами при наименьших затратах на сырье.
Например, имеется N видов сырья, с различными показателями качества - всего m показателей качества. Aij показатели качества для каждого вида сырья. Базовая величина показателей bj. Обозначим через cj стоимость единицы (тонны) сырья с различными показателями качества.
Требуется составить смесь таким образом, чтобы средневзвешенные показатели качества не превышали базовых величин. Xj – это количество сырья каждого вида, обеспечивающее базовые показатели при минимальных затратах:
Математическая модель задачи:
Найти |
|
(24) |
|
n |
|
min ЦФ = åcj xj |
|
|
|
i=1 |
|
При ограничениях |
|
(25) |
n |
|
|
åaij x j |
£ bi (i =1,m) |
|
i=1 |
|
|
x j ³ 0 |
( j =1,n) |
|
3.3 Симплексный метод
Для решения задач линейного программирования используют симплекс-
метод или метод последовательного улучшения плана. Суть метода заключается в переборе крайних точек плана и нахождение в каждой точке значения целевой функции. Все точки, в которых целевая функция принимает наихудшие значения, не нужны. Остается точка, в которой ЦФ принимает оптимальное значение (максимум или минимум).
Целевая функция – это функция, характеризующая оптимальное решение (качественная характеристика процесса). В зависимости от технологического процесса целевая функция может стремится, либо к максимуму, либо к
17
минимуму. Например, прибыль должна быть максимальна, а затраты на перевозки готовой продукции минимальны.
Для аналитического решения задач линейного программирования разработан специальный алгоритм направленного перебора вершин. Этот алгоритм обеспечивает переход от одной вершины к другой в таком направлении, при котором значение целевой функции от вершины к вершине улучшается.
В геометрии есть понятие «симплекс». Симплексом тела в k-мерном пространстве называют k+1 его вершин. Так, для плоскости при k=2 симплексом будут три вершины треугольника. Аналитический метод решения задачи линейного программирования называю симплекс-методом. Вычисления, обеспечивающие
определение значения целевой функции и переменных в одной вершине называют итерацией.
Симплексный метод предполагает:
∙Умение находить начальный опорный план.
∙Наличие признака оптимальности опорного плана.
∙Умение переходить нехудшему опорному плану.
Начальный опорный план представлен в таблице 4. Рассмотрим составление
начального опорного плана на примере задачи о наилучшем использовании ресурсов. Начальный опорный план составляется на основе математической модели (19), (20).
Таблица 4 – Начальный опорный план
БП |
СБ |
А |
X1 |
|
|
|
2 |
X5 |
0 |
4 |
1 |
X6 |
0 |
3 |
2 |
X7 |
0 |
3 |
0 |
ЦФj-Cj |
0 |
-2 |
|
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
6 |
-1 |
3 |
0 |
0 |
0 |
3 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
4 |
1 |
0 |
0 |
1 |
|
1 |
-3 |
0 |
0 |
0 |
-6 |
При составлении начального опорного плана в столбец «БП» вносятся базовые переменные. Базовыми называются переменные, которые входят в одно уравнение модели с коэффициентом 1, а в остальные с коэффициентом 0. Например, в задаче о наилучшем использовании ресурсов базовые переменные указывают на возможные остатки ресурсов.
Столбец «СБ» содержит значения прибыли с единицы продукции соответствующих базовых переменных. Столбец «А» содержит значения равные запасам сырья на предприятии. Столбец «Х1» содержит в первой строке значение прибыли с единицы выпускаемой продукции, далее расход каждого вида ресурса на выпуск единицы продукции Х1. Аналогичным образом заполняются оставшиеся столбцы X2, X3, X4, столбцы Х5, Х6, Х7 заполняются аналогично таблице 4.
Последняя строка начального опорного плана – это стока целевой функции или индексная строка. Значения в индексной строке рассчитываются по следующим формулам:
18
|
m |
× А0 |
D |
0 = å СБ j |
|
|
j=1 |
(26) |
|
m |
|
|
× Аj -C j |
|
D j = å СБ j |
||
|
j=1 |
|
Значения целевой функции равно соответственно 0.
Решения бывают допустимыми и оптимальными. Каждое решение имеет свой признак.
Признак 1.
Определяет является ли полученное решение допустимым. Решение является допустимым, если в столбце свободных членов (целевая функция не рассматривается) все члены не отрицательные.
Признак 2.
Признак 2 определяет наличие оптимального решения, при этом возможны два варианта:
1)целевая функция имеет минимальное значение в том случае, когда все элементы в строке целевой функции (свободный член не рассматривается) будут отрицательными.
2)Целевая функция имеет максимальное значение в том случае, когда все элементы в строке целевой функции будут положительными.
При неоптимальности начального опорного плана необходимо перейти к нехудшему опорному плану.
Для этого определяется разрешающий столбец. Разрешающий столбец определяется по максимальной по модулю оценке в индексной строке, в таблице 4 разрешающий столбец – Х2.
Разрешающая строка соответствует минимальному симплексному отношению, которое определяется как А/Хj. Хj – это соответствующие значения разрешающего столбца. В таблице 4 разрешающая строка первая.
В новой симплекс-таблице необходимо из столбца «БП» вывести одну из переменных и ввести другую. Для более короткого решения рекомендуется выводить из базиса переменную, соответствующую переменной разрешающей строки и внести переменную соответствующую базисному столбцу. В столбец «СБ» вносится значение прибыли с единицы продукции введенной новой базисной переменной.
Кроме того, при составлении новой симплекс-таблицы необходимо выполнять следующие правила симплексных преобразований:
1)все элементы разрешающей строки делятся на разрешающий элемент;
2)все элементы разрешающего столбца равны нулю, за исключением разрешающего элемента, он равен 1;
3)все остальные элементы таблицы находят по правилу прямоугольника. Правило прямоугольника формулируется следующим образом:
Чтобы получить элемент aij новой симплексной таблицы необходимо из
произведения угловых элементов главной диагонали вычесть произведение угловых элементов побочной диагонали и полученное число разделить на разрешающий элемент (на рисунке 3 выделенный рамкой)
19
аij |
главная |
aij0 |
|
|
побочная |
ai0j |
Разреш_элемент |
Рисунок 3 - Правило прямоугольников
Диагональ, содержащая разрешающий и искомый элемент новой таблицы, называют главной, а другую побочной. Прямоугольник мысленно выстаивают таким образом, чтобы в элементы главной диагонали входил искомый элемент и разрешающий элемент, а в элементы побочной диагонали элемент разрешающего столбца и элемент разрешающей строки.
После проведения симплексных преобразований определяется оптимальность нового опорного плана. Если в индексной строке нет отрицательных элементов, то план оптимален и прибыль от реализации продукции максимальна. При этом вид выпускаемой продукции и остатки ресурсов смотрятся в столбце «БП», а их количество в столбце «А». А если в индексной строке есть отрицательные элементы, то строится новый опорный план
иопределяется его оптимальность.
3.4Построение двойственных задач и их свойства
Каждой задаче линейного программирования соответствует двойственная задача. Двойственная задача формулируется по следующим правилам:
1)каждому i-му ограничению исходной задачи соответствует переменная двойственной задачи, которую называют двойственной переменной;
2)каждой переменной исходной задачи соответствует ограничение двойственной задачи (ДЗ). Например, в исходной задаче три переменных, значит, ДЗ должна иметь три ограничения;
3)матрица коэффициентов при двойственных переменных в ограничениях двойственной задачи является транспонированной матрицей коэффициентов при
переменных в ограничениях исходной задачи. Например, |
é1 |
1 |
2 ù |
. Тогда |
||
А = ê |
5 |
ú |
||||
|
|
|
ë7 |
3û |
|
|
é1 |
7 |
ù |
|
|
|
|
транспонированная матрица АТ = ê1 |
5 |
ú . |
|
|
|
|
ê |
|
ú |
|
|
|
|
ê |
|
ú |
|
|
|
|
ë2 |
3û |
|
|
|
|
|
4) |
если в исходной задаче ограничения имеют знаки неравенств ≤, то в ДЗ ≥. |
5) |
правые части ограничений в ДЗ равны коэффициентам при переменных в |
|
целевой функции исходной задачи; |
|
20 |
6)коэффициенты при двойственных переменных в целевой функции ДЗ равны правым частям ограничений исходной задачи;
7)максимизация целевой функции исходной задачи заменяется минимизацией целевой функции в ДЗ.
Например, исходная задача линейного программирования имеет вид:
ìЦФ = 4x1 + 5x2 + 9x3 ®max |
|
ï |
. |
ïíx1 + x2 + 2x3 £16 |
|
î7x1 + 5x2 + 3x3 £ 25 |
|
Двойственная задача на основе вышеизложенных указаний будет иметь вид:
ìЦФД =16y1 + 25y2 |
®min |
|||||
ïy |
|
+ 7y |
2 |
³ 4 |
|
|
ï 1 |
|
|
|
|
||
ï |
|
+ 5y2 |
³ 5 |
. |
||
íy1 |
||||||
ï2y + 3y |
2 |
³ 9 |
|
|||
ï |
|
1 |
|
|
|
|
ïy |
i |
³ 0; |
|
i =1,2 |
|
|
î |
|
|
|
|
|
|
В общем виде ДЗ имеет вид:
ì |
m |
yi |
|
ïЦФД = åbi |
® min |
||
ï |
i=1 |
|
|
ï m
íåaij yi ³ c j
ïi=1
ïïyi ³ 0
î
Важное свойство двойственной задачи заключается в том, что max ЦФ = min ЦФД.
Двойственная переменная yi является коэффициентом при bi и, следовательно, показывает, как изменяется ЦФ при изменении ресурса bi на единицу. Двойственные переменные называют двойственными оценками. В электронных таблицах Excel двойственная оценка называется теневой ценой. Существенным является то, что для нахождения двойственных оценок решать двойственную задачу не требуется. Их значения уже находятся в симплексной таблице оптимального решения исходной задачи.
Если некоторый i-ый ресурс используется не полностью, т.е. имеется резерв, значит, дополнительная переменная в ограничении для данного
ресурса будет больше нуля, а двойственная оценка этого ограничения равна нулю.
В двойственную задачу для перехода от неравенств к равенствам вводятся дополнительные двойственные переменные. Смысл дополнительных двойственных переменных заключается в следующем: если основные переменные (например, х1, х2, х3) вошли в оптимальное решение, то дополнительные переменные (y4, y5, y6) равны нулю. Если основные переменные не вошли в оптимальное решение, т.е. равны нулю, то
соответствующие им дополнительные переменные имеют положительное значение. Дополнительные переменные двойственной задачи показывают
насколько уменьшиться значение целевой функции при принудительном выпуске единицы данной продукции.
21