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

Заказ №38664

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

Решение:

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