Анализ на чувствительность двойственных оценок (стр. 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 Математическая модель исходной задачи

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

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

L = 3x₁ + 2x₂ + 5x₃ → max

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

x₁ +x₂ +x₃ + x₄=430

3x₁ + 2x₃ + x₅ = 46

x₁ + 4x₂ +x₆ =420

x_j ≥ 0 , j = 1,6

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

А=

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

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

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

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

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

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

А^Т=

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

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

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

L = 3x₁ + 2x₂ + 5x₃ → max

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

x₁ +x₂ +x₃ + x₄=430

3x₁ + 2x₃ + x₅ = 46

x₁ + 4x₂ +x₆ =420

x_j ≥ 0 , j = 1,6

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

m < n; b_i ≥ 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=∆₃= - 8. Таким образом, столбец Р₃ является генеральным. Среди элементов a_i1 находится такой, который соответствует минимальному значению b_i / a_i1. Это элемент a₂₁. Таким образом, 2-ая строка является генеральной. Все элементы b_i и a_ij пересчитываются соответственно по формулам (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-я строка. Все элементы b_i и a_ij пересчитываются соответственно по формулам (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,) является оптимальным.