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

Заказ №38664

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

Решение: Решение: 1. Построим математическую модель задачи Вводим переменные. Пусть 1 2 3 х , x , x - объем производства продукции видов А, В и С соответственно. Составляем функцию цели. Необходимо максимизировать прибыль. 1 2 3 1 max f (x) c x 2х 5х x n j   j j     Экономический смысл: 2 1 5 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-м ограничении знак – строгое равно. 84 Прямое ограничение. Т.к. количество изделий не может быть отрицательным числом, то x1 , x2 , x3  0 . Таким образом, имеем задачу линейного программирования: Найти вектор значений ( , , ) 1 2 3 x  x x x , при котором функция цели 2 1 5 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 . Преобразуем систему ограничений:                     , 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)  2х1  5х2  x3  2x1  5x2  24  2x1  4x2  x2  24 Таким образом, имеем задачу линейного программирования с двумя переменными:

Найти вектор значений ( , ) 1 2 x  x x , при котором функция цели f (x)  x2  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). 0 x1  0 x1  - решение – прямая, совпадающая с осью ОХ2 0 x1  - решение – правая полуплоскость. 0 x2  0 x2  - решение – прямая, совпадающая с осью ОХ1 0 x2  - решение – верхняя полуплоскость. 86 Т.е. ограничения х1  0 и х2  0 показывают, что решение системы находится в I четверти системы координат. Пересечение этих полуплоскостей, каждая из которых определяется соответствующим неравенством системы и удовлетворяет условиям, определяет выпуклый многоугольник. Данный многоугольник – область допустимых значений. Любая точка этой области является допустимым решением задачи. Рисунок 1 - Решение задачи графическим методом

б) Найдем оптимальное решение Оптимальное решение может быть только в угловых точках многоугольника. Чтобы найти оптимальное решение можно найти координаты всех угловых точек многоугольника, вычислить значение целевой функции во всех угловых точках. Наибольшее из этих значений и будет максимальным значением целевой функции, а координаты соответствующей угловой точки – оптимальным решением. Существует другой способ, который позволяет графически сразу найти угловую точку, соответствующую оптимальному решению. Для этого построим линию уровня. Приравняем целевую функцию без константы постоянной величине а: f (x)  х2  а 87 Это уравнение является множеством точек, в котором целевая функция принимает значение, равное а. Меняя значение а, получим семейство параллельных прямых, каждая из которых называется линией уровня. В данном случае, линия уровня – любая линия, параллельная оси ОХ1. Для определения направления движения к оптимуму построим вектор-градиент С  , координаты которого являются частными производными функции f(x), т.е. С  =(0;1). Чтобы построить этот вектор, нужно начало координат соединить с точкой (0; 1). Поскольку задача стоит на максимизацию, перемещаем линию уровня по направлению вектораградиента С  . Максимума ( , ) 1 2 f x x достигает в угловой точке А. Находим координаты т. А:      5 0

Находим значение функции цели: max f (x)  x2  24  5 + 24 = 29 Ответ: max f (x)  29 при х1 = 0, х2 = 5. Найдем значение объема выпуска продукции 3-гор вида: 3 24 2 1 4 2 x   x  x = 24 – 2×0 – 4×5 = 4 Экономический смысл: Максимальная прибыль от реализации изделий всех видов составит 29 ден.ед., если производить 5 единиц продукции вида В и 4 единицы продукции вида С, а изделия вида А не производить совсем. При таком объеме производства все 24 единицы сырья вида III будут израсходованы. 4. Приведем задачу к канонической форме Канонический вид записи модели, т.е. когда система функциональных ограничений состоит только из уравнений с неотрицательной правой частью. В левые части неравенств вводим неотрицательные добавочные переменные со знаком «+» (т.к. знак неравенства ≤ ):                  , , , , 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 )  х2  24  0  24  24 Дальнейшее решение оформляем в симплексные таблицы (таблица 5). i c - коэффициенты при основных переменных в функции цели f (x) ; j c - коэффициенты при переменных функции цели. Таблица 5 Симплексные таблицы