Предприятие выпускает два вида продукции A₁ и A₂, используя при этом три вида сырья B₁, B₂ и B₃. Известны запасы сырья равные b₁, b₂ и b₃ соответственно. Расход сырья вида Bi на производство единицы продукции Aj равен ai,j. Доход от реализации единицы продукции Aj составляет cj условных единиц. Требуется составить такой план производства продукции, при котором доход будет максимальным.
Составить стандартную модель данной задачи и решить ее графическим методом. Составить двойственную задачу и решить ее с помощью теорем двойственности.
Ответы
Ответ:
Обозначим через х1 и х2 количество изделий первого и второго вида в плане предприятия. Поскольку производство продукции ограничено только сырьем каждого типа Bi, то получим условия:
11 1 12 2 1
21 1 22 2 2
31 1 32 2 3
a x a x b a x a x b a x a x b + ≤⎧ ⎪ + ≤ ⎨ ⎪ + ≤ ⎩
или
12
12
12
1 3 27 3 2 30 2 3 30 xx xx xx ⋅ + ⋅ ≤⎧ ⎪ ⋅ + ⋅ ≤ ⎨ ⎪ ⋅ + ⋅ ≤ ⎩ Переменные х1 и х2 не могут быть отрицательными по смыслу задачи 0, 1, 2.j xj ≥=
Прибыль от реализации продукции () 1 1 2 2 1 22 2 max, f X c x c x x x =+=+→ где () 12 ,X xx = .
Получили стандартную модель с двумя переменными.
1
Решим задачу линейного программирования геометрически, придерживаясь следующего плана. 1.Строим прямые l1, l2, l3: ll: 12 1 3 27 xx ⋅ + ⋅ = , по двум точкам А1(27; 0) и В1(0; 9); l2: 12 3 2 30 xx ⋅ + ⋅ = , по двум точкам А2(10; 0), В2(0; 15); l3: 12 2 3 30 xx ⋅ + ⋅ = , по двум точкам А3(15, 0), В3(0; 10). 2. Обратимся к неравенствам системы ограничений. Так как неравенства системы выполняются для любой точки из соответствующей полуплоскости, то их достаточно проверить дня какой-либо одной точки. Возьмём точку O(0, 0) и подставим её координаты в неравенства системы. Если неравенство выполняется для точки O(0, 0), то это неравенство определяет полуплоскость, содержащую точку O(0, 0). Если неравенство не выполняется для точки O(0, 0), то это неравенство определяет полуплоскость, не содержащую точку O(0, 0). Отметим те полуплоскости, которые удовлетворяют неравенства системы. 3. Учтем на чертеже неотрицательность переменных х1 и х2, и получим многоугольник решений данной системы неравенств O A2 Xmax C B1 (рис. 1). 4.Строим нормальный вектор { } { } 12 , 2, 2n c c == G .
5.Строим прямую ( l ):
1 1 2 20 c x c x ⋅ −⋅=; 2x1 – 2x2 = 0, перпендикулярную нормальному вектору. 6. Передвигая прямую ( l ) параллельным образом в направлении вектора n G
. Максимальное значение целевая функция принимает в последней общей точке передвигаемой прямой и многоугольника допустимых решений. Координаты этой точки находим как координаты точки пересечения прямых ( l2 ) и ( l3 ), решая систему уравнений:
12
12
12
3 2 30 2 3 30 6; 6 xx xx xx +=⎧ ⎨ += ⎩ == ( )max 6,6 2 6 2 6 24 ff = =⋅+⋅= . 7.Запишем окончательный ответ: Хmax = (6, 6), fmax = f(Xmax) = 24. Наибольшая прибыль будет равна 24 (ден. ед).