Для изготовления двух видов продукции Р1 и Р2 используют четыре вида ресурсов

Для изготовления двух видов продукции Р1 и Р2 используют четыре вида ресурсов, имеющихся в ограниченном количестве. Определить план выпуска продукции, при котором будет достигнута максимальная прибыль, исходные данные задачи приведены в табл.1. Таблица 1 Виды ресурсов Объем ресурсов Норма расхода на единицу продукции Р1 Р2 S1 18 1 3 S2 16 2 1 S3 5 – 1 S4 21 3 – Прибыль (тыс.руб.) от производства единицы продукции Р1 и Р2 – 2, и 3 соответственно. Решение. Необходимо спланировать выпуск продукции таким образом, чтобы прибыль была максимальной. Определим переменные задачи: х1- количество продукции Р1; x2 – количество продукции Р2. Суммарная прибыль от производства равна z=2х1+3×2. Целью является определение среди всех допустимых значений x1, х2 таких, которые максимизируют суммарную прибыль, т. е. целевую функцию z. Перейдем к ограничениям, которые налагаются на x1, х2. Объем производства продукции не может быть отрицательным, следовательно: x1, x2≥0. Расход всех ресурсов для изготовления двух видов продукции Р1 и Р2 не может превосходить их имеющийся объем, следовательно: x1+3×2≤18, 2×1+x2≤16, x2≤5 3×1≤21 Таким образом, математическая модель данной задачи имеет следующий вид: z=2х1+3×2→ max x1+3×2≤18 2×1+x2≤16×2≤53×1≤21×1, x2≥0 Данная модель является линейной, т. к. целевая функция и ограничения линейно зависят от переменных. Решим задачу графическим методом. z=2х1+3×2→ max x1+3×2≤18 2×1+x2≤16×2≤53×1≤21×1, x2≥0 Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами. Границей неравенства x1+3×2≤18 является прямаяx1+3×2=18, построим ее по двум точкам: Х1 0 18 Х2 6 0 Произвольная точка (0; 0) удовлетворяет неравенству x1+3×2≤18, поэтому областью решения неравенства является область, в которой находится точка (0; 0). Полуплоскость решения обозначена стрелкой. Границей неравенства 2×1+x2≤16 является прямая 2×1+x2=16, построим ее по двум точкам: Х1 0 8 Х2 16 0 Произвольная точка (0; 0) удовлетворяет неравенству 2×1+x2≤16, поэтому областью решения неравенства является область, в которой находится точка (0; 0). Полуплоскость решения обозначена стрелкой. Неравенство x2≤5 задает полуплоскость, расположенную ниже прямой x2=5. Полуплоскость решения обозначена стрелкой. Неравенство 3×1≤21 или x1≤7 задает полуплоскость, расположенную левее прямой x1=7. Полуплоскость решения обозначена стрелкой. Пересечением полуплоскостей будет являться область, координаты точек которой удовлетворяют условию неравенств системы ограничений задачи. Неравенство x1, x2≥0 ограничивают область допустимых решений первым квадрантом. Имеем многоугольник решений ОАВСDE. Рассмотрим целевую функцию задачи: z=2х1+3×2→ max. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление возрастания функции Z(X). Начало вектора – точка (0; 0), конец – точка (2; 3). Строим прямую 2х1+3×2=const (2х1+3×2=const) – линию уровня функции Z, перпендикулярную вектору-градиенту. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта “зеленая” прямая. Она пересекает область в точке C, которая получена в результате пересечения прямых 2×1+x2=16 и x1+3×2=18. Тогда ее координаты удовлетворяют уравнениям этих прямых. Составим систему уравнений: 2×1+x2=16 ,x1+3×2=18. Из второго уравнения выражаем x1=18-3×2 и подставляем в первое: 2(18-3×2 )+x2=16, 36-6×2+х2=16, x2=4 x1=18-12=6 Итак, x1=6, x2=4. Таким образом, максимальное значение целевой функции: z=2х1+3×2=2∙6+3∙4=24 Решим задачу симплекс-методом. Приведем задачу z=2х1+3×2→ max x1+3×2≤18 2×1+x2≤16×2≤53×1≤21×1, x2≥0 к канонической форме. Для этого от системы неравенств перейдем к системе линейных уравнений, введя дополнительные переменные х3, x4, x5, х6 и перепишем условие задачи: z=2х1+3×2→ max x1+3×2+x3=18 2×1+x2+x4=16×2+x5=53×1+x6=21×1, x2,x3,x4,x5,x6≥0 Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Решим систему уравнений относительно базисных переменных: x3,x4,x5,x6. Полагая, что свободные переменные равны 0, получим первый опорный план: X = (0,0, 18,16,5,21) Базисное решение называется допустимым, если оно неотрицательно. Составим симплекс-таблицу: Первая симплекс-таблица Базис Свободные члены Свободные переменные X1 X2 X3 X4 X5 X6 X3 18 1 3 1 0 0 0 X4 16 2 1 0 1 0 0 X5 5 0 1 0 0 1 0 X6 21 3 0 0 0 0 1 Индексная строка 0 -2 -3 0 0 0 0 Индексная строка есть результат вычитания из нуля коэффициентов перед свободными переменными. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ключевого выберем столбец, соответствующий переменной x1 (при отыскании максимума выбирается наименьший отрицательный элемент в индексной строке – это -3). Компоненты вектора свободных членов делятся на положительные элементы ключевого столбца и из них выбирается наименьшее. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (18:3 , 16:1,5:1) = min (6,16,5)=5 Следовательно, третья строка является ведущей. Разрешающий элемент равен 1, он находится на пересечении ключевого столбца и ключевой строки. Вместо переменной x5 в план войдет переменная x2. Каждый элемент ключевой строки делится на разрешающий элемент. Полученные частные являются элементами ключевой строки следующей таблицы. Ключевой столбец в новой таблице – нули, за исключением разрешающего элемента. Остальные элементы рассчитываются по схеме (выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент): Эн = ЭС – (Э1х Э2)/ ЭР Эн – новый элемент, ЭС – старый элемент, Э1 – элемент ключевой строки, Э2 – элемент ключевого столбца, ЭР – разрешающий элемент. Получаем новую симплекс-таблицу: Вторая симплекс-таблица Базис Свободные члены Свободные переменные X1 X2 X3 X4 X5 X6 X3 3 1 0 1 0 -3 0 X4 11 2 0 0 1 -1 0 X2 5 0 1 0 0 1 0 X6 21 3 0 0 0 0 1 Индексная строка 15 -2 0 0 0 3 0 В столбце свободных членов все элементы положительны, то полученное решение является допустимым. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ключевого выберем столбец, соответствующий переменной x1 (наименьший отрицательный элемент в индексной строке – это -20). Компоненты вектора свободных членов делим на положительные элементы ключевого столбца и из них выбираем наименьшее: min (3:1 , 11:2,21:3) = min (3, 5.5, 7)=3 Следовательно, первая строка является ведущей. Разрешающий элемент равен 1. Вместо переменной x5 в план войдет переменная x2. Получаем новую симплекс-таблицу: Третья симплекс-таблица Базис Свободные члены Свободные переменные X1 X2 X3 X4 X5 X6 X1 3 1 0 1 0 -3 0 X4 5 0 0 -2 1 5 0 X2 5 0 1 0 0 1 0 X6 12 0 0 -3 0 9 1 Индексная строка 21 0 0 2 0 -3 0 В столбце свободных членов все элементы положительны, то полученное решение является допустимым. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ключевого выберем столбец, соответствующий переменной x5 (наименьший отрицательный элемент в индексной строке – это -3). Компоненты вектора свободных членов делим на положительные элементы ключевого столбца и из них выбираем наименьшее: min (5:5 , 5:1,12:9) = min (1, 5, 4/3)= 1 Следовательно, вторая строка является ведущей. Разрешающий элемент равен 5. Вместо переменной x4 в план войдет переменная x5. Получаем новую симплекс-таблицу: Четвертая симплекс-таблица Базис Свободные члены Свободные переменные X1 X2 X3 X4 X5 X6 X1 6 1 0 -15 35 0 0 X5 1 0 0 -25 15 1 0 X2 4 0 1 25 -15 0 0 X6 3 0 0 35 -95 0 1 Индексная строка 24 0 0 45 35 0 0 Среди значений индексной строки нет отрицательных. Поэтому таблица определяет оптимальный план задачи. Т.е. полученное решение максимизирует целевую функцию. При этом оптимальным планом будут величины: х1=6, х2=4 (они свободные), x5=1, х6=3 (они базисные), целевая функция: z=2х1+3×2=2∙6+3∙4=24 Значения базисных переменных x5=1 и х6=3 означают то, что имеются резервы ресурсов S3 в количестве 1 единицы и S4 в количестве 3 единиц, что свидетельствует об их излишках. Решим задачу с помощью MS Excel. На рабочем листе введем числовые данные задачи. Для оптимального решения, которое появится после вычислений, отведены ячейки B8:В9. Ячейка В11 зарезервирована для вычисления значения целевой функции, ячейки F3:F6 – для левых частей ограничений. В режиме отображения формул заполненная таблица имеет вид: Поскольку ячейки оптимального решения B8:В9 не содержат данных, значение расхода сырья и целевой функции пока 0. Подключим надстройку Excel «Поиск решения» (если она отсутствует на ленте «Данные»). Кнопка «Office», параметры Excel, Надстройки, Перейти и в диалоговом окне выбираем «Поиск решения»: В результате на ленте «Данные» в группе «Анализ» появилась соответствующая надстройка. Выбираем команду «Поиск решения» и в появившееся диалоговое окно вводим данные, при этом ограничения удобнее задавать в виде диапазонов: Нажимаем ОК, затем “Выполнить”. После нажатия кнопки «Выполнить» открывается окно «Результаты поиска решения», которое сообщает, что решение найдено. Сохраняем его:

Часть выполненной работы