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

Заказ №38664

Для производства трех видов продукции A, B, C используется три вида сырья I, II, III. Нормы затрат каждого из видов сырья на единицу продукции каждого вида, а также прибыль с единицы продукции приведены в таблице. Таблица 2 Данные по продукции Сырье Продукция Запас сырья А В С I 4 6 1 32 II 6 4 1 32 III 2 2 1 12 Прибыль 4 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 4х 5х x n j   j j     136 4 1 5 2 3 х  х  x - общая прибыль от производства изделий всех трех видов. Функциональные ограничения (по сырью):               2 2 12 6 4 32 4 6 32 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 , при котором функция цели 4 1 5 2 3 f (x)  x  x  x достигает максимального значения, при ограничениях:                  , , 0 2 2 12 6 4 32 4 6 32 1 2 3 1 2 3 1 2 3 1 2 3 x x x х х x x х x x x x 2. Приведем задачу к стандартной форме При стандартной форме модели необходимо, чтобы во всех функциональных ограничениях знак был  .                 , , 0 2 2 12 6 4 32 4 6 32 1 2 3 1 2 1 2 3 1 2 3 x x x х х x х x x x x 3. Решим задачу графическим методом 3.1 Преобразуем ЗЛП в ЗЛП с двумя переменными Графический метод применяет для решения ЗЛП с двумя переменными. Выразим переменную 3 x из 3-го ограничения через переменные 1 2 x , x : 3 12 2 1 2 2 x   x  x . Преобразуем систему ограничений: 137                     , 0 2 2 12 6 4 12 2 2 32 4 6 12 2 2 32 1 2 1 2 1 2 1 2 1 2 1 2 x x х х x х x x x x x x или               , 0 2 2 12 4 2 20 2 4 20 1 2 1 2 1 2 1 2 x x х х x х x x Функция цели: max f (x)  4х1  5х2  x3  4x1  5x2 12  2x1  2x2  2x1  3x2 12 Таким образом, имеем задачу линейного программирования с двумя переменными: Найти вектор значений ( , ) 1 2 x  x x , при котором функция цели f (x)  2x1  3x2 12 достигает максимального значения, при ограничениях:               , 0 2 2 12 4 2 20 2 4 20 1 2 1 2 1 2 1 2 x x х х x х x x 3.2 Построим область допустимых решений системы ограничений Решением каждого ограничения системы является полуплоскость с граничащей ей прямой. Таблица 3 Построение области допустимых решений № Ограничение решение пояснение (1) 2х1  4х2  20 2х1  4х2  20 прямая проходит через точки (0;5) и (10;0) 2х1  4х2  20 полуплоскост ь включает точку начала координат (2) 4х1  2х2  20 4х1  2х2  20 прямая проходит через точки (0;10) и (5;0) 4х1  2х2  20 полуплоскост ь включает точку начала координат (3) 2 2 12 х1  х2  2 2 12 х1  х2  прямая проходит через точки (0;6) и (6;0) 2 2 12 х1  х2  полуплоскост ь включает точку начала координат Прямые ограничения х1  0 и х2  0 показывают, что решение системы находится в I четверти системы координат. 138 Пересечение этих полуплоскостей, каждая из которых определяется соответствующим неравенством системы и удовлетворяет условиям, определяет выпуклый многоугольник. Данный многоугольник – область допустимых значений. Любая точка этой области является допустимым решением задачи. Рисунок 2 - Решение задачи графическим методом 3.3 Найдем оптимальное решение Оптимальное решение может быть только в угловых точках многоугольника. Для определения оптимального решения построим вектор-градиент С  , координаты которого являются частными производными функции f(x), т.е. С  =(2;3). Чтобы построить этот вектор, нужно начало координат соединить с точкой (2; 3). Построим линию уровня – линию. параллельную вектору-градиенту:. f (x)  2х1  3х2  а - линия уровня. Вектор-градиент показывает увеличение целевой функции. Поскольку задача стоит на максимизацию, перемещаем линию уровня по направлению вектора- градиента С  . Максимума ( , ) 1 2 f x x достигает в угловой точке А. Находим координаты т. А. Она лежит на пересечении прямых, соответствующих ограничениям (1) и (3): 139        2 2 12 2 4 20 1 2 1 2 x x x x Получаем,      4 2 2 1 x x Находим значение функции цели: max f (x)  2×2+3×4 + 12 = 28 Ответ: max f (x)  28 при х1 = 2, х2 = 4. Найдем значение объема выпуска продукции 3-го вида: 3 12 2 1 2 2 x   x  x = 12 – 2×2 – 2×4 = 0 Экономический смысл: Максимальная прибыль от реализации изделий всех видов составит 28 ден.ед., если производить 2 единицы изделий вида А и 4 единицы изделий вида В, а изделия вида С не производить совсем. При таком объеме производства все 12 единицы сырья вида III будут израсходованы. 4. Приведем задачу к канонической форме Канонический вид записи модели, т.е. когда система функциональных ограничений состоит только из уравнений с неотрицательной правой частью. В левые части неравенств вводим неотрицательные добавочные переменные со знаком «+» (т.к. знак неравенства ≤ ):                  , , , , 0 2 2 12 4 2 20 2 4 20 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) будут не основные. Выпишем матрицу из коэффициентов при переменных системы ограничений: 140 Координаты переменных 3 4 5 x , x , х образуют единичную матрицу 3-го порядка. Их берем за основные. Основные переменные - 3 4 5 x , x , х Неосновные переменные - 1 2 x , x Находим исходное допустимое опорное (базисное) решение. Базисное решение – решение, при котором неосновные переменные равны нулю x1  0, x2  0 , тогда подставляя значения переменных в уравнения системы ограничений получаем.             20 20 12 , 0 5 4 3 1 2 1 x x x x x x - 1-ое опорное решение. Решение является допустимым, т.к. нет отрицательных значений. Находим значение целевой функции: f (x1 )  2×0+3×0 + 12 = 12 Дальнейшее решение оформляем в симплексные таблицы (таблица 4). i c - коэффициенты при основных переменных в функции цели f (x) ; j c - коэффициенты при переменных функции цели. Таблица 4 Симплексные таблицы 141 Исследуем 1-ое опорное решение на оптимальность. Для этого находим оценки переменных Δj Оценки переменных входящих в базис равны 0, т.е. , , 0 3 4 5  Оценки остальных переменных находим по формуле: j c а с  j   i  ij  , где