Курсовая работа: Анализ на чувствительность двойственных оценок

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

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

В таблице 1.1 первые m строк определяются исходными данными задачи, а показатели (m+1)-ой строки вычисляют. В этой строке в столбце вектора P0 записывается значение целевой функции, которое она принимает при данном опорном плане, а в столбце вектора Pj – значение

.

Значение F0 равно скалярному произведению вектора Р0 на вектор сбаз:

.

После заполнения таблицы (1.1) исходный опорный план проверяют на оптимальность. Для этого просматривают элементы (m+1) – ой строки таблицы. В результате может иметь место один из следующих трех случаев:

1) Значения Δj больше или равны нулю для всех ;

2) Δj<0 для некоторого j и все соответствующие этому индексу величиныaij<0 для ;

3) Δj<0 для некоторых индексов j, и для каждого такого j по крайней мере одно из чисел aij>0.

В первом случае на основании признака оптимальности исходный опорный план является оптимальным. Во втором случае целевая функция не ограничена сверху на множестве планов, а в третьем случае можно перейти от исходного плана к новому опорному плану, при котором значение целевой функции увеличится. Этот переход от нового опорного плана к другому осуществляется исключением из исходного базиса какого-нибудь из векторов и введением в него нового вектора, исходя из максимальной абсолютной величины отрицательных чисел Δj. Если таких чисел несколько, то в базис вводится вектор, имеющий тот же индекс, что и максимум из чисел cj , где Δj<0.

Пусть , остальные Δj ³ 0, следовательно, в базис вводится вектор Pk. Для того чтобы определить вектор, подлежащий исключению из базиса, находим минимальное значение отношения: .

Пусть это достигается для некоторого i=r. Тогда из базиса исключается вектор Рr, а число ark называют разрешающим (генеральным) элементом. Столбец и строку, на пересечении которых находится элемент ark называют направляющими (генеральными).

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

(1.6)

(1.7)

После вычисления aij и bi согласно формулам (1.6) и (1.7) их значения заносят в новую таблицу. Элементы (m+1)-ой строки вычисляются на основе их определения. После заполнения новой симплекс-таблицы просматривают элементы (m+1)-ой строки. Если все ≥0, то новый опорный план является оптимальным. Если же среди указанных чисел имеются отрицательные, то, используя описанную выше последовательность действий, находят новый опорный план. Этот процесс продолжают до тех пор, пока либо не получают оптимальный план задачи, либо не устанавливают ее неразрешимость

1.2 Двойственная задача линейного программирования

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

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

(1.8)

при условиях

(1.9)

(1.10)

Определение. Задача, состоящая в нахождении минимального значения функции

(1.11)

при условиях

(1.12)

(1.13)

называется двойственной по отношению к задаче (1.8)–(1.10).

Задачи (1.8)–(1.10) и (1.11)–(1.13) образуют пару задач, называемую в линейном программировании двойственной парой.

1.2.1 Правила составления двойственной задачи

Двойственная задача по отношению к исходной составляется согласно следующим правилам:

Целевая функция исходной задачи (1.8)–(1.10) исследуется на максимум, а целевая функция двойственной (1.11)–(1.13) –на минимум.

Матрица, составленная из коэффициентов при неизвестных в системе ограничений (1.9) исходной задачи (7.1)–(7.3), и аналогичная матрица в двойственной задаче (1.8)–(1.10) получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов – строками).

Число переменных в двойственной задаче (1.11)–(1.13) равно числу соотношений в системе (1.9) исходной задачи (1.8)–(1.10), а число ограничений в системе (1.12) двойственной задачи–числу переменных в исходной задаче.

Коэффициентами при неизвестных в целевой функции (1.11) двойственной задачи (1.11)–(1.13) являются свободные члены в системе (1.9) исходной задачи (1.8)–(1.10) а правыми частями в соотношениях системы (1.12) двойственной задачи – коэффициенты при неизвестных в целевой функции (1.8) исходной задачи.

Если переменная , исходной задачи (1.8)–(1.10) может принимать только лишь положительные значения, то j-е условие в системе (1.12) двойственной задачи (1.11)–(1.13) является неравенством вида «». Если же переменная  может принимать как положительные, так и отрицательные значения, то j-е соотношение в системе (1.12) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (7.2) исходной задачи (1.8)–(1.10) и переменными двойственной задачи (1.11)–(1.13) , т.е. если i-е соотношение в системе (1.9) исходной задачи является неравенством, то i-я переменная двойственной задачи . В противном случае переменная  может принимать как положительные, так и отрицательные значения.

1.2.2 Правила анализа на чувствительность двойственной оценки

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

Рассмотрим пару двойственных задач.

Исходная задача: найти максимум функции

(7.7)

при условиях

 (7.8)

 (7.9)

Двойственная задача: найти минимум функции

(7.10)

при условиях

(7.11)

Предположим, что задача (7.7)–(7.9) имеет невырожденные опорные планы и хотя бы один из них является оптимальным.

Максимальное значение целевой функции (7.7) задачи (7.7)–(7.9) будем рассматривать как функцию свободных членов системы линейных уравнений (7.8): .

Теорема. В оптимальном плане двойственной задачи (7.10), (7.11) значение переменной  численно равно частной производной функции  по данному аргументу, т. е.

(7.12)

Последнее равенство означает, что изменение значений величин  приводит к увеличению или уменьшению . Это изменение  определяется величиной  и может быть охарактеризовано лишь тогда, когда при изменении величин  значения переменных  в оптимальном плане соответствующей двойственной задачи (7.10), (7.11) остаются неизменными. Поэтому представляет интерес определить такие интервалы изменения каждого из свободных членов системы линейных уравнений. (7.8), в которых оптимальный план двойственной задачи (7.10), (7.11) не меняется. Это имеет место для всех тех значений , при которых столбец вектора  последней симплекс-таблицы решения задачи (7.7)–(7.9) не содержит отрицательных чисел, т. е. тогда, когда среди компонент вектора нет отрицательных. Здесь  — матрица, обратная матрице В, составленной из компонент векторов базиса, который определяет оптимальный план задачи (7.7)–(7.9).

Таким образом, если найдено решение задачи (7.7)–(7.9), то нетрудно провести анализ устойчивости двойственных оценок относительно изменений . Это, в свою очередь, позволяет:

1. проанализировать устойчивость оптимального плана задачи (7.10), (7.11) относительно изменений свободных членов системы линейных уравнений (7.8),

2. оценить степень влияния изменения , на максимальное значение целевой функции задачи (7.7)–(7.9), что дает возможность определить наиболее целесообразный вариант возможных изменений .

Вывод

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

линейный симплекс программирование двойственный

2. Практическая часть

2.1 Постановка задачи

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

Таблица 2

Исходные данные

Требуется:

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

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

выявить изменения общей стоимости изготовляемой продукции, определяемой оптимальным планом ее производства при уменьшении количества ресурса I типа на 130 единиц и увеличения количества ресурсов II и III типа на 120 и 110 единиц.

Провести анализ возможного изменения общей стоимости продукции как при изменении объемов каждого из ресурсов по отдельности, так и при одновременном изменении в указанных размерах.

2.2 Математическая модель исходной задачи

Пусть xj – количество изделий j –го вида; aij – затраты времени на единицу продукции вида j на оборудовании i-го типа, cj – стоимость единицы изделия вида j, si – общий фонд рабочего времени на оборудовании типа i.

Целевая функция:

L = 3x1 + 2x2 + 5x3 → max

Ограничения:

x1 +x2 +x3 + x4=430

3x1 + 2x3 + x5 = 46

x1 + 4x2 +x6 =420

xj ≥ 0 , j = 1,6

Составляется матрица из коэффициентов при неизвестных в системе ограничений исходной задачи.

А=

2.3 Математическая модель двойственной задачи

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

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

Найти минимум функции:

Ограничения:

И составляется аналогичная матрица, которая получается транспонированием (т.е. заменой строк столбцами, а столбцов – строками).

АТ=

2.4 Нахождение решения исходной задачи

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

Целевая функция:

L = 3x1 + 2x2 + 5x3 → max

Ограничения:

x1 +x2 +x3 + x4=430

3x1 + 2x3 + x5 = 46

x1 + 4x2 +x6 =420

xj ≥ 0 , j = 1,6

Сначала проверяется, можно ли решить задачу симплексным методом:

m < n; bi ≥ 0, i= 1,3; задача записана в форме основной задачи линейного программирования. Имеется исходный опорный план X =(0,0,0,0,430,460,420). Далее заполняется первая симплексная таблица (таблица 3):

Таблица 3

Симплекс-таблица (1-ая итерация)

Страницы: 1, 2, 3, 4