Линейное программирование
Контрольная работа - Менеджмент
Другие контрольные работы по предмету Менеджмент
?ка ткани рисунка вида ;
- план выпуска ткани рисунка вида ;
- план выпуска ткани рисунка вида ;
Для начала решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы и определим максимальное значение целевой функции:
(X) = 49x1 + 33x2 + 76x3 + 109x4
при следующих условиях-ограничений:
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме):
x1 + 1x2 + 2x3 + 10x4 + 1x5 + 0x6 + 0x7 + 0x8 + 0x9 = 25000
x1 + 3x2 + 8x3 + 6x4 + 0x5 + 1x6 + 0x7 + 0x8 + 0x9 = 120000
x1 + 3x2 + 7x3 + 9x4 + 0x5 + 0x6 + 1x7 + 0x8 + 0x9 = 155000
x1 + 5x2 + 12x3 + 11x4 + 0x5 + 0x6 + 0x7 + 1x8 + 0x9 = 250000
x1 + 3x2 + 4x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 + 1x9 = 100000
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
312101000043860100023790010085121100010234100001
Решим систему уравнений относительно базисных переменных: (x5, x6, x7, x8, x9), полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,25000,120000,155000,250000,100000)
БазисBx1x2x3x4x5x6x7x8x9x5250003121010000x6120000438601000x7155000237900100x825000085121100010x9100000234100001F(X0)0-49-33-76-10900000
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее: следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
БазисBx1x2x3x4x5x6x7x8x9minx52500031210100002500x612000043860100020000x7155000237900100172222/9x825000085121100010227273/11x9100000234100001100000F(X1)0-49-33-76-109000000
Получаем новую симплекс-таблицу:
БазисBx1x2x3x4x5x6x7x8x9x425003/101/101/511/100000x610500021/522/564/50-3/51000x7132500-7/1021/1051/50-9/100100x822250047/1039/1094/50-11/100010x99750017/1029/1034/50-1/100001F(X1)272500-163/10-221/10-541/50109/100000
Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее: следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (1/5) и находится на пересечении ведущего столбца и ведущей строки.
БазисBx1x2x3x4x5x6x7x8x9minx425003/101/101/511/10000012500x610500021/522/564/50-3/51000154413/17x7132500-7/1021/1051/50-9/1001002548010/13x822250047/1039/1094/50-11/100010227044/49x99750017/1029/1034/50-1/1000012565717/19F(X2)272500-163/10-221/10-541/50109/1000000
Получаем новую симплекс-таблицу:
БазисBx1x2x3x4x5x6x7x8x9x31250011/21/2151/20000x620000-8-10-34-41000x767500-81/2-1/20-26-31/20100x8100000-10-10-49-60010x950000-410-19-20001F(X2)9500006550271380000
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
БазисBx1x2x3x4x5x6x7x8x9x31250011/21/2151/20000x620000-8-10-34-41000x767500-81/2-1/20-26-31/20100x8100000-10-10-49-60010x950000-410-19-20001F(X3)9500006550271380000
Оптимальный план можно записать так:= 12500= 20000= 67500= 100000= 50000(X) = 7612500 = 950000
Xоптим = ( 0; 0; 12500; 0; 0; 120000; 155000; 250000; 100000).
Для получения максимальной прибыли 950 000 руб. необхадимо выпустить тканей рисунков вида Р3 в объеме 12500.
Ткани рисунков вида Р1 , Р2 , Р4 являются убыточными; их производство нерентабельно.
Проверка при помощи программного продукта (Рисунок 5):
Рисунок 5 - проверка реализованная программным методом.
2.1Составление и решение двойственной задачи
Обозначим :
y1 - теневая цена красителя А1;
y2 - теневая цена красителя А2;
y3 - теневая цена красителя А3;
y4 - теневая цена красителя А4;
y5 - теневая цена красителя А5;
y1 + 120000y2 + 155000y3 + 250000y4 + 100000y5 > min
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.= (A3, A6, A7, A8, A9, ) =
2000001000001000001000001
Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
А-1 =
1/2000001000001000001000001
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A-1 =
(76, 0, 0, 0, 0) x
1/2000001000001000001000001
= (38;0;0;0;0)
Оптимальный план двойственной задачи равен:= 38= 0= 0= 0= 0
Fmax = 25000*38+120000*0+155000*0+250000*0+100000*0 = 950000.
Таким образом дефицитным красителем является краситель А1 , а к не дефицитным красителям относятся красители А2 , А3 , А4 , А5 . Недефицитные красители недоиспользуются на :
краситель А2 на 20 000 грамм;
краситель А3 на 67 500 грамм;
краситель А4 на 100 000 грамм;
краситель А5 на 50 000 грамм;
При увеличении запасов красителя краситель А1 на 1 ед. (25001 грамм) можно получить увеличение прибыли на 38 руб., что составит 950038 руб. При этом план выпуска ткани рисунка Р3 надо увеличить на 0,5 м, т.е выпустить ткани 12500,5 . В этом случае недефицитные красители будут недоиспользоваться :
1.Краситель Р2 - 4 ; его недоиспользование составит 20 004 грамм;
2.Краситель Р3 - 3,5; его недоиспользование составит 67 503,5 грамм;
.Краситель Р4 - 6 ; его недоиспользование составит 100 006 грамм;
.Краситель Р5 - 2 ; его недоиспользование составит 50 002 грамм;
Для вычисления допустимых пределов изменения запасов красителей составим матрицу и вектор-столбец :
Найдём матрицу , обратную исходной матрице .