Для производства трех видов продукции A, B, C используется три вида сырья I, II, III. Нормы затрат каждого из видов сырья на единицу продукции каждого вида, а также прибыль с единицы продукции приведены в таблице Таблица 2 Данные по продукции Сырье Продукция Запас сырья (Решение → 11295)

Заказ №38664

Для производства трех видов продукции A, B, C используется три вида сырья I, II, III. Нормы затрат каждого из видов сырья на единицу продукции каждого вида, а также прибыль с единицы продукции приведены в таблице. Таблица 2 Данные по продукции Сырье Продукция Запас сырья А В С I 4 12 1 64 II 6 8 1 64 III 2 4 1 24 Прибыль 3 7 1 Определить план выпуска продукции для получения максимальной прибыли при условии, что сырье III должно быть полностью израсходовано. 1. Построить математическую модель задачи. 2. Привести задачу к стандартной форме. 3. Решить полученную задачу графическим методом. 4. Привести задачу к канонической форме. 5. Решить полученную задачу симплекс-методом. 6. Провести анализ модели на чувствительность. 7. Проанализировать результаты решения.

Решение: 

1. Построим математическую модель задачи Вводим переменные. Пусть 1 2 3 х , x , x - объем производства продукции видов А, В и С соответственно. Составляем функцию цели. Необходимо максимизировать прибыль. 1 2 3 1 max f (x) c x 3х 7х x n j   j j     109 Экономический смысл: 7 1 3 2 3 х  х  x - общая прибыль от производства изделий всех трех видов. Составляем ограничения. Функциональные ограничения (по сырью):               2 4 24 6 8 64 4 12 64 1 2 3 1 2 3 1 2 3 х х x x х x x x x Поскольку сырье III должно быть полностью израсходовано, то в 3-м ограничении знак – строгое равно. Прямое ограничение. Т.к. количество изделий не может быть отрицательным числом, то x1 , x2 , x3  0 . Таким образом, имеем задачу линейного программирования: Найти вектор значений ( , , ) 1 2 3 x  x x x , при котором функция цели 3 1 7 2 3 f (x)  x  x  x достигает максимального значения, при ограничениях:                  , , 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 2. Приведем задачу к стандартной форме При стандартной форме модели необходимо, чтобы во всех функциональных ограничениях знак был  .                 , , 0 2 4 24 6 8 64 4 12 64 1 2 3 1 2 1 2 3 1 2 3 x x x х х x х x x x x 3. Решим задачу графическим методом Графический метод применяет для решения ЗЛП с двумя переменными. Выразим переменную 3 x из 3-го ограничения через переменные 1 2 x , x : 3 24 2 1 4 2 x   x  x . Преобразуем систему ограничений: 110                     , 0 2 4 24 6 8 24 2 4 64 4 12 24 2 4 64 1 2 1 2 1 2 1 2 1 2 1 2 x x х х x х x x x x x x или               , 0 2 4 24 4 4 40 2 8 40 1 2 1 2 1 2 1 2 x x х х x х x x Функция цели: max f (x)  3х1  7х2  x3  3x1  7x2  24  2x1  4x2  x1  3x2  24 Таким образом, имеем задачу линейного программирования с двумя переменными: Найти вектор значений ( , ) 1 2 x  x x , при котором функция цели f (x)  x1  3x2  24 достигает максимального значения, при ограничениях:               , 0 2 4 24 4 4 40 2 8 40 1 2 1 2 1 2 1 2 x x х х x х x x а) Построим область допустимых решений Решением каждого ограничения системы является полуплоскость с граничащей ей прямой. 2 8 40 х1  х2  (1) Построим прямую 2 8 40 х1  х2  . Она проходит через точки (0;5) и (20;0). Для того чтобы определить, какая плоскость удовлетворяет неравенству, необходимо выбрать любую точку не принадлежащую прямой. Выберем точку начала координат (0;0), подставим в неравенство 2 8 40 х1  х2  и получим 0 < 40. Данное утверждение является верным, следовательно, неравенству соответствует нижняя полуплоскость, включающая точку (0;0). 4х1  4х2  40 (2) Построим прямую 4х1  4х2  40 . Она проходит через точки (0;10) и (10;0). Выберем точку начала координат (0;0), подставим в неравенство 4х1  4х2  40 и получим 0 < 40. Данное утверждение является верным, следовательно, неравенству соответствует нижняя полуплоскость, включающая точку (0;0). 2 4 24 х1  х2  (3) Построим прямую 2 4 24 х1  х2  . Она проходит через точки (0;6) и (12;0). Выберем точку начала координат (0;0), подставим в неравенство 2 4 24 х1  х2  и получим 0 < 24. Данное утверждение является верным, следовательно, неравенству соответствует нижняя полуплоскость, включающая точку (0;0). 111 0 x1  0 x1  - решение – прямая, совпадающая с осью ОХ2 0 x1  - решение – правая полуплоскость. 0 x2  0 x2  - решение – прямая, совпадающая с осью ОХ1 0 x2  - решение – верхняя полуплоскость. Т.е. ограничения х1  0 и х2  0 показывают, что решение системы находится в I четверти системы координат. Пересечение этих полуплоскостей, каждая из которых определяется соответствующим неравенством системы и удовлетворяет условиям, определяет выпуклый многоугольник. Данный многоугольник – область допустимых значений. Любая точка этой области является допустимым решением задачи. Рисунок 1 - Решение задачи графическим методом б) Найдем оптимальное решение Оптимальное решение может быть только в угловых точках многоугольника. 112 Чтобы найти оптимальное решение можно найти координаты всех угловых точек многоугольника, вычислить значение целевой функции во всех угловых точках. Наибольшее из этих значений и будет максимальным значением целевой функции, а координаты соответствующей угловой точки – оптимальным решением. Существует другой способ, который позволяет графически сразу найти угловую точку, соответствующую оптимальному решению. Для этого построим линию уровня. Приравняем целевую функцию без константы постоянной величине а: f (x)  х1  3х2  а Это уравнение является множеством точек, в котором целевая функция принимает значение, равное а. Меняя значение а, получим семейство параллельных прямых, каждая из которых называется линией уровня Для определения направления движения к оптимуму построим вектор-градиент С  , координаты которого являются частными производными функции f(x), т.е. С  =(1;3). Чтобы построить этот вектор, нужно начало координат соединить с точкой (1; 3). Поскольку задача стоит на максимизацию, перемещаем линию уровня по направлению вектораградиента С  . Максимума ( , ) 1 2 f x x достигает в угловой точке А. Находим координаты т. А:      4 4 2 1 x x Находим значение функции цели: max f (x)  x1  3x2  24  4 + 3×4 + 24 = 40 Ответ: max f (x)  40 при х1 = 4, х2 = 4. Найдем значение объема выпуска продукции 3-гор вида: 3 24 2 1 4 2 x   x  x = 24 – 2×4 – 4×4 = 0 Экономический смысл: Максимальная прибыль от реализации изделий всех видов составит 40 ден.ед., если производить по 4 единицы продукции видов А и В, а изделия вида С не производить совсем. При таком объеме производства все 24 единицы сырья вида III будут израсходованы. 4. Приведем задачу к канонической форме Канонический вид записи модели, т.е. когда система функциональных ограничений состоит только из уравнений с неотрицательной правой частью. В левые части неравенств вводим неотрицательные добавочные переменные со знаком «+» (т.к. знак неравенства ≤ ): 113                  , , , , 0 2 4 24 4 4 40 2 8 40 1 2 3 4 5 1 2 3 1 2 5 1 2 4 x x x x x х х х x х х x x х 5. Решим полученную задачу симплекс-методом Находим первое допустимое базисное решение 1-ое решение проще найти, если среди n переменных есть m таких, коэффициенты при которых образуют единичную матрицу порядка m. Тогда эти переменные можно взять за основные. Остальные (n-m) будут не основные. Координаты переменных 3 4 5 x , x , х образуют единичную матрицу 3-го порядка. Их берем за основные. Основные переменные - 3 4 5 x , x , х Неосновные переменные - 1 2 x , x n – количество переменных (n = 5); m – количество основных переменных (m = 3); Находим исходное допустимое опорное (базисное) решение. Базисное решение – решение, при котором неосновные переменные равны нулю x1  0, x2  0 , тогда подставляя значения переменных в уравнения системы ограничений получаем.             40 40 24 , 0 5 4 3 1 2 1 x x x x x x - 1-ое опорное решение. Решение является допустимым, т.к. нет отрицательных значений. Находим значение целевой функции: f (x1 )  1×0+3×0 + 24 = 24 Дальнейшее решение оформляем в симплексные таблицы (таблица 3). i c - коэффициенты при основных переменных в функции цели f (x) ; j c - коэффициенты при переменных функции цели. Таблица 3 Симплексные таблицы