Таким образом, если найдено решение задачи (7.7)–(7.9), то нетрудно провести анализ устойчивости двойственных оценок относительно изменений
1. проанализировать устойчивость оптимального плана задачи (7.10), (7.11) относительно изменений свободных членов системы линейных уравнений (7.8),
2. оценить степень влияния изменения
Вывод
В теоретической части пояснительной записки к курсовой работе приведен краткий теоретический материал о формах представления задач линейного программирование, симплексный метод и метод двойственной задачи, необходимый для решения задач линейного программирования.
линейный симплекс программирование двойственный
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
Ограничения:
3x1 + 2x3 + x5 = 46
xj ≥ 0 , j = 1,6
Составляется матрица из коэффициентов при неизвестных в системе ограничений исходной задачи.
А=
2.3 Математическая модель двойственной задачи
Число переменных в двойственной задаче равно числу уравнений в системе исходной задачи, т. е. равно семи.
Целевая функция исходной задачи исследуется на максимум, а система условий содержит только уравнения. Поэтому в двойственной задаче целевая функция исследуется на минимум, а ее переменные могут принимать любые значения (в том числе и отрицательные). Следовательно, для исходной задачи двойственная задача такова:
Найти минимум функции:
Ограничения:
И составляется аналогичная матрица, которая получается транспонированием (т.е. заменой строк столбцами, а столбцов – строками).
АТ=
2.4 Нахождение решения исходной задачи
Задача записывается в форме основной задачи линейного программирования.
Целевая функция:
L = 3x1 + 2x2 + 5x3 → max
Ограничения:
3x1 + 2x3 + x5 = 46
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,) является оптимальным.