XB = B-1* bj (2.11)
P = сBт *B-1 * bj (2.12)
В исходной вершине многогранника (начале координат) базисная матрица является единичной и квадратной, так как представлена дополнительными переменными – ресурсами.
. XB = B-1* bj = I* bj = bj (2.13)
P = сBт * B-1 * bj = 0*I* bj= 0 (2.14)
То есть, никакой продукции не производится и нет прибыли.
Ддя оценки полученного решения. используют выражение в правой части уравнения (2.10), которое представляет вектор относительных оценок (столбцов) небазисных переменных, называемых симплекс-критерием2:
dj = (сBт * В-1* aNq - cтN) (2.15)
Так как исходный базис (в начале координат) представлен единичной матрицей дополнительных переменныи, и потому (рТ*aNq=рТ*I=0) – относительные оценки (столбцов) небазисной переменной должны иметь отрицательные значения:
dj=(0- cтN)= - cтN (2.16)
которые определяют величину, роста целевой функции на единицу вводимой небазисной переменной - (2.10).
Как правило, из всех небазисных (столбцов) переменных выбирают ту, которая имеет самые высокие по модулю отрицательные значения. На каждом этапе решения можно вводить только одну переменную, В постепенном и поочередном введении в базис (B) основных переменных заключается решение задачи.
Но, когда относительные оценки всех небазисных столбцов переменных будут иметь положительные или нулевые значения – это значит, что получено оптимальное решение – и, при увеличении небазисной переменной, увеличения целевой функции не произойдет.
Заметим, что одновременно с решением прямой задачи, находят относительные оценки дополнительных переменных (ресурсов, соответствующих ограничениям прямой задачи), заданных вектором (dj):
(dJ) = (сBт * В-1* aNq - 0) = сBт * В-1= р т = yТ (2.25)
где:
(aNq) единичный вектор-столбец дополнительной небазисной переменной,
cтN=0 – прибыль дополнительных ресурсов.
Как следует из (2.25) двойственные оценки ресурсов (y) являются базисными оценками ресурсов (р т) основных переменных прямой задачи в точке (вершине) оптимального решения3 и представляют собой величину прироста целевой функции на единицу увеличения этого ресурса. При нудевой оценке ресурса (y=0), когда дополнительная переменная является базисной, роста целевой функции не произойдет, так как этот ресурс используется не полностью.
Таким образом, симпексный критерий является не только индикатором решения прямой задачи, но и двойственной оценкой используемых ресурсов (yТ), Заметим, что для оценки влияния изменений переменных (ресурсов (bj), коэффициентов изменения целевой функции (cj) и нормативных коэффицинтов матрицы (aij)) на изменение целевой функции используются, так называемые, маргинальные оценки, в том смысле, что они действительны лишь в таком диапазоне изменений переменных, когда текущий базис остается оптимальным. Определеие диапазона возможных изменений параметров переменных, в рамках оптимального решения, широко используется на практике, в пограммных продуктах линейного программирования и рассматривается в соответствующей литературе [7-12].
Итак, после оценка текущего решения и выбора лучшего столбца небазисной (aNq)) переменой, необходимой для направленного перехода из одной допустимой базисной вершины в другую (лучшую) нужно определить, в каком количестве выбранная переменная должна быть введена в базис, и какая переменная должна быть выведена из базиса. Это зависит от достаточности используемых ресурсов и их норм расхода. То есть, из базиса должен быть выведен тот ресурс, который обеспечивает минимальное количество введенной продукции, при существующих расходных нормах - при большем количестве продукции этого ресурса просто не хватит:
min (XBj / aBpq) = Xq (2.17)
где: индекс (p) обозначает номер строки минимального значения этого соотношения,
- индекс (q) - номер столбца дополнительной переменной, выводимой из базиса,
Введение4 небазисных столбцов переменных и замена базисных переменных на небазисные требует преобразования базисной матрицы, тесно соприкасаюшегося с Гауссовым исключением [5-9]. Рассмотрим последовательные этапы этого пересчета -
- на первом этапе, после замены номеров столбцов вводимого в базис и выводимого из него столбцов переменных, определяют направляющий элемент. Он находится в той строке вводимого столбца переменной, которая соответствует min (XBj / aBpq) - и равен (aBpq);
- на втором этапе рассчитывают значения всех элементов направляющей строки путем деления ее "старых" членов на направляющий элемент - именно в этом соотношении новая переменная замешает старую переменную:
aНpj= acpj / acpq (2.18)
aНpj - расчетный элемент,
acpj - исходный элемент,
aНpq - направляющий элемент,
- на третьем этапе производится пересчет оставшихся злементов таблицы. По экономическому содержанию этот расчет элементов тпблицы производится по аналогии с расчетом количества оставшегося i-го ресурса (aНij), как разности межлу исходным его значением (acij) и количествм затраченного (ресурса) на производство вводимой продукции (как произведения количества продукции (aНpj) на норму ее расхода (aciq )).
aНij = aСij - aНpj*aСiq (2.19)
где: aНij - расчетный элемент,
acij - исходнце данные (старой таблицы),
aНpj - элемент направляющей строкм в столбце расчетного элемента,
aciq - элемент исходной строки в столбце направляющего элемента.
На этом завершается решение прямой задачи, вместе с получением двойственных оценок ресурсов, индикатором которых являются положительные или нулевые значения симплексного критерия в оптимальной вершине многогранника.
3. РЕШЕНИЕ ЗАДАЧИ СИМПЛЕКСНЫМ МЕТОДОМ (практическая часть).
Математическая модель прямой задачи в матрично-векторной форме имеет следующий вид:
Целевая функция:
сNт * XN + сBт * XB =Р->mах
Ограничения:
N*XN+B*XB =bj
Условие неотрицательности:
XB≥0
XN=0
Решение задачи заключается в поочередном расчете 3-х симплексных таблиц, каждая из которых соответствует определенной вершине многогранника допустимых решений. Cимплекс-таблицы 1С. соответствует вершине многогранниеа, расположенной в начале координат.
Симплексная таблица 1C (начало координат)
bi i=1,2 | (N) | Базис (B) | XiB = bi *В-1= bi | aBi2= аNi 2* В-1 | min XiB / aBi2 | |||
XN1 aNi1 | XN2 aNi2 | XBj / XBj | (XB3) ai3 | (XB4) ai4 | ||||
400 | 5 | 20 | (XB3) | 1 | 0 | 400 | 20 | 20 |
450 | 10 | 15 | (XB4) | 0 | 1 | 450 | 15 | 30 |
cTN | 45 | 80 | cTB → | 0 | 0 | P= XiB* cIB =0 | ||
dj | -45 | -80 | рj → | 0 | 0 |
Приводим последовательные шаги итеративных вычислений
1 шаг - вычисление вектора базисных переменных (XiB):
XiB = bi * В-1 = bi
2 шаг - вычисление целевой функции (Р):
Р = XiB *cBJ
3 шаг - вычисление симплексного мультипликатора (ПJ) (оценки базисных ресурсов):
рJ = cBJ * В-1
4 шаг - вычисление симплексного критерия (dj) - относительных оценок небазисных переменных. (по столбцам небазисной матрицы).
dj = рJ *aNij - cNj
d1 = рJ *aNi1 - cN1
d2 = рJ *aNi2 - cN2
5 шаг - определение переменной, вводимой в базис. В базисную матрицу должен быть введен столбец коэффициентов (аNi2) переменной Х2, который имеет наибольшую (по модулю, отрицательную величину симплексного критерия (d2=-80).
6 шаг - пересчет вводимого в базис столбца коэффициентов. Эта операция выполняется последовательным умножением слева вектора (аNi 2) на обратную (единичную) матрицу (В-1)
aB i2= аNi 2 * В-1
7 шаг – определение i-го гесурса, обеспечивающего производство минимального количества вводимой в базис продукции (X2):
min (XBi / aB i2)
Так как (XBi /aB12=400/20=20) меньше, чем (XBi /aB22=450/15=30), то ресурс (bi=400, i=1) является определяюшим, а соответствующая ему дополнительная переменная X3 – подлежит выводу из базиса.
8 шаг - определение “направляющего” элемента. В соответствии с шагом 7 он находится во вводимом столбце коэффициентов продукции X2 в строке определяюшего ресурса и равен 20 (aB12=20).
На этом вычислительные операции первого этапа, связанные с определением исходного нулевого базиса и поиском новой вершины многогранника (нового базиса) завершены.
Операции второго этапа заключаются в формировании нового базиса (замены векторов, пересчете элементов матрицы) и проверки его на оптимальность. Результаты этих вычислений приведены в симплексной таблице 2С.
Симплексная таблица 2C
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
