Сырье Продукция Запас сырья A B C I 4 12 1 64 II 6 8 1 64 III 2 4 1 24 Прибыль 7 3 1 \ (Решение → 15079)

Сырье Продукция Запас сырья A B C I 4 12 1 64 II 6 8 1 64 III 2 4 1 24 Прибыль 7 3 1 \

Решение.

1. Обозначив через 1 2 3 x , x , x неотрицательные объемы выпуска продукции вида A, B, C соответственно. Видим, что прибыль, полученная при реализации x1 единиц продукции A, x2 единиц продукции B и x3 единиц продукции C, составит 7x1+3x2+x3. Так как задача состоит в максимизации целевой функции, то  , ,  7 3 max. f x1 x2 x3  x1  x2  x3  Ограниченность ресурсов сырья I и II приводит к неравенствам 38 4 12 64, 6 8 64. x1  x2  x3  x1  x2  x3  Ограниченность ресурсов сырья III вместе с требованием, чтобы сырье III было полностью израсходовано, приводит к уравнению 2 4 24. x1  x2  x3  Итак, математическая модель задачи имеет следующий вид:  , ,  7 3 max, f x1 x2 x3  x1  x2  x3                     0, 0, 0. 2 4 24, 6 8 64, 4 12 64, 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x x 2. Приведем задачу к стандартной форме, т.е. к виду, где все ограничения имеют форму неравенств. Выразив из третьего ограниченияуравнения одну из переменных, например x3, 24 2 4 , 3 1 2 x   x  x поставим полученное выражение в целевую функцию:  , ,  7 3 24 2 4 5 24 max, f x1 x2 x3  x1  x2   x1  x2  x1  x2   в ограничения-неравенства:   6 8 24 2 4  64 4 4 40 10. 4 12 24 2 4 64 2 8 40 4 20, 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2                       x x x x x x x x x x x x x x x x Кроме того, учтем тот факт, что x30, откуда получаем еще одно ограничение неравенство 24  2x1  4x2  0  2x1  4x2  24  x1  2x2 12 Итак, получена стандартная форма задачи:  , ,  5 24 max, f x1 x2 x3  x1  x2                  0, 0. 2 12, 10, 4 20, 1 2 1 2 1 2 1 2 x x x x x x x x 39 3. Решим полученную задачу графическим методом. Сначала определим многоугольник решений. Для этого в системе координат x10x2 на плоскости изобразим граничные прямые.       3 2 1 1 2 1 2 1 2 1 2 0, 0. 2 12, 10, 4 20, L L L x x x x x x x x                Каждая из построенных прямых делит плоскость на две полуплоскости. Чтобы определить искомую полуплоскость, нужно взять какую-либо точку, принадлежащую одной из полуплоскостей и проверить, удовлетворяют ли ее координаты данному неравенству или нет. Прямые ограничения х1,2 ≥ 0 означают, что область решений будет лежать в первой четверти декартовой системы координат. Первое ограничение х1 + 4х2  20. Решением этого неравенства является полуплоскость, лежащая ниже прямой х1 +4х2 = 20 ( L1 ), проходящей через точки (20;0) и (0;5). Второе ограничение х1 + х2  10. Решением этого неравенства является полуплоскость, лежащая ниже прямой х1 + х2 = 10 ( L2 ), проходящей через точки (10;0) и (0;10). Третье ограничение х1 +2х2  12. Решением этого неравенства является полуплоскость, лежащая ниже прямой х1 +2х2 = 12 ( L3 ), проходящей через точки (12;0) и (0;6). Получили область допустимых решений многоугольник ОABCD.

Рисунок 1. Решение задачи графическим методом Построим основную прямую F = 24, то есть 5x1  x2  0 , проходящую через начало координат O (0,0) перпендикулярно вектору C  5;1. Перемещая прямую F  24 в направлении вектора C  5;1 , находим максимальную точку D (далее линия уровня выходит из многоугольника решений), в которой пересекаются прямые L2 и ось Оx: D(10;0). Получим: х1 = 10, х2 = 0. Итак, Dmax=(10;0), Fmax  510  0  24  74.

4. Приведем задачу к канонической форме. Для этого с помощью дополнительных неотрицательных переменных перейдем к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком «плюс», так как все неравенства имеют вид «≤». В целевую функцию дополнительные переменные входят с коэффициентом 0. Получим каноническую форму ЗЛП:  , ,  5 0 0 0 24 max, f x1 x2 x3  x1  x2   x3   x4   x5                     0, 1,5. 2 12, 10, 4 20, 1 2 5 1 2 4 1 2 3 x i x x x x x x x x x i 5. Решим полученную задачу симплекс-методом. Составим первую симплексную таблицу: Базис Свободный член Переменные Оценочные x1 x2 x3 x4 x5 отношения x3 20 1 4 1 0 0 20/1=20 x4 10 1 1 0 1 0 10/1=10 x5 12 1 2 0 0 1 12/1=12 -F 24 -5 1 0 0 0  Исходный опорный план Х0=(0,0,20,10,12) не является оптимальным, т.к. в последней строке есть отрицательные коэффициенты. В качестве разрешающего столбца выберем первый. Обозначен (). Для выбора разрешающей строки найдем min{20; 10; 12}= 10. Обозначен (). Вторая строка – разрешающая. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент. Обозначен . Переменная x1 переходит в базисную, x4 – в свободную. Составим следующую симплексную таблицу. Для этого из первой строки вычтем 42 второю. Из третьей строки вычтем вторую. К последней строке прибавим вторую, умноженную на 5