Решить задачу оптимизации использования производственных ресурсов симплексным методом с искусственным базисом.
Исходные данные задачи 2 дополнить условиями по производству продукции отдельных видов:
Продукции 1-го вида произвести не менее 50 ед.;
Продукции 3-го вида произвести не менее 100 ед.
Задача должна быть решена на МАХ экономического эффекта.
Решение
Математическая модель задачи имеет вид:.
6x1+ 8x2+4x3+7x4≤18007x1+ 6x2+5x3+8x4≤24008x1+ 12x2+10x3+14x4≤3500x1≥50x2≥100
х1, х2,х3, х4≥0
Fx=12x1+10x2+15x3+8x4→ max
Запишем эту задачу в канонической форме, перейдя от неравенств к равенствам с добавлением дополнительных переменных.
в 1-м равенстве вводим переменную x5;
в 2-м равенстве вводим переменную x6,
в 3-м равенстве вводим переменную x7
в 4-м равенстве вводим переменную x8 со знаком минус
в 5-м равенстве вводим переменную x9 со знаком минус
получим
6x1+ 8x2+4x3+7x4+x5=18007x1+ 6x2+5x3+8x4+x6=24008x1+ 12x2+10x3+14x4+x7=3500x1-x8=50x2-x9=100
Введем искусственные переменные x10 и x11 и решим задачу методом искусственного базиса:
6x1+ 8x2+4x3+7x4+x5=18007x1+ 6x2+5x3+8x4+x6=24008x1+ 12x2+10x3+14x4+x7=3500x1-x8+x10=50x2-x9+x11=100
Целевую функцию запишем так:
Z(X) = 12x1+10x2+15x3 +8x4- Mx10- Mx11→ max
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Из уравнений выразим искусственные переменные:
X10= 50-x1+x8
X11= 100-x3 + x9
и подставим их в целевую функцию:
Z(X) = 12x1+10x2+15x3 +8x4 - M(50-x1+x8) - M(100-x3 + x9) → max
Или Z(X) = (12+M)x1+10x2+(15+M)x3+8x4 – Mx8 - Mx9 – 150М → max
Матрица коэффициентов системы уравнений имеет вид:
х1
х2
х3 х4
х5 х6
х7
х8 х9
х10 х11
6 8 4 7 1 0 0 0 0 0 0
7 6 5 8 0 1 0 0 0 0 0
8 12 10 14 0 0 1 0 0 0 0
1 0 0 0 0 0 0 -1 0 1 0
0 0 1 0 0 0 0 0 -1 0 1
В качестве базисных переменных выберем переменные х5, х6, х7, х10, х11 так как они входят только в одно уравнение и с единичным коэффициентом
. Составим первый опорный план.
Базис хi
В х1
х2
х3 х4
х5 х6
х7
Х8 Х9
Х10 Х11
Х5 1800 6 8 4 7 1 0 0 0 0 0 0
Х6
2400 7 6 5 8 0 1 0 0 0 0 0
Х7
3500 8 12 10 14 0 0 1 0 0 0 0
Х10 50 1 0 0 0 0 0 0 -1 0 1 0
Х11 100 0 0 1 0 0 0 0 0 -1 0 1
F -150М -12-М -10 -15-М -8 0 0 0 М М 0 0
Данный план не оптимален, т. к. в индексной строке имеются отрицательные элементы.
Итерация 1
В качестве ведущего столбца возьмем столбец с наибольшим по модулю значением. Это третий столбец (выделим цветом)
Для определения ведущей строки разделим столбец В на элементы ведущего столбца и найдем наименьшее значение (делим на положительные числа) min{18004,24005,350010,- 1001}=100
пятая строка будет ведущей (выделим цветом )
На пересечении ведущего столбца и ведущей строки стоит разрешающий элемент 1
Базис хi
В х1
х2
х3 х4
х5 х6
х7
Х8 Х9
Х10 Х11
Х5 1800 6 8 4 7 1 0 0 0 0 0 0
Х6
2400 7 6 5 8 0 1 0 0 0 0 0
Х7
3500 8 12 10 14 0 0 1 0 0 0 0
Х10 50 1 0 0 0 0 0 0 -1 0 1 0
Х11 100 0 0 1 0 0 0 0 0 -1 0 1
F -150М -12-М -10 -15-М -8 0 0 0 М М 0 0
Пересчитаем симплекс-таблицу: в новом плане вместо переменной х11, в новый план войдет переменная х3, ведущую строку разделим на 1, на месте разрешающего элемента запишем 1, в остальных клетках столбца х1 запишем нули, остальные элементы таблицы пересчитаем по правилу прямоугольника
Получим новую таблицу
Базис хi
В х1
х2
х3 х4
х5 х6
х7
Х8 Х9
Х10 Х11
Х5 1400 6 8 0 7 1 0 0 0 0 0 -4
Х6
1900 7 6 0 8 0 1 0 0 0 0 -5
Х7
2500 8 12 0 14 0 0 1 0 10 0 -10
Х10 50 1 0 0 0 0 0 0 -1 0 1 0
Х3 100 0 0 1 0 0 0 0 0 -1 0 1
F 1500-50М -12-М -10 0 -8 0 0 0 М -15 0 15+М
Данный план не оптимален, т
Задать вопрос
на новый заказ в Автор24.
