Предприятие может производить четыре вида изделий A, B , С и D , располагая для их изготовления ограниченными ресурсами – чугуна и стали соответственно в количествах 414 и 514 кг и оборудования в количестве 394 станко-часов. Данные, представленные в таблице, характеризуют затраты каждого из перечисленных трех видов ресурсов на изготовление одного изделия вида A, B , С и D . Необходимо определить, сколько изделий каждого вида должно производить предприятие, чтобы достичь наибольшей прибыли
Ресурсы Затраты ресурсов на единицу изделия
A B С D
Чугун, кг 4,4 3,4 2,4 5,4
Сталь, кг 6,4 6,4 5,4 2,4
Оборудование, станко-час 5,4 2,4 8,4 3,4
Прибыль, ден. Ед. 9,8 6,8 8,8 13,8
Требуется:
1. Построить экономико-математическую модель задачи.
2.С помощью симплекс-метода определить план выпуска изделий, при котором прибыль от их реализации будет максимальной.
3.Сформулировать экономически и записать двойственную задачу. Найти оптимальные двойственные оценки. Пояснить экономический смысл полученных объективно обусловленных двойственных оценок.
4. Определить ценность ресурсов. Увеличение объемов какого вида ресурсов наиболее выгодно?
5. Найти интервалы устойчивости двойственных оценок по отношению к измерению запаса ресурсов каждого вида.
6. Определить изменение максимальной прибыли от реализации продукции при увеличении запаса ресурса «чугун» на 30 кг, запаса ресурса «оборудование» на 50 станко-часов и уменьшении запаса ресурса «сталь» на 25 кг. Определить раздельное и суммарное влияние этих изменений.
7. Определить нормы относительной заменяемости ресурсов.
8. Найти допустимые интервалы изменения коэффициентов целевой функции.
9. Оценить целесообразность введения в план пятого вида изделия V, на производство которого расходуются ресурсы «чугун», «сталь», «оборудование» в количествах 5 кг; 6 кг; 10 станко-часов соответственно, а прибыль от реализации одной единицы продукции V составляет 7 ден. Ед.
Решение
Составим математическую модель задачи
х1 – количество выпускаемой продукции А
х2 – количество выпускаемой продукции В
х3 - – количество выпускаемой продукции С
х4 -– количество выпускаемой продукции D
Так как запасы ресурсов ограничены, то составим неравенства системы ограничений
4,4x1+ 3,4x2+2,4 x3+5,4x4≤4146,4x1+6,4x2+ 5,4x3+2,4x4 ≤5145,4x1+ 2,4x2+8,4x3+ 3,4x4 ≤394х1, х2, х3, х4≥0
По своему экономическому содержанию переменные х1, х2, х3, х4 могут принимать только неотрицательные значения.
F = 9,8x1 + 6,8x2 + 8,8x3 + 13,8x4 → max - целевая функция (прибыль от производства выпущенной продукции)
Получили задачу линейного программирования – при имеющихся запасах ресурсов и прибыли за единицу продукции, составить такой план, чтобы получить наибольший доход.
Введем дополнительные переменные х5, х6, х7 – количество неиспользованных ресурсов. Запишем эту задачу в канонической форме
4,4x1+ 3,4x2+2,4 x3+5,4x4+x5=4146,4x1+6,4x2+ 5,4x3+2,4x4+x6=5145,4x1+ 2,4x2+8,4x3+ 3,4x4+x7=394xi≥0 i=1,2,3,4,5,6,7
F = 9,8x1 + 6,8x2 + 8,8x3 + 13,8x4
Решим задачу симплекс-методом. Составим первую симплексную таблицу.
В качестве базисных переменных выберем переменные х5, х6, х7, так как они входят только в одно уравнение и с единичным коэффициентом. Составим первый опорный план.
Базис хi
В х1 х2 х3 х4
х5 х6 х7
х5 414 4,4 3,4 2,4 5,4 1 0 0
х6 514 6,4 6,4 5,4 2,4 0 1 0
х7 394 5,4 2,4 8,4 3,4 0 0 1
F 0 -9,8 -6,8 -8,8 -13,8 0 0 0
Данный план не оптимален, т. к. в индексной строке имеются отрицательные элементы.
Итерация 1
В качестве ведущего столбца возьмем столбец с наибольшим по модулю значением. Это четвертый столбец (выделим цветом) max-9,8, -6,8, -8,8, -13,8=13,8
Для определения ведущей строки разделим столбец В на элементы ведущего столбца и найдем наименьшее значение (делим на положительные числа) min{4145,4, 5142,4,3943,4 }=76,6
Первая строка будет ведущей (выделим цветом )
На пересечении ведущего столбца и ведущей строки стоит разрешающий элемент 5,4
Пересчитаем симплекс-таблицу: в новом плане вместо переменной х5, в новый план войдет переменная х4, ведущую строку разделим на 5,4, на месте разрешающего элемента запишем 1, в остальных клетках столбца х4 запишем нули, остальные элементы таблицы пересчитаем по правилу прямоугольника
В индексной строке:
-9,8--13,8*4,45,4=1,44 -6,8--13,8*3,45,4=1,89
-8,8--13,8*2,45,4=-2,67 0--13,8*15,4=2,56
0--13,8*05,4=0 0--13,8*05,4=0
В столбце В:
514-2,4*4145,4=330 394-3,4*4145,4=133,33
0-(-13,8)*4145,4=1058
Базис хi
В х1 х2 х3 х4 х5 х6 х7
Х4 76,67 0,81 0,63 0,44 1 0,19 0 0
х6 330 4,44 4,89 4,33 0 -0,44 1 0
х7 133,33 2,63 0,26 6,89 0 -0,63 0 1
F 1058 1,44 1,89 -2,67 0 2,56 0 0
Данный план не оптимален, т. к. в индексной строке имеются отрицательные элементы.
Итерация 2
В качестве нового ведущего столбца возьмем столбец с наибольшим по модулю отрицательным значением. Это столбец х3 (выделим цветом)
Для определения ведущей строки разделим столбец В на элементы ведущего столбца и найдем наименьшее значение (делим на положительные числа) min{76,670,44, 3304,33, 133,336,89}=19,35
третья строка будет ведущей (выделим цветом )
На пересечении ведущего столбца и ведущей строки стоит разрешающий элемент 6,89
Пересчитаем симплекс-таблицу: в новом плане вместо переменной х7, в новый план войдет переменная х3, ведущую строку разделим на 6,89, на месте разрешающего элемента запишем 1, в остальных клетках столбца х3 запишем нули, остальные элементы таблицы пересчитаем по правилу прямоугольника
Базис хi
В х1 х2 х3 х4 х5 х6 х7
Х4 68,06 0,65 0,61 0 1 0,23 0 -0,065
х6 246,13 2,79 4,73 0 0 -0,048 1 -0,63
Х3 19,35 0,38 0,038 1 0 -0,091 0 0,15
F 1109,61 2,46 1,99 0 0 2,31 0 0,39
В индексной строке нет отрицательных элементов, поэтому данный план будет оптимальным, нет необходимости пересчитывать все элементы таблицы.
Получаем:
х1=0, х2=0, х3=19,35, х4=68,06 - план выпуска
х5=0, х6=246,13, х7=0, – остатки ресурсов
F = 9,8*0+ 6,8*0 + 8,8*19,35 + 13,8*68,06=1109,51 – максимальная прибыль
х5=0, х6=246,13, х7=0, – остатки неиспользованного сырья
Так как х1=0, х2=0, то производство продукции А и В невыгодно.
В условиях этой задачи требуется дать оценку каждому ресурсу
. Оценка ресурса должна показывать, насколько увеличится прибыль, если количество ресурса увеличить на единицу. Проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок у(у1, y2, y3) минимизирующий общую оценку всех ресурсов
Установим соответствие между переменными
x1,x2,x3,x4 - основные переменные x5,x6,x7 дополнительные y5,y6,y7дополнительные переменные y1,y2,y3,y4-основные
Математическая модель двойственной задачи имеет вид:
4,4y1+ 6,4y2+5,4 y3≥9,83,4y1+ 6,4y2+2,4 y3≥6,82,4y1+ 5,4y2+8,4 y3≥8,85,4y1+ 2,4y2+3,4 y3≥13,8yi≥0 i=1,2,3
W= 414y1 + 514y2 + 394y3 → min
Используя последнюю итерацию прямой задачи, найдем, оптимальный план двойственной задачи.
y1=2,31, y2=0, y3=0,39
Z(Y) = 414*2,31+514*0+394*0,39 = 1109,51
4) Определение дефицитных и недефицитных (избыточных) ресурсов.
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
4,4*0 + 3,4*0 + 2,4*19,35 + 5,4*68,06 = 414 = 414
6,4*0 + 6,4*0 + 5,4*19,35 + 2,4*68,06 = 267,87 < 514
5,4*0 + 2,4*0 + 8,4*19,35 + 3,4*68,06 = 394 = 394
1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-й ресурс (чугун) полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y1≠ 0).
2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида (сталь) израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y2= 0.
Неиспользованный экономический резерв ресурса 2 составляет
246,13= (514 - 267,87).
3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-й ресурс (использование оборудования) полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y3≠ 0).
При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:
4,4*2.31 + 6,4*0 + 5,4*0.39 = 12,27 > 9,8
3,4*2,31 + 6,4*0 + 2,4*0,39 = 8,79 > 6,8
2,4*2,32 + 5,4*0 + 8,4*0.39 = 8,8 = 8,8
5,4*2,31 + 2,4*0 + 3,4*0.39 = 13,8 = 13,8
1-ое ограничение выполняется как строгое неравенство, т.е. продукцию А производить экономически не выгодно. Также, в оптимальном плане прямой задачи x1= 0
Задать вопрос
на новый заказ в Автор24.
