Курсовая работа: Анализ на чувствительность двойственных оценок
сформулировать двойственную задачу и найти оптимальные планы прямой и двойственной задачи.
найти интервалы устойчивости двойственных оценок по отношению к изменениям ресурсов каждого типа.
выявить изменения общей стоимости изготовляемой продукции, определяемой оптимальным планом ее производства при уменьшении количества ресурса 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 | ||
