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