Небольшая фирма производит по заказу партиями стеклянную посуду — наборы стаканов для сока и коктейлей

Небольшая фирма производит по заказу партиями стеклянную посуду — наборы стаканов для сока и коктейлей. Для производства этой посуды фирма закупила специальное оборудование, производственная линия которого которое может быть настроена на производство либо стаканов для сока, либо для коктейлей. Переключение оборудования с одного на другой тип продукции происходит достаточно быстро, так что этим временем можно пренебречь при планировании. 100 наборов стаканов для сока изготовляется за 6 часов, 100 наборов стаканов для коктейлей – за 5 часов. В течение недели, в соответствии с трудовым соглашением, оборудование может быть занято не более чем на 60 часов. Произведенная продукция хранится на складе фирмы емкостью 1 500 кубических метров. Упаковка с набором стаканов для сока занимает 1 м3, а упаковка с набором для коктейлей — 2 м3. Наборы для сока продаются по цене 5 д.е., наборы для коктейлей стоят 4 д.е. , спрос на наборы для сока не превышает 800 штук в неделю, в то время как все произведенные наборы для коктейлей продаются в течение недели. Оптимизировать недельный производственный план. Решение. Для удобства обработки данных, поместим исходные данные задачи в таблицу: Расход на единицу продукции (на один набор) Ресурс сока коктейль Оборудование Объем 6/100 1 5/100 2 60 1500 Прибыль 5 4 Составим математическую модель задачи. Необходимо спланировать недельный объем производства продукции так, чтобы прибыль была максимальной. Поэтому переменными являются: х1- количество наборов для сока; x2 – количество наборов для коктейля. Суммарная недельная прибыль от производства равна z=5х1+4×2. Целью является определение среди всех допустимых значений x1, х2 таких, которые максимизируют суммарную прибыль, т. е. целевую функцию z. Перейдем к ограничениям, которые налагаются на x1, х2. Объем производства продукции не может быть отрицательным, следовательно: x1, x2≥0. Ограничение на использование оборудования: 0,06×1+0,05×2≤60 или 6×1+5×2≤6000 Ограничение по емкости склада: x1+2×2≤1500 Ограничение на спрос – спрос на наборы для сока не превышает 800 штук в неделю: x1≤800 Таким образом, математическая модель данной задачи имеет следующий вид: z=5х1+4×2→ max 6×1+5×2≤6000×1+2×2≤1500×1≤800×1, x2≥0 Решим задачу графическим методом. Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами. 6×1+5×2≤6000, x1+2×2≤1500, x1≤800 Границей неравенства 6×1+5×2≤6000 является прямая6×1+5×2=6000, построим ее по двум точкам: Х1 0 1000 Х2 1200 0 Произвольная точка (0; 0) удовлетворяет неравенству 6×1+5×2≤6000, поэтому областью решения неравенства является область, в которой находится точка (0; 0). Полуплоскость решения обозначена стрелкой. Границей неравенства x1+2×2≤1500 является прямаяx1+2×2=1500, построим ее по двум точкам: Х1 0 1500 Х2 750 0 Произвольная точка (0; 0) удовлетворяет неравенству x1+2×2≤1500, поэтому областью решения неравенства является область, в которой находится точка (0; 0). Полуплоскость решения обозначена стрелкой. Неравенство x1≤800 описывает полуплоскость, лежащую левее прямой x1=800, параллельной оси ординат. Левая полуплоскость решения обозначена стрелкой. Пересечением полуплоскостей будет являться область, координаты точек которой удовлетворяют условию неравенств системы ограничений задачи. Не забудем про ограничения x1, x2≥0: условия неотрицательности переменных ограничивают область допустимых решений первым квадрантом. Имеем многоугольник решений ОАВСD: Рассмотрим целевую функцию задачи: z=5х1+4×2→ max. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление возрастания функции Z(X). Начало вектора – точка (0; 0), конец – точка (5; 4). Для удобства построения вектора- градиента, построим вектор, соноправленный с {5, 4}, который “удобно” изобразить в масштабе построенного изображения, пусть это будет вектор {500, 400}. Строим прямую 500х1+400×2= const – линию уровня функции Z(X), перпендикулярную вектору-градиенту. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта “зеленая” прямая. Она пересекает область в точке С, которая получена в результате пересечения прямых 6×1+5×2=6000 и x1=800. Тогда ее координаты удовлетворяют уравнениям этих прямых. Составим систему уравнений: 6×1+5×2=6000 ,x1=800. Итак, x1=800,×2=240. Таким образом, максимальное значение целевой функции: z=5х1+4×2=5∙800+4∙240=4960 Итак, x1=800, x2=240, zmax=4960 Решим задачу симплекс-методом. Приведем к канонической форме задачу: z=5х1+4×2→ max 6×1+5×2≤6000×1+2×2≤1500×1≤800×1, x2≥0 От системы неравенств перейдем к системе линейных уравнений, введя дополнительные переменные х3, x4, x5 и перепишем условие задачи: z=5х1+4×2→ max 6×1+5×2+x3=6000×1+2×2+x4=1500×1+x5=800×1, x2, x3, x4, x5≥0 Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид: A=65100600012010150010001800 Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Решим систему уравнений относительно базисных переменных: x3,x4,x5. Полагая, что свободные переменные равны 0, получим первый опорный план: X = (0,0,0, 6000,1500,800) Базисное решение называется допустимым, если оно неотрицательно. Составим симплекс-таблицу: Первая симплекс-таблица Базис Свободные члены Свободные переменные X1 X2 X3 X4 X5 X3 6000 6 5 1 0 0 X4 1500 1 2 0 1 0 X5 800 1 0 0 0 1 Индексная строка 0 -5 -4 0 0 0 Индексная строка есть результат вычитания из нуля коэффициентов перед свободными переменными. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ключевого выберем столбец, соответствующий переменной x1 (при отыскании максимума выбирается наименьший отрицательный элемент в индексной строке – это -5). Компоненты вектора свободных членов делятся на положительные элементы ключевого столбца и из них выбирается наименьшее. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (6000: 6 , 1500:1,800:1) = min (1000,1500,800)=800 Следовательно, третья строка является ведущей. Разрешающий элемент равен 1, он находится на пересечении ключевого столбца и ключевой строки. Вместо переменной x5 в план войдет переменная x1. Вторая симплекс-таблица Базис Свободные члены Свободные переменные X1 X2 X3 X4 X5 X3 1200 0 5 1 0 -6 X4 700 0 2 0 1 -1 X1 800 1 0 0 0 1 Индексная строка 4000 0 -4 0 0 5 В столбце свободных членов все элементы положительны, то полученное решение является допустимым. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ключевого выберем столбец, соответствующий переменной x2 (наименьший отрицательный элемент в индексной строке – это -4). Компоненты вектора свободных членов делим на положительные элементы ключевого столбца и из них выбираем наименьшее: min (1200:5 , 700:2) = min (240,350)=240 Следовательно, первая строка является ведущей. Разрешающий элемент равен 1,2, он находится на пересечении ключевого столбца и ключевой строки. Вместо переменной x3 в план войдет переменная x2. Получаем новую симплекс-таблицу: Третья симплекс-таблица Базис Свободные члены Свободные переменные X1 X2 X3 X4 X5 X2 240 0 1 0,2 0 -1,2 X4 220 0 0 -0,4 1 1,4 X1 800 1 0 0 0 1 Индексная строка 4960 0 0 0,8 0 0,2 Среди значений индексной строки нет отрицательных. Поэтому таблица определяет оптимальный план задачи. Т.е. полученное решение максимизирует целевую функцию. При этом оптимальным планом будут величины: х1=800, х2=240 (они свободные), x4 = 220 (она базисная), целевая функция: z=5х1+4×2=5∙800+4∙240=4960 Из этой таблицы также следует, что базисная переменная х4=220, т.е. имеется резерв емкости склада в 220 кубических метров (на складе будет свободное место). Решим задачу с помощью MS Excel. На рабочем листе введем числовые данные задачи. Для оптимального решения, которое появится после вычислений, отведены ячейки B8:В9. Ячейка В11 зарезервирована для вычисления значения целевой функции, ячейки F3:F5 – для левых частей ограничений. В режиме отображения формул заполненная таблица имеет вид: Поскольку ячейки оптимального решения B8:В9 не содержат данных, значение расхода сырья и целевой функции пока 0. Выбираем команду «Поиск решения» и в появившееся диалоговое окно вводим данные, при этом ограничения удобнее задавать в виде диапазонов: Нажимаем ОК, затем “Выполнить”. После нажатия кнопки «Выполнить» открывается окно «Результаты поиска решения», которое сообщает, что решение найдено. Сохраняем его:

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