|
Математическая модель задачи имеет вид:
W’ = 9* х1 + 8* х2 + 10* х3 → max
- 0,22* х1 - 0,21*х2 - 0,31*х3 ≥ 0
301 - 0,17* х1 - 0,15*х2 - 0,12*х3 ≥ 0
321 - 0,25*х1 - 0,20*х2 - 0,15* х3 ≥ 0
Для упрощения расчетов ограничения (1.1) заменяем условием неотрицательных переменных: х1 ≥ 0; х2 ≥ 0; х3 ≥ 0.
Перейдем к минимизации целевой функции W’, изменив знаки всех ее коэффициентов на противоположные, и к ограничениям в виде равенств, введя дополнительные переменные:
W = -9* х1 - 8* х2 - 10* х3 → min
y1 = 251 - 0,22* х1 - 0,21*х2 - 0,31*х3;
y2 = 301 - 0,17* х1 - 0,15*х2 - 0,12*х3;
y3 = 321 - 0,25*х1 - 0,20*х2 - 0,15* х3;
где х1, х2, х3, y1, y2, y3 - неотрицательны.
Сведем к задаче линейного программирования:
W = 0 - (9* х1 + 8* х2 + 10* х3) (1.7)
y1 = 251 - (0,22* х1 + 0,21*х2 + 0,31*х3);
y2 = 301 - (0,17* х1 + 0,15*х2 + 0,12*х3) (1.8)
y3 = 321- (0,25*х1 + 0,20*х2 + 0,15* х3);
Составим таблицу, состоящую из коэффициентов целевой функции (1.7) и системы ограничений (1.8).
Таблица 2 |
Базисная переменная |
Свободный член |
Свободные переменные | | | |
х1 |
х2 |
х3 | |
y1 |
251 |
0,22 |
0,21 |
0,31 | |
y2 |
301 |
0,17 |
0,15 |
0,12 | |
y3 |
321 |
0,25 |
0,20 |
0,15 | |
W |
0 |
9 |
8 |
10 |
В качестве разрешающего столбца выбираем х2. В столбце найдем разрешающий элемент путем сравнения соотношений 251/0,21; 301/0,15; 321/0,20.
Наименьшее из соотношений (251/0,21 = 1195) будет определять разрешающий элемент. Им будет элемент 0,21 находящийся на пересечении столбца х2 и строки y1. Этот элемент обводится.
Затем вычисляем обратную величину разрешающего элемента λ = 1/0,21 = 4,76 и записывают её в нижней части той же ячейки, в которой находится разрешающий элемент. Все элементы разрешающей строки умножаем на λ. Затем все элементы разрешающей графы умножают на (-λ), результаты записываются в нижней части соответствующих ячеек.
Подчеркивают в разрешающей строке все верхние числа (251, 0,22, 0,31), а в разрешающей графе - все нижние числа (-0,72, -0.95, -38.10) за исключением λ. Для каждого из элементов, не принадлежащих ни к разрешающей строке, ни к разрешающей графе, записывают в нижней части соответствующей ячейки произведения подчеркнутых чисел, стоящих в той же строке и в той же графе, что и данный элемент.
Перейти на страницу: 1 2 3 |
