Формирование плана выпуска изделий на месяц. Построение экономико-математических моделей для функции выручки, себестоимости, прибыли. Рассмотрение графика решения системы неравенств. Анализ экономико-математической модели для многокритериальной задачи.
Система ограничений: , Запишем задачу в канонической форме: , В задаче отсутствует единичный базис. На второй итерации получен оптимальный план вспомогательной задачи: х0 = (0; 0; 35/6; 19/2; 32/3), о чем свидетельствуют неотрицательные двойственные оценки и отсутствие отрицательных компонент в столбце А0. Оптимальный план вспомогательной задачи будет использоваться как начальное БДП для основной задачи. На третьей итерации нет отрицательных двойственных оценок и отрицательных компонент в столбце А0, значит получен оптимальный план основной задачи: х* = (1; 16; 0; 10; 0) и значение целевой функции С(х*) = 318. Находятся для оптимального плана. х* = (1;16;0;10;0) х4 - количество ресурса R1 на складе после производства х5 - количество ресурса R2 на складе после производства. х4 = 10, значит после производства на складе осталось 10 единиц ресурса R1, то есть R1 - избыточный ресурс относительно этого оптимального плана. х5 = 0, значит после производства на складе не осталось ресурса R2, то есть R2 - дефицитный ресурс.
Введение
Постановка задачи: Промышленное предприятие может изготавливать три вида изделий A, B, C, используя при этом три основных, т.е. определяющих программу выпуска ресурсов R1, R2, R3. Нормы расхода ресурсов на единицу изделий каждого вида, запасы ресурсов на месяц, себестоимость изготовления единицы изделия и их цены приведены в табл.1. По требованиям технологии ресурс R3 должен быть полностью израсходован в течение месяца. Необходимо сформировать план выпуска изделий на месяц, применяя следующие критерии: 1. Максимум получаемой прибыли.
2. Минимум себестоимости изготовления изделий.
Таблица 1 Исходные данные
Наименование показателей Нормы расхода ресурсов на одно изделие Запасы ресурсов
Себестоимость изготовления изделий, тыс.руб. 11 16 18
Цена единицы изделия, тыс.руб. 14 19 18
Прибыль от реализации единицы продукции, тыс.руб. 3 3 5
Основная часть
Задача 1
Построить соответствующие экономико-математические модели рассматриваемых однокритериальных и многокритериальных задач.
Экономико-математическая модель для функции «выручка»: х1 - количество продукции А;
х2 - количество продукции В;
х3 - количество продукции С.
Целевая функция выглядит следующим образом: С1(х) = 14х1 19х2 23х3 > max
Система ограничений: , Экономико-математическая модель для функции «себестоимость»: Целевая функция: С2(х) = 11х1 16х2 18х3 > min
Система ограничений: , Экономико-математическая модель для функции «прибыль»: Целевая функция: С3(х) = 3х1 3х2 5х3 > max
Система ограничений: , Экономико-математическая модель для многокритериальной задачи (себестоимость и прибыль): Целевые функции: С2(х) = 11х1 16х2 18х3 > min
С3(х) = 3х1 3х2 5х3 > max
Система ограничений: , Задача 2
Решить однокритериальную задачу линейного программирования (ЗЛП) с целевой функцией «выручка» симплекс-методом. Выполнить послеоптимизационный анализ. Целочисленное решение получить методом Гомори и методом ветвей и границ. экономика себестоимость прибыль
Решение: х1 - количество продукции А;
х2 - количество продукции В;
х3 - количество продукции С.
Целевая функция выглядит следующим образом: С1(х) = 14х1 19х2 23х3 > max
Система ограничений: , Запишем задачу в канонической форме: , В задаче отсутствует единичный базис. Применим метод искусственного базиса.
Целевая функция для вспомогательной задачи: ( ) = -х6 > max
Система ограничений: , БДП вспомогательной задачи: = (0;0;0;27;34;35). Симплекс-таблица для вспомогательной задачи представлена в таблице 2: Таблица 2. Решение вспомогательной задачи
На второй итерации получен оптимальный план вспомогательной задачи: х0 = (0; 0; 35/6; 19/2; 32/3), о чем свидетельствуют неотрицательные двойственные оценки и отсутствие отрицательных компонент в столбце А0.
Оптимальный план вспомогательной задачи будет использоваться как начальное БДП для основной задачи. Для этого пересчитаем двойственные оценки основной задачи, используя начальный БДП х0 = (0; 0; 35/6; 19/2; 32/3).
На первой итерации минимальная из отрицательных двойственных оценок: -34/3, значит А2 вводится в базис, А5 выводится. После пересчета таблицы есть одна отрицательная двойственная оценка, поэтому столбик А1 вводится в базис, А3 выводится. На третьей итерации нет отрицательных двойственных оценок и отрицательных компонент в столбце А0, значит получен оптимальный план основной задачи: х* = (1; 16; 0; 10; 0) и значение целевой функции С(х*) = 318. Задача решена.
Послеоптимизационный анализ.
1. Интервал устойчивости.
Общая формула: Sk = (bk ?bkmin; bk ?bkmax)
Интервал устойчивости Sk показывает, как может изменяться значение bk, чтобы структура оптимального плана не изменялась.
S1 = (b1 ?b1min; b1 ?b1max) k= 1; n = 3; n k = 4; b1 = 27.
?b1min = -10/1 = -10
?b1max = ?
S1 = (27 (-10)); 27 ?) = (17; ?).
S2 = (b2 ?b2min; b2 ?b2max) k= 2; n = 3; n k = 5; b1 = 34.
?b2min = -16 : 3/2 = -32/3 = - 10
?b2max = min { -10 : (-1/2); -1 : (-1)} = min {20;1} = 1
S2 = (34 (- 10 ); 34 1) = (24 ; 35)
Ресурс R3 расходуется полностью, поэтому интервал устойчивости для него - одно число, равное 35.
2. Интервал оптимальности.
Интервал оптимальности - это значения коэффициентов целевой функции, которые не влекут изменения оптимального плана.
Общая формула: Pk = [ Ck ?Ckmin; Ck ?Ckmax]
P1 = [ C1 ?C1min; C1 ?C1max]
С1 = 14
?C1min = -5/1 = -5
?C1max = -29/2 : (-1/2) = 29
P1 = [ 14 (-5); 14 29] = [9;43]
P2 = [ C2 ?C2min; C2 ?C2max]
С2 = 19
?C2min = -29/2: 3/2 = -29/3 = -9
?C2max = ?
P2 = [19 (-9 ); 19 ?] = [10 ; ?]
P3 = [ C3 ?C3min; C3 ?C3max]
С3 = 23
?C3min = -5/2 = -2,5
?C3max =-29/2 : (-1) = 29/2 = 14,5
P3 = [23 (-2,5); 23 14,5] = [20,5; 37,5]
3. Избыточные и дефицитные ресурсы.
Находятся для оптимального плана. х* = (1;16;0;10;0) х4 - количество ресурса R1 на складе после производства х5 - количество ресурса R2 на складе после производства. х4* = 10, значит после производства на складе осталось 10 единиц ресурса R1, то есть R1 - избыточный ресурс относительно этого оптимального плана. х5* = 0, значит после производства на складе не осталось ресурса R2, то есть R2 - дефицитный ресурс.
Ресурс R3 не остается на складе после производства, так как должен быть полностью использован.
Задача 3
Решить однокритериальную задачу линейного программирования с целевой функцией «прибыль» геометрически.
Решение: х1 - количество продукции А;
х2 - количество продукции В;
х3 - количество продукции С.
Целевая функция: С3(х) = 3х1 3х2 5х3 > max
Система ограничений: , Выразим третью переменную из третьего ограничения: х3=
После преобразований целевая функция и ограничения примут следующий вид: С3(х) = -3х1 8х2 175> max
, Чтобы решить задачу графически, необходимо решить систему неравенств. На рисунке 1 отображено решение системы неравенств, градиент и линии уровня целевой функции. Решением задачи является точка пересечения первого и второго ограничений, на графике обозначена буквой А и имеет координаты (1;16)
Рисунок 1 - графическое решение задачи
Полученные значения х1 и х2 необходимо подставить в х3, которое ранее было выражено из третьего ограничения: х3 = 0.
Ответ: х1* = 1; х2* = 16, х3* = 0, С3(х*) = 51.
Задача 4
Решить две однокритериальные задачи при следующих условиях: Цена каждой единицы изделия (cj, j = 1,2,3) может изменяться, причем эти изменения определяются соотношениями: с1= 14-?; с2 = 19 ?; с3 = 23 2?, где ? - некоторый параметр. Для каждого из возможных значений цены изделий найти план производства (не обязательно целочисленный), при котором суммарная выручка была бы максимальной.
Решение: х1 - количество продукции А;
х2 - количество продукции В;
х3 - количество продукции С.
Целевая функция выглядит следующим образом: С1(х) = 14х1 19х2 23х3 > max
Система ограничений: , Запишем задачу в канонической форме: , В задаче отсутствует единичный базис. Применим метод искусственного базиса.
Целевая функция для вспомогательной задачи: ( ) = -х6 > max
Система ограничений: , БДП вспомогательной задачи: = (0;0;0;27;34;35). Симплекс-таблица для вспомогательной задачи представлена в таблице 2: Таблица 4 Решение вспомогательной задачи
На второй итерации получен оптимальный план вспомогательной задачи: х0 = (0; 0; 35/6; 19/2; 32/3), о чем свидетельствуют неотрицательные двойственные оценки и отсутствие отрицательных компонент в столбце А0.
Оптимальный план вспомогательной задачи будет использоваться как начальное БДП для основной задачи. Для этого пересчитаем двойственные оценки основной задачи, используя начальный БДП х0 = (0; 0; 35/6; 19/2; 32/3).
Чтобы х0 = (0; 0; 35/6; 19/2; 32/3) = (0; 0; 5 ; 9,5; 10 ) был оптимальным планом, необходимо и достаточно выполнения следующих условий: , Система не имеет решений.
Зафиксируем значение ?: ?ф = 0. Тогда на второй итерации в базис будет вводиться А2, выводиться - А5.
Предприятие может использовать не более чем 27 2? единиц ресурса R1 и не более чем 34-? единиц ресурса R2, где ? - некоторый параметр. Для каждого возможного значения ? определить план производства изделий, при котором выручка от реализации является максимальной.
Решение: х1 - количество продукции А;
х2 - количество продукции В;
х3 - количество продукции С.
Целевая функция выглядит следующим образом: С1(х) = 14х1 19х2 23х3 > max
Система ограничений: , Запишем задачу в канонической форме: , В задаче отсутствует единичный базис. Применим метод искусственного базиса.
Целевая функция для вспомогательной задачи: ( ) = -х6 > max
Система ограничений: , БДП вспомогательной задачи: = (0;0;0;27;34;35). Симплекс-таблица для вспомогательной задачи представлена в таблице 2: Таблица 9 Решение вспомогательной задачи
На второй итерации получен оптимальный план вспомогательной задачи: х0 = (0; 0; 35/6; 19/2; 32/3), о чем свидетельствуют неотрицательные двойственные оценки и отсутствие отрицательных компонент в столбце А0.
Оптимальный план вспомогательной задачи будет использоваться как начальное БДП для основной задачи. Для этого пересчитаем двойственные оценки основной задачи, используя начальный БДП х0 = (0; 0; 35/6; 19/2; 32/3).
На первой итерации есть отрицательные двойственные оценки, наименьшая из них -34/3, поэтому столбец А2 вводится в базис. На второй итерации есть отрицательная двойственная оценка -5/2, поэтому столбец А1 вводится в базис. При пересчете таблицы получен БДП х2 = ( 1 ?; 16 - 1,5 ?; 0; 10 2,5?)
Чтобы БДП х2 был оптимальным, необходимо, чтобы все двойственные оценки компоненты в А0 были неотрицательны: => 1 ? ? ? 10
При ? ? [1; 10 ] оптимальный план х2 = ( 1 ?; 16 - 1,5 ?; 0; 10 2,5?) и значение целевой функции С(х2) = 318 - 14,5?.
Проанализируем ситуацию, когда ? > 10 , тогда неравенство 16 - 3/2? ? 0 перестанет выполняться, то есть в А0 появится отрицательная компонента, будет применяться двойственный симплекс-метод. Но при ? > 10 задача не имеет решения.
Проанализируем случай, когда ? < 1, тогда А1 станет отрицательной и будет выводиться из базиса, применим двойственный симплекс-метод.
Чтобы х3 = (0, 35/2; 0; 19/2 2?; -1-?) = (0; 17,5; 0; 9,5 2?; -1-?) был оптимальным планом, необходимо, чтобы все двойственные оценки компоненты в А0 были неотрицательны: => -4.75 ? ? < -1
При ? ? [-4,75; -1) оптимальный план х3 = (0; 17,5; 0; 9,5 2?; -1-?) и значение целевой функции С(х3) = 332,5
Проанализируем ситуацию, когда ? < - 4,75, тогда А4 станет отрицательной и будет выводиться из базиса, применим двойственный симплекс-метод.
Чтобы х4 = (-19 - 4?; 46 6?; 0; 0; -20 - 5?) был оптимальным планом, необходимо, чтобы все двойственные оценки компоненты в А0 были неотрицательны: => -7 ? ? < -4,75
При ? ? [-7 ; -4,75) оптимальный план х4 = (-19 - 4?; 46 6?; 0; 0; -20 - 5?) и значение целевой функции С(х4) = 608 58?.
Проанализируем случай, когда ? < -7 , тогда неравенство 46 6? ? 0 перестанет выполняться, то есть в А0 появится отрицательная компонента, будет применяться двойственный симплекс-метод. Но при ? < -7 задача не имеет решения.
Ответ: Для всех значений параметра -? < ? < ? найдены оптимальные планы и целевые функции: 1. ? ? [1; 10 ], х2* = ( 1 ?; 16 - 1,5 ?; 0; 10 2,5?), С(х2*) = 318 - 14,5?.
