Фирма производит три вида продукции (А, В, С), для выпуска каждого из которых требуется определённое время обработки на всех четырёх устройствах I, II, III, IV.
Вид продукции Время обработки Прибыль, дол.
I II III IV
А 1+m 3 1+k 2 3+m
В 8-n 1+n 3 3 6+n
С 3 3 2 4 4+k
Пусть время работы на устройствах, соответственно, 84-2m, 42-n, 21+k и 42 часа. В соответствии со своими индивидуальными данными (m – число гласных букв в фамилии студента m=2, n – число гласных букв в полном имени студента n=3, k – число гласных букв в отчестве студента k=3) определите, какую продукцию и в каких количествах следует производить. Рынок сбыта для каждого продукта неограничен. Временем, требуемым для переключения устройства в зависимости от вида продукции, можно пренебречь. Рассмотреть задачу максимизации прибыли.
Исходные данные задачи:
Вид продукции Время обработки Прибыль, дол.
I II III IV
А 3 3 4 2 5
В 5 4 3 3 9
С 3 3 2 4 7
Время работы, ч
80 39 24 42 -
Решение
Составим математическую модель данного производства. Введем следующие обозначения: x1 – выпуск изделий А; x2 – выпуск изделий В; х3 – выпуск изделий С.
Запишем выражение для целевой функции (общая прибыль от проданных изделий, которая должна быть максимальной):
Q=5x1+9x2+7x3→max.
Исходя из резервов времени работы на устройствах и неотрицательности количества выпускаемых изделий, составляем условия ограничения:
Для решения задачи симплекс-методом переведем ЗЛП в основную форму, превратив неравенства в равенства, для чего введем новые неотрицательные переменные х4, х5, х6, х7:
3х1 + 5х2 +3х3 + х4 = 80
3х1 + 4х2 + 3х3 +х5 = 39
4х1 + 3х2 +2х3 + х6 = 24
2х1 + 3х2 +4х3 + х7 = 42
Введенные новые переменные имеют следующий экономический смысл: х 4 – неизрасходованный ресурс времени на устройстве I; х5 - неизрасходованный ресурс времени на устройстве II; х6 - неизрасходованный ресурс времени на устройстве III; х7 - неизрасходованный ресурс времени на устройстве IV.
Векторы для новых переменных Р4 = , Р5 = , Р6 = , Р7 = являются единичными, т.е. введенные переменные {х4, х5, х6, х7} представляют базис, а остальные переменные {х1, х2, х3} являются свободными, следовательно, опорный план имеет вид:
Х=().
Значение целевой функции равно Qo=5·0+9·0+7·0=0 (долл.): ничего не произвели – ничего не получили.
Таблица. Исходная симплекс-таблица данной задачи
i Базис Сб
βi 5 9 7 0 0 0 0
Р1
Р2
Р3 Р4
Р5 Р6
Р7
1 Р4
0 80 3 5 3 1 0 0 0
2 Р5 0 39 3 4 3 0 1 0 0
3 Р6
0 24 4 3 2 0 0 1 0
4 Р7
0 42 2 3 4 0 0 0 1
5
0 -5 -9 -7 0 0 0 0
Рассчитаем исходные значения целевой функции Qo=СбВ=80·0+39·0 + 24·0+42·0 =0 и вспомогательных величин Δj=CбPj–Cj:
Δ1 = P1Cб–C1=3·0+3·0+4·0+2·0–5=-5,
Δ2 = P2Cб–C2=5·0+4·0+3·0+3·0–9=-9,
Δ3 = P3Cб–C3=3·0+3·0+2·0+4·0–7=-7.
Отрицательные числа Δj свидетельствуют о возможности увеличения общей стоимости продукции и показывают насколько увеличится сумма при введении в план единицы продукции.
Максимальное значение модуля вспомогательной величины Δj равно 9, следовательно, номер разрешающего столбца к=2.
Для данного столбца все > 0. Находим минимальное значение : min= min{16, 9.75, 8, 14} = 8. Следовательно, номер разрешающей строки r = 3. Таким образом, разрешающий элемент = 3(выделен цветом). Вводим в базис вектор Р2, выводим из базиса вектор Р6. Все элементы данной новой строки вычисляются делением на разрешающий элемент
Остальные элементы вычисляются по правилу треугольника, согласно которому находятся три числа:
число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы (число А);
число, стоящее в исходной симплекс-таблице на пересечении строки, в которой находится искомый элемент новой симплекс-таблицы и столбца, соответствующего вектору, вводимому в базис (число С);
число, стоящее в новой симплекс-таблице на пересечении столбца, в котором стоит искомый элемент, и строки вновь вводимого в базис вектора (число В).
Искомый элемент новой симплекс-таблицы вычисляется по формулам Жордана-Гаусса: А-В∙С.
Таким образом, новая симплекс-таблица представлена в следующей таблице.
i Базис Сб
βi 5 9 7 0 0 0 0
Р1
Р2
Р3 Р4
Р5 Р6
Р7
1 Р4
0 40 -11/3 0 -1/3 1 0 -5/3 0
2 Р5 0 7 -7/3 0 1/3 0 1 -4/3 0
3 Р2
9 8 4/3 1 2/3 0 0 1/3 0
4 Р7
0 18 -2 0 2 0 0 -1 1
5
72 7 0 -1 0 0 3 0
Так как среди чисел существует отрицательное значение то, следовательно, план не является оптимальным. Разрешимость задачи остается в силе, так как есть положительные коэффициенты в столбце Р3, кроме .
Разрешающий столбец , т.к. . Этот столбец нужно ввести в базис. Для определения разрешающей строки найдём минимум min=min=min=9. Следовательно, разрешающая строка и разрешающий элемент равен .
Четвертая строка новой симплекс таблицы получается путём деления исходной строки на 2.
i Базис Сб
βi 5 9 7 0 0 0 0
Р1
Р2
Р3 Р4
Р5 Р6
Р7
1 Р4
0 43 -4 0 0 1 0 -11/6 1/6
2 Р5 0 4 -2 0 0 0 1 -7/6 -1/6
3 Р2
9 2 2 1 0 0 0 2/3 -1/3
4 Р3 7 9 -1 0 1 0 0 -1/2 1/2
5
81 6 0 0 0 0 5/2 1/2
Векторы Р2, Р3 , Р4 и Р5 образуют базис, соответствующие числа равны нулю
. Остальные элементы симплекс-таблицы пересчитываются по правилу треугольника:
=40-9*(-1/3)=43 =A-BC=7-9*(1/3)=4=8-9*2/3=2
=-*=72-9(-1)=81
Так как все , то полученный план является оптимальным: .
Экономическая интерпретация полученного решения: для получения максимальной прибыли нужно произвести 2 изделия В; 9 изделий С; при этом ресурсы времени на устройствах I и II не будут израсходованы полностью, останется 43 и 4 часа, а на устройствах III и IV полностью. Выпуск продукции обеспечит максимальную прибыль в 81 долл.
Задание по теме «Транспортная задача»
На четыре базы A1, A2, A3, A4 поступил однородный груз в количествах, соответственно равных 30-n, 25+m, 15+n и 30 единиц. Этот груз требуется перевезти в три пункта назначения B1, B2, B3 соответственно в количествах 40-n, 20+n и 40+m единиц. Тарифы перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения указаны в транспортной таблице.
Пункты отправления Пункты назначения Запасы
B1 B2 B3
A1 c11 c12 c13 30-n
A2 c21 c22 c23 25+m
A3 c31 c32 c33 15+n
A4 c41 c42 c43 30
Потребности 40-n 20+n 40+m 100+m
Значения коэффициентов (тарифов) транспортной таблицы:
№ варианта 14
Значения
c11 5
c12 4
c13 5
c21 2
c22 3
c23 4
c31 3
c32 k
c33 5
c41 5
c42 2
c43 4
Опорный план перевозок найти методом северо-западного угла, методом минимального элемента и методом аппроксимации Фогеля, оптимальный план перевозок – методом потенциалов, используя метод минимального элемента, и методом дифференциальных рент. Вычислить оптимальное значение транспортных издержек. (n – количество букв в Фамилии n =6, m – количество букв в полном Имени m =7, k – число согласных букв в Отчестве k =3).
Исходные данные:
Пункты отправления Пункты назначения Запасы
B1 B2 B3
A1 5 4 5 24
A2 2 3 4 32
A3 3 3 5 21
A4 5 2 4 30
Потребности 34 26 47 107
Данная транспортная задача является закрытой, так как сумма запасов 24+32+21+30=107 равна сумме потребностей 34+26+47=107. Опорный план должен содержать 4+3-1=6 заполненных клеток.
Начинаем заполнение таблицы с клетки А1B1. После заполнение этой клетки переходим к заполнению клетки А2B1, которой требуется еще 10, берем у второго производителя, при этом остается 22. Так как второму потребителю нужно 26, недостающие 4 берем у третьего производителя, после чего у него останется 17, недостающие 30 берем у производителя А4. В результате все запасы исчерпаны, и все потребности удовлетворены.
Предприятия
Сырьё B1 B2 B3 Запасы
А1
6604010541024
0024
5
3035308636000 4
5 25717510541024
0024
А2
2
6159512763410
0010
6121409144000 3
14922512890522
0022
44196024701500 4 2571759906032
0032
А3 3 689610321310001200151644654
004
3 384810448310005715015240017
0017
5 18478516446521
0021
А4
5 2 8001018034030
0030
4 220345-6096030
0030
Потребности 177165219710340
00340
11811021717026
0026
7620021971047
0047
107
Таким образом, опорный план по методу северо-западного угла задается следующей матрицей Х=, а значение целевой функции равно Q=5*24+2*10+3*22+3*4+5*17+4*30=423 ден. ед.
2. Метод минимального элемента
Предприятия
Сырьё B1 B2 B3 Запасы
А1
5
4
4464054286250074931342901004508514986024
0024
5 25717510541024
0024
А2
2
6159512763432
0032
6140459334500 3
4 2571759906032
0032
А3 5854703422650051879542799000965201047752
002
3 3 18351510096519
0019
5 18478516446521
0021
А4
5 11049018669026
0026
2 711202444754
004
4 220345-6096030
0030
Потребности 177165219710340
00340
11811021717026
0026
7620021971047
0047
107
На первом шаге минимальным тарифом будет c21=c42=2
Задать вопрос
на новый заказ в Автор24.
