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

заказ №38669

Для производства трех видов продукции A, B, C используется три вида сырья I, II, III. Нормы затрат каждого из видов сырья на единицу продукции каждого вида, а также прибыль с единицы продукции приведены в таблице. Таблица 4 - Данные по продукции Сырье Продукция Запас сырья А В С 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.1 Переменные задачи 1 2 3 х , x , x - объем производства продукции видов А, В и С соответственно. 1.2 Функция цели 192 Прибыль с единицы продукции видов А, В и С составляет 2, 5 и 1 ден.ед. соответственно. Следовательно, прибыль с объемов производства 1 2 3 х , x , x единиц продукции будет равна 2 1 5 2 3 х  х  x . Получаем функцию цели: f (x)  2х1  5х2  x3 max 1.3 Ограничения задачи Составляем ограничения по сырью (функциональные ограничения): 4 1 12 2 3 x  x  x - затраты сырья I вида на производство всей продукции; 6 1 8 2 3 x  х  x - затраты сырья II вида на производство всей продукции; 2 1 4 2 3 х  х  x - затраты сырья III вида на производство всей продукции. Запасы продукции составляют 54, 64 и 24 единицы соответственно. При этом сырье III должно быть полностью израсходовано. Получаем ограничения:               2 4 24 6 8 64 4 12 64 1 2 3 1 2 3 1 2 3 х х x x х x x x x Т.к. количество изделий не может быть отрицательным числом, то имеем прямое ограничения: x1 , x2 , x3  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 2. Приведем задачу к стандартной форме Стандартная форма записи модели (симметричная) – модель, когда все функциональные ограничения задаются неравенствами, т.е. необходимо, чтобы во всех ограничениях по сырью знак был  .. Получаем, 193                 , , 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.1 Преобразуем модель задачи Графический метод применяет для решения ЗЛП с двумя переменными. Выразим переменную 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 3.2 Построим область допустимых решений системы ограничения Решением каждого ограничения системы является полуплоскость с граничащей ей прямой. Таблица 5 – Построение области допустимых решений № Ограничение решение пояснение 1 2 8 40 х1  х2  2 8 40 х1  х2  прямая проходит через точки (0;5) и (20;0) 194 Прямая А1А2 на графике 2 8 40 х1  х2  полуплоскост ь включает точку начала координат 2 4х1  4х2  40 4х1  4х2  40 прямая проходит через точки (0;10) и (10;0) Прямая В1В2 на графике 4х1  4х2  40 полуплоскост ь включает точку начала координат 3 2х1  4х2  24 2х1  4х2  24 прямая проходит через точки (0;6) и (12;0) Прямая С1С2 на графке 2х1  4х2  24 полуплоскост ь включает точку начала координат 0 x1  0 x1  - решение – прямая, совпадающая с осью ОХ2 0 x1  - решение – правая полуплоскость. 0 x2  0 x2  - решение – прямая, совпадающая с осью ОХ1 0 x2  - решение – верхняя полуплоскость. Т.е. ограничения х1  0 и х2  0 показывают, что решение системы находится в I четверти системы координат. Пересечение этих полуплоскостей, каждая из которых определяется соответствующим неравенством системы и удовлетворяет условиям, определяет выпуклый многоугольник. Данный многоугольник – область допустимых значений. Любая точка этой области является допустимым решением задачи. 195 Рисунок 1 - Решение задачи графическим методом 3.3 Найдем оптимальное решение Оптимальное решение может быть только в угловых точках многоугольника. Для нахождения оптимальной точки построим вектор-градиент С. С  , координаты которого являются частными производными функции f(x), т.е. С  =(0;1). Чтобы построить этот вектор, нужно начало координат соединить с точкой (0; 1). Построим линию уровня – линию, параллельную вектору-градиенту. Приравняем целевую функцию без константы постоянной величине а: f (x)  х2  а Это уравнение является множеством точек, в котором целевая функция принимает значение, равное а. Меняя значение а, получим семейство параллельных прямых, каждая из которых называется линией уровня. В данном случае, линия уровня – любая линия, параллельная оси ОХ1. Поскольку задача стоит на максимизацию, перемещаем линию уровня по направлению вектора- градиента С  . Максимума ( , ) 1 2 f x x достигает в угловой точке А1. Находим координаты т. А1:      5 0 2 1 x x Находим значение функции цели: max f (x)  x2  24  5 + 24 = 29 196 Ответ: max f (x)  29 при х1 = 0, х2 = 5. Найдем значение объема выпуска продукции 3-гор вида: 3 24 2 1 4 2 x   x  x = 24 – 2×0 – 4×5 = 4 Для исходной задачи имеем: max f (x)  29 при х1 = 0, х2 = 5, х3 = 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. Решим полученную задачу симплекс-методом 5.1 Находим первое допустимое базисное решение 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 , тогда подставляя значения переменных в уравнения системы ограничений получаем.