Фирма производит три вида продукции

Составим математическую модель данного производства. Введем следующие обозначения: 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