Смекни!
smekni.com

Анализ на чувствительность двойственных оценок (стр. 3 из 6)

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

. Это, в свою очередь, позволяет:

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

2. оценить степень влияния изменения

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

Вывод

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

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


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

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

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

Таблица 2

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

Вид сырья Нормы затрат сырья Наличие ресурса
A B C
1 грузовик 1 1 1 430
2 Легковой автомобиль 3 0 2 460
3 мотоцикл 1 4 0 420
4 Цена ед. продукции 3 2 5

Требуется:

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

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

выявить изменения общей стоимости изготовляемой продукции, определяемой оптимальным планом ее производства при уменьшении количества ресурса 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-ая итерация)

i Базис
1
0 430 1 1 1 1 0 0
2
0 460 3 0 2 0 1 0
3
0 420 1 4 0 0 0 1
m+1 0 -3 -2 -5 0 0 0

В (m+1)-ой строке находится максимальная по абсолютной величине оценка ∆j=∆3= - 8. Таким образом, столбец Р3 является генеральным. Среди элементов ai1 находится такой, который соответствует минимальному значению bi / ai1. Это элемент a21. Таким образом, 2-ая строка является генеральной. Все элементы bi и aij пересчитываются соответственно по формулам (1.6) и (1.7). Новые данные заносятся в таблицу 4.


Таблица 4

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

i Базис
3 2 5 0 0 0
1
0 220 -1/2 1 0 1 -1/2 0
2
5 230 3/2 0 0 0 1/2 0
3
0 420 1 4 0 0 0 1
m+1 1150 9/2 -2 0 0 5/2 0

Новый опорный план: X =(0,0,230,220,0,420). Не все оценки ∆j ≥ 0 . Находятся генеральные строка и столбец. Это столбец Р2 и 2-я строка. Все элементы bi и aij пересчитываются соответственно по формулам (1.6) и (1.7). Новые данные заносятся в таблицу 5.

Таблица 5

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

i Базис
3 2 5 0 0 0
1
0 230 -3/4 0 0 1 -1/2 -1/4
2
5 230 3/2 0 1 0 1/2 0
3
2 105 1/4 1 0 0 0 1/4
m+1 1360 5 0 0 0 5/2 1/2

В (m+1)-ой строке все оценки ∆j ≥ 0. Найденный план X*=(0,230,0,230, 0,105,) является оптимальным.