2 Математическая модель
Математическая модель в общем виде:
при ограничениях
Вводятся обозначения для искомой задачи :
m – вид полуфабрикатов ,
n – сорта бензина ,
ai – пропорциональное содержание полуфабрикатов в бензине,
bj – ограничения полуфабрикатов в бензине, тыс.л.
Сij - стоимость бензина,
xij – объем выпуска бензина,
Z – минимальная стоимость всей продукции.
Математическая модель данной ЗЛП:
при ограничениях:
3 Метод реализации модели
Поставлена задача линейного программирования. Найти максимальное значение функции
Z=C1X1+C2X2+...+CnXn
п
ри
ограничениях
a11x1+a12x2+...+a1nxn=b1
a21x1+a22x2+...+a2nxn=b2
............................................
am1x1+am2x2+amnxn=bm
xj≥0(j=1,2,...n)
bi≥0(i=1,2,...m)
Предполагается, что система ограничений задачи содержит m единичных векторов, причем без ограничения общности можно положить, что единичными являются первые m векторов.
Z=C1X1+C2X2+...+CnXn
при ограничениях
x
1+a1,m+1
xm+1+...+a1nxn=b1
x2+a2,m+1 xm+1+...+a2nxn=b2
.....................................................
xm+am,m+1+xm+1+...+amnxn=bm
xj≥0(j=1,2,...n)
Алгоритм симплексного метода представляет собой способ целенаправленного перебора планов, чтобы значения линейной формы в задачах на минимум уменьшалось при переходе от одного опорного плана к другому, число шагов для достижения этой цели m≤k≤2m, где m-число уравнений или размеренность базиса.
Заполняется исходная таблица. После чего производится вычисления в последовательности:
- Подсчитывается Zj-Cj и определяется, не является ли рассматриваемый план оптимальным, т.е. не выполняется ли для всех xj условие: Zj-Cj≤0
- Если для некоторого значение Zj -Cj>0 , то выбирается вектор, который может быть введен в базис. Для этого разыскивается какое-нибудь , для которого max(Zj-Cj)=Zk-Ck>0 , тогда Pk вводится в базис.
- Выбирается вектор, который подлежит исключению из базиса. Это вектор для которого: для всех xik>0, тогда Pi –исключается из базиса.
-Если все , то линейная форма неограниченна снизу.
- После выделения направляющей строки и направляющего столбца, таблица преобразуется по формуле полного исключения.
В результате каждой итерации образуется новый опорный план. В конце концов, либо придем к оптимальному плану, либо убедимся в неограниченности линейной формы задачи.
Вычисления сводятся в табл.2
Таблица №2
i |
Б |
СБ |
Ро |
С1 |
С2 |
… |
С1 |
… |
Сm |
Cm+1 |
... |
Cj |
... |
Ck |
... |
Cn |
P1 |
P1 |
... |
P1 |
... |
Pm |
Pm+1 |
... |
Pj |
... |
Pk |
... |
Pn |
||||
1 |
P1 |
С1 |
X1 |
1 |
0 |
... |
0 |
... |
0 |
X1 |
... |
|
... |
|
... |
X1n |
2 |
P2 |
С2 |
X2 |
0 |
1 |
... |
0 |
... |
0 |
|
... |
|
... |
|
... |
X2n |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
|
... |
|
... |
... |
1 |
P1 |
С1 |
X1 |
0 |
0 |
... |
1 |
... |
0 |
|
... |
|
... |
|
... |
X1n |
... |
... |
... |
... |
… |
... |
... |
|
... |
... |
... |
... |
|
... |
|
... |
|
m |
Pm |
Сm |
Xm |
0 |
0 |
... |
0 |
... |
1 |
|
... |
|
... |
|
... |
Xmn |
m+1 |
|
|
Z0 |
0 |
0 |
... |
0 |
... |
0 |
|
... |
|
... |
|
... |
|