Анализ на чувствительность двойственных оценок (стр. 1 из 6)
Введение
Под термином «программирование» понимают выбор программных действий для решения задачи.
Математическое программирование представляет собой математическую дисциплину, занимающуюся изучением экстремальных задач и разработкой методов их решения. В зависимости от свойств функций раздел математического программирования можно рассматривать как ряд самостоятельных дисциплин. Задачи математического программирования делятся на задачи линейного и нелинейного программирования.
Задачи нелинейного программирования возникают в естественных и физических науках, техники, экономики, в сфере деловых отношений и в науке управления государством. Преобразование реальной задачи в задачу нелинейного программирования в значительной мере является искусством, направляемым теорией. Теория точно указывает, какая из многих возможных формулировок задачи решается наиболее эффективно, а какая не может быть решена вовсе [1].
Прежде всего, задачи математического программирования делятся на линейного и нелинейного программирования. При этом если все функции f и
линейные, то соответствующая задача является задачей линейного программирования. Если же хотя бы одна из указанных функции нелинейная, то соответствующая задача является задачей нелинейного программирования.Наиболее изученным разделом математического программирования является линейное программирование. Для решения задач линейного программирования разработан целый ряд эффективных методов, алгоритмов и программ [2].
Анализ линейного программирования имеет статическое оптимальное решение, по этому, как только изменяются исходные условия, полученное решение теряет свою актуальность. Анализ чувствительности задачи линейного программирования как раз и связан с исследованием возможных изменений полученного оптимального решения в результате изменений исходных данных задачи. Анализ чувствительности – это процесс, который реализуется после того, как получено оптимальное решение [1].
Данная курсовая работа посвящена общему методу решения задач линейного программирования, известному как симплекс-метод. Процесс решения любой задачи линейного программирования симплекс-методом имеет итерационный характер: однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор, пока не будет найдено оптимальное решение. Информация, которую можно получить с использованием симплекс-метода, не ограничивается оптимальным решением. Этот метод позволяет дать экономическую интерпретацию решения.
1. Теоретическая часть
1.1 Общая и основная задачи линейного программирования
Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции
n
L = ∑ cjxj(1.1)
j=1
при условиях
n
∑ aijxj ≤ bi (i=1,k) (1.2)
j=1
n
∑ aijxj = bi (i=k+1,m) (1.3)
j=1
xj ≥ 0 (j=1,l,l ≤ n), (1.4)
где aij, bi, cj – заданные постоянные величины и k ≤ m.
Функция (1.1) называется целевой функцией задачи (1.1) – (1.4), а условия (1.2) – (1.4) – ограничениями данной задачи.
Стандартной или симметричной задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1.1) при выполнении условий (1.2) и (1.4), где k=m и l=n.
Канонической или основной задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1.1) при выполнении условий (1.3) и (1.4), где k=0 и l=n.
Совокупность чисел X=(x1, x2, … , xn), удовлетворяющих ограничениям задачи (1.2) – (1.4), называется допустимым решением или планом.
План X*=(x1*, x2*, … , xn*), при котором целевая функция задачи (1.1) принимает свое максимальное (минимальное), значение, называется оптимальным.
Указанные выше три формы задачи линейного программирования эквивалентны в том смысле, что каждая из них с помощью несложных преобразований может быть переписана в форме другой задачи. Это означает, что если имеется способ нахождения решения одной из задач, то тем самым может быть определен оптимальный план любой из трех задач
1.1.1 Алгоритм симплексного метода
Симплексный метод решения задач линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет опорный план, и когда ее опорный план является невырожденным, причем, целевая функция исследуется на максимум).
Указанный переход возможен, если известен какой-либо исходный план. Рассмотрим задачу (1.1) - (1.4), где
; 
; 
;…; 
; 
;…; 
; 
.Так как
,то опорный план согласно признаку оптимальности будет иметь вид:
В опорном плане присутствует (n-m) – нулей. Этот план определяется системой единичных векторов P1,…,Pm, которые образуют базис m- мерного пространства, следовательно, некоторые из векторов
могут быть представлены в виде линейной комбинации векторов данного базиса. Пусть 
.Положим
; 
.Так как P1,…,Pm являются единичными векторами, то
и 
а 
, (1.5)где Δj – критерий остановки, j=
.В симплекс методе все решения связанные с определением оптимальности и выявлением целесообразности перехода к новому опорному плану принимаются в соответствии с ниже приведенными теоремами.
Теорема 1. (Признак оптимальности опорного плана) Опорный план
для задач (1.3), (1.4) является оптимальным, если все оценки
.Теорема 2. (Признак неограниченности сверху) Если
для некоторого 
и среди чисел 
нет положительных ( 
), то задачи (3), (4) являются неограниченными сверху на множестве плана.Сформулированные теоремы позволяют проверить, является ли найденный опорный план оптимальным, и выявить целесообразность перехода к новому плану.
Исследование опорного плана на оптимальность, а также дальнейший вычислительный процесс удобнее вести, если условия задачи и первоначальные данные, полученные после определения исходного опорного плана, записать в симплексную таблицу (таблица 1).
Таблица 1
Симплексная таблица
| i | базис | Cбаз | P0 | С1 | С2 | … | Cr | … | Сm | Cm+1 | … | Ck | … | Cn |
| P1 | P2 | … | Pr | … | Pm | Pm+1 | … | Pk | … | Pn | ||||
| 1 | P1 | C1 | b1 | 1 | 0 | … | 0 | … | 0 | a1m+1 | … | a1k | … | a1n |
| 2 | P2 | C2 | b2 | 0 | 1 | … | 0 | … | 0 | a2m+1 | … | a2k | … | a2n |
| … | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
| r | Pr | Cr | br | 0 | 0 | … | 1 | … | 0 | arm+1 | … | ark | … | arn |
| … | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
| m | Pm | Cm | bm | 0 | 0 | … | 0 | … | 1 | amm+1 | … | amk | … | amn |
| m+1 | F0 | D1 | D2 | … | Dr | … | Dm | Dm+1 | … | Dk | … | Dn |
В столбце Cбаззаписываются коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и векторы данного базиса.
В столбце P0 записываются положительные компоненты искомого опорного плана. В нем же в результате вычислений записываются компоненты опорного плана. Столбцы векторов Pj представляют собой коэффициенты разложения по векторам данного базиса.