Решение задач оптимизации симплекс-методомРефераты >> Программирование и компьютеры >> Решение задач оптимизации симплекс-методом
Необходимо определить количество продукции, при выпуске которой прибыль является максимальной.
Предположим, что будет изготовлено x1 единиц продукции 1-го типа, х2 – 2-го типа. Тогда для производства такого количества изделий потребуется затратить
4x1 +4х2 сырья вида А.
Так как запас сырья данного вида не может превышать 7, то должно выполняться неравенство
4x1 +4х2 ≤ 120.
Аналогичные рассуждения относительно возможного использования сырья вида B приведут к следующим неравенствам:
3x1 + 12х2 ≤ 252,
При этом так как количество выпускаемой продукции не может быть отрицательной, то
x1>0, x2>0. (1)
Далее, если будет выпущено х1 единиц продукции 1-го типа, х2 единиц продукции 2-го типа, то прибыль от их реализации составит
F= 30x1 + 40х2 .
Таким образом, приходим к следующей математической задаче: дана система
4x1 +4х2 ≤ 120,
3x1 + 12х3 ≤ 252, (2)
трёх линейных неравенств с двумя неизвестными хj (j=1 3) и линейная функция относительно этих же переменных
F= 30x1 + 40х2 ; (3)
требуется среди всех неотрицательных решений системы неравенств (2) найти такое, при котором функция (3) принимает максимальное значение.
Линейная функция (3), максимум которой требуется определить, вместе с системой неравенств (2) и условием неотрицательности переменных (1) образуют математическую модель исходной задачи.
Так как функция (3) линейная, а система (2) содержит только линейные неравенства, то задача (1)-(3) является задачей линейного программирования.
Данные расчётов для всех итераций приведены в таблице:
Базисные неизвестные |
Свободные члены |
x1 |
x2 |
x3 |
x4 |
x3 x4 |
120 252 |
4 3 |
4 12 |
1 0 |
0 1 |
ƒ |
0 |
-30 |
-40 |
0 |
0 |
x1 x3 |
30 162 |
1 0 |
1 9 |
1/4 3/4 |
0 1 |
ƒ |
900 |
0 |
-10 |
7,5 |
0 |
x1 x2 |
18 12 |
0 1 |
1 0 |
-1/12 1/3 |
1/9 -1/9 |
ƒ |
1080 |
0 |
0 |
45/6 |
10/9 |
Таким образом, если предприятие изготовит 12 единиц изделий вида А и 18 единиц изделий В, то оно получит максимальную прибыль, равную: F=30*12 + 40*18 = 1080.