При откорме животных используется два вида корма 1 и 2
Вариант № 2.
Задача № 1. Решить графическим методом типовую задачу оптимизации.
Совхоз для кормления животных использует два вида корма. В дневном рационе животного должно содержаться не менее 6 единиц питательного вещества и не менее 12 единиц питательного вещества . Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальными? Использовать данные таблицы:
Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на максимум и почему?
Решение:
1. Введем переменные:
– количество корма 1;
– количество корма 2.
2. Зададим целевую функцию. Задача на минимизацию затрат. Запишем уравнение, описывающее затраты
3. Ограничения:
Найдем решение сформированной задачи, используя ее геометрическую интерпретацию. Сначала определим область допустимых решений. Для этого в неравенствах системы ограничений знаки неравенств заменим на знаки точных равенств, и найдем соответствующие прямые:
Выразим через
Для построения прямой достаточно двух точек, найдем их координаты:
Эти прямые изображены на рисунке 1. Условие неотрицательности показывает, что искомая область располагается в первой четверти.
Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой – нет. Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка, в противном случае – другая полуплоскость.
Рисунок 1. Графический метод решения
На рисунке 1, область допустимых решений не ограничена и отмечена штрихом. Координаты любой точки, принадлежащей этой области, удовлетворяют данной системе неравенств и условию неотрицательности переменных. Поэтому сформулированная задача будет решена, если мы сможем найти точку, принадлежащую области допустимых решений, в которой целевая функция принимает минимальное значение. Чтобы найти указанную точку, построим вектор и линию уровня, которая перпендикулярна этому вектору.
Так как задача на минимум, то линию уровня будем двигать по направлению вектора. Первая точка касания и будет оптимальным решением. Координаты этой точки и определяют оптимальные количества кормов и , при которых ежедневные затраты на кормление одного животного являются минимальными.
В данном примере это точка пересечения прямых I и Следовательно, ее координаты удовлетворяют уравнениям этих прямых
Следовательно, если совхоз для кормления животных будет использовать 2 кг корма 1 и 2 кг корма 2, то минимальные затраты составят
Если данную задачу решать на максимум, то линия уровня будет сдвигаться вправо до бесконечности (так область решений не ограничена). Таким образом, конечного решения не будет.
Задача № 2. Предложить оптимальное управленческое решение в следующих типовых хозяйственных ситуациях.
В обработку поступили две партии досок для изготовления комплектов из трех деталей (треугольные каркасы настилов на стройплощадку), причем первая партия содержит 52 доски длиной по 6,5 м каждая, вторая содержит 200 досок длиной по 4 м каждая. Каждый комплект состоит из двух деталей по 2 м каждая и одной детали в 1,25 м.
Ставится задача поиска рационального варианта раскроя поступившего в обработку материала.
Решение:
Критерием оптимальности в данной задаче будет максимум выпуска комплектной продукции. Построим возможные способы раскроя исходного материала:
Введем необходимые обозначения: – число досок из партии , которое следует раскроить способом. Рассмотрим соотношения:
Обозначим через – минимальное из этих соотношений (это и будет количество комплектной продукции). Следовательно, экономико-математическая модель примет вид:
– Целые неотрицательные. Для удобства записи заменим двухиндексные переменные на одноиндексные переменные так как это показано в таблице раскроя Тогда ЭММ задачи примет вид:
При ограничениях:
Реализуя приведенную модель в любом пакете прикладных программ, получим решение:
Оптимальные значения остальных переменных равны нулю. Следовательно, в данной хозяйственной ситуации максимальное количество наборов, равное 215 шт. можно изготовить и реализовать, если:
– раскроить каждую из 15 досок длиной 6,5 м на 2 детали по 2 м и 2 детали по 1,25 м;
– раскроить каждую из 37 досок длиной 6,5 м на 5 деталей по 1,25 м;
– раскроить каждую из 200 досок длиной 4 м на 2 детали по 2 м. В этом случае будет получена максимальная выручка.
Задача № 3. Провести моделирование и решить специальную задачу линейного программирования.
Компания, занимающаяся ремонтом автомобильных дорог, в следующем месяце будет проводить ремонтные работы на пяти участках автодорог. Песок на участки ремонтных работ может доставляться из трех карьеров, месячные объемы предложений по карьерам известны. Из планов производства ремонтных работ известны месячные объемы потребностей по участкам работ. Имеются экономические оценки транспортных затрат (в у. е.) на перевозку 1тонны песка с карьеров на ремонтные участки.
Числовые данные для решения содержатся ниже в Матрице планирования. Требуется:
1) Предложить план перевозок песка на участки ремонта автодорог, который обеспечивает минимальные совокупные транспортные издержки.
2) Что произойдет с оптимальным планом, если изменятся условия перевозок: а) появится запрет на перевозки от первого карьера до второго участка работ?; б) по этой коммуникации будет ограничен объем перевозок 3 тоннами?
Матрица планирования:
Решение:
Суммарные объемы предложений по карьерам равны суммарным объемам потребностей по участкам работ, т. е. выполняется условие общего баланса Следовательно, данная задача закрытого типа.
Построим начальный базисный план Методом минимальной стоимости. Назначение перевозок начинаем с клетки (1,5), имеющей минимальную стоимость перевозки (1). В клетку (1,5) записываем наименьшее из значений и и исключаем из дальнейшего рассмотрения пятый участок. Корректируем предложение первого карьера на величину
Следующая поставка осуществляется от второго карьера третьему участку. В клетку (2,3) назначаем перевозку исключаем из дальнейшего рассмотрения третий участок. Корректируем предложение второго карьера С оставшейся матрицей поступаем аналогично предыдущему:
План перевозок, построенный методом минимальной стоимости:
Построенный начальный план перевозок является вырожденным, так как число назначенных перевозок меньше В одну из свободных клеток поставим ноль. Определим полную стоимость перевозок по найденному опорному плану:
Определим оптимальность полученного плана. С помощью Метода потенциалов вычислим потенциалы строк и столбцов по стоимости перевозок в загруженных клетках. Если известен , то если известен , то Положим, например, Тогда будут вычислены и остальные потенциалы строк и столбцов.
Для незагруженных клеток вычислим величины превышения стоимости
Полученный план не оптимален. Среди оценок имеется отрицательное значение. Потенциальной является клетка . От клетки строим замкнутый контур: Начиная с клетки разметим вершины контура попеременно знаками плюс «+», минус «-», обходя замкнутый контур в любом направлении. Из клеток, помеченных знаком «-», выбираем наименьшее значение объема перевозки Сформируем новый улучшенный план: на 100 увеличим перевозки в клетках, помеченных знаком «+», и уменьшим в клетках, помеченных знаком «-».
Определим полную стоимость перевозок по новому плану
Вычислим потенциалы и величины превышения стоимости для незагруженных клеток:
Полученный план не оптимален. Среди оценок имеется отрицательное значение. Потенциальной является клетка . От клетки строим замкнутый контур: Выбираем наименьшее значение объема перевозки Сформируем новый улучшенный план: на 0 увеличим перевозки в клетках, помеченных знаком «+», и уменьшим в клетках, помеченных знаком «-».
Определим полную стоимость перевозок по новому плану
Вычислим потенциалы и величины превышения стоимости для незагруженных клеток:
Характеристики свободных клеток не отрицательны, следовательно, текущий план оптимален.
Выясним, что произойдет с оптимальным планом, если появится запрет на перевозки от первого карьера до второго участка работ. В этом случае, будем считать, что транспортные затраты на перевозку от первого карьера до второго участка работ бесконечно большая . Составим начальный план методом минимальной стоимости в столбце.
Построенный начальный план перевозок является невырожденным, так как число назначенных перевозок равно Определим полную стоимость перевозок по найденному опорному плану:
Определим оптимальность полученного плана с помощью Метода потенциалов.
Для незагруженных клеток вычислим величины превышения стоимости
Характеристики свободных клеток не отрицательны, следовательно, текущий план оптимален. Таким образом, при запрете на перевозку с первого карьера на второй участок, транспортные расходы вырастут на
Выясним, что произойдет с оптимальным планом, если перевозка от первого карьера до второго участка работ будет ограничена объемом 3 тонны. Составим начальный план произвольным образом, учитывая данное ограничение.
Построенный начальный план перевозок является невырожденным, так как число базисных клеток (без ограничений на перевозку) равно Определим полную стоимость перевозок по найденному опорному плану:
Определим оптимальность полученного плана с помощью Метода потенциалов.
Для незагруженных клеток вычислим величины превышения стоимости
Полученный план не оптимален. Среди оценок имеются отрицательные значения. Потенциальной является клетка . От клетки строим замкнутый контур: Выбираем наименьшее значение объема перевозки Сформируем новый улучшенный план.
Определим полную стоимость перевозок по найденному опорному плану:
Для незагруженных клеток вычислим величины превышения стоимости
Полученный план не оптимален. Среди оценок имеются отрицательные значения. Потенциальной является клетка . От клетки строим замкнутый контур: Выбираем наименьшее значение объема перевозки Сформируем новый улучшенный план.
Определим полную стоимость перевозок по найденному опорному плану:
Для незагруженных клеток вычислим величины превышения стоимости
Характеристики свободных клеток не отрицательны (кроме клетки с ограничением), следовательно, текущий план оптимален. Таким образом, при ограничении на перевозку с первого карьера на второй участок тремя тоннами, транспортные расходы вырастут на
Задача № 4. Рассчитать характеристики системы массового обслуживания. Поток требований является простейшим (пуассоновским), а продолжительность обслуживания распределена по экспоненциальному закону.
На строительном участке в инструментальной мастерской работают 3 мастера. Если рабочий заходит в мастерскую, когда все мастера заняты обслуживанием ранее обратившихся работников, то он не уходит из мастерской и ожидает обслуживания. Статистика показала, что среднее число рабочих, обращающихся в мастерскую в течение часа, равно 4, среднее время, которое затрачивает мастер на заточку или ремонт инструмента, равно 10 мин. Рассчитайте основные характеристики работы данной мастерской как СМО с ожиданием.
Решение:
Имеем
Тогда интенсивность обслуживания равна
Интенсивность нагрузки равна
Поскольку
Очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. Находим вероятности состояний:
Число занятых каналов найдем, разделив абсолютную пропускную способность СМО на интенсивность обслуживания
Вероятность отсутствия очереди будет:
Среднее число рабочих в очереди:
Среднее число рабочих в мастерской:
Среднее время ожидания в очереди:
Среднее время пребывания рабочего в мастерской:
Источник
Для решения задач линейного программирования в Excel используют команду Поиск решения.
В офисах до 2003 включительно эта команда находится в меню Сервис.
Если ее там нет, нужно выполнить команду Сервис→Надстройки…
В офисе 2007 и выше команда Поиск решения находится в меню Данные.
Если ее там нет, нужно сделать следующее.
В Настройке панели быстрого доступа выбрать Другие команды.
Появится окно Параметры Excel. Здесь выбрать пункт Надстройки и щелкнуть по кнопке Перейти.
Далее установить Поиск решения.
ЗАДАЧА 1. При откорме животных каждое животное ежедневно должно получить не менее 60ед питательного вещества А, и не менее 50ед вещества В и не менее 12ед вещества С. Указанные питательные вещества содержат три вида корма. Содержание единиц питательных веществ в 1 кг каждого из видов приведено в таблице:
| Питательные вещества | Количество единиц питательных веществ в 1кг корма вида | |
| I | II | III |
| А | ||
| В | ||
| С |
Составить дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах, если цена 1кг I вида составляет 9 грн., норма II вида – 12 грн, и норма III вида – 10 грн.
Постановка задачи.
Пусть – количество кормов каждого вида в кг.
Ограничения:
Функция цели:
Решение задачи:
Введем исходные данные в рабочий лист.
Пусть значения хранятся в ячейки B8:D8.
Значение функции цели F в ячейке
F8 = СУММПРОИЗВ(B8:D8;B6:D6).
Ограничения соответственно:
E3 = СУММПРОИЗВ($B$8:$D$8;B3:D3)
E4 = СУММПРОИЗВ($B$8:$D$8;B4:D4)
E5 = СУММПРОИЗВ($B$8:$D$8;B5:D5)
Таким образом, было задано условие исходной задачи линейного программирования.
Установим курсор в ячейку F8и выполним команду Сервис®Поиск решения. Появится окно Поиск решения.
В поле Установить целевую функцию должен быть указан адрес ячейки, содержащей целевую функцию. В нашем случае это F8.
Поскольку мы ищем минимум функции, то установим опцию «равной минимальному значению».
В поле Изменяя ячейки необходимо указать адреса ячеек, в которых хранятся неизвестные (искомые) значения. В нашем случае это ячейки B8:D8.
Для добавления ограничений необходимо щелкнуть по кнопке Добавить, появится диалоговое окно Добавить ограничение.
В поле Ссылка на ячейку необходимо ввести адрес ячейки, где хранится ограничение, затем, выбрать знак и ввести значение ограничения в поле Ограничение.
Щелчок по кнопке Добавить позволит вводить очередное ограничение, находясь в окне Добавить ограничение.
Щелчок по кнопке OKозначает ввод очередного ограничения и возврат к диалоговому окну Поиск решения.
В нашем случае окноПоиск решения будет иметь вид:
Щелчок по кнопке Выполнить начнет процесс решения задачи, завершится который появлением диалогового окна:
Щелчок по кнопке OK приведет к появлению в F8 значения целевой функции F, а в B8:D8— значений переменных , при которых целевая функция достигает минимального значения.
Если задача не имеет решения или не верно были заданы исходные данные, в окне Результаты поиска решения может появиться сообщение о том, что решение не найдено.
Итак, назначение основных кнопок и окон диалогового окна Поиск решения:
Поле Установить целевую ячейку –определяет целевую ячейку, значение которой необходимо максимизировать или минимизировать, или сделать равным конкретному значению.
Опции «минимальному значению», «максимальному значению» и «значению», определяют, что необходимо сделать со значением целевой ячейки – максимизировать, минимизировать или приравнять конкретному значению.
ПолеИзменяя ячейки определяет изменяемые ячейки. Изменяемая ячейка – это ячейка, которая может быть изменена в процессе поиска решения для достижения нужного результата в целевой ячейке с удовлетворением заданных ограничений.
Окно Ограничения перечисляет текущие ограничения в данной задаче. Ограничение это условие, которое должно удовлетворять решению. Ограничения перечисляются в виде ячеек или интервалов ячеек, обычно содержащих формулу, которая зависит от одной или нескольких изменяемых ячеек, значения которых должны попадать внутрь определенных границ или удовлетворять равенству.
Кнопки Добавить, Изменить, Удалить позволяют добавить, изменить, удалить ограничение.
Кнопка Выполнить запускает процесс решения определенной задачи.
Кнопка Закрыть закрывает окно диалога, не решая задачи.
Кнопка Сбросить очищает все текущие установки задачи и возвращает все параметры к их значениям по умолчанию.
С помощью решающего блока можно решить множество различных оптимизационных задач с ограничениями любого типа.
1 | 2 |
Источник
Довольно обширный класс задач математического программирования образуют так называемые задачи на составление смесей или задачи на использование заменителей. Задача подобного рода возникает в случае необходимости смешивания различных компонент со сходными свойствами с целью создания смеси, отвечающей определенным требованиям, или при необходимости замены в смеси одних компонент другими. Характерный пример такой задачи — составление наиболее экономичных смесей горючего для двигателей разных типов. Известно, что выпускаемые марки бензина различаются теплотворной способностью, температурой воспламенения, степенью очистки и т.п. Возникает задача составления наиболее дешевой смеси из различных марок бензина при условии, чтобы определенные количественные показатели смеси были выше (или ниже) заранее установленных величин. Аналогичной является задача на составление наиболее дешевой смеси различных сортов угля для нагрева паровых котлов и т.п.
Не менее важными являются задачи составления экономной шихты для выплавки чугуна и стали. Так, для получения легированной стали необходимо использовать шихту определенного химического состава. Многие ингредиенты шихты весьма дорогостоящие, и вместе с тем в ее состав входят малоценные материалы — чугун, лом, отходы с определенным известным содержанием присадок. Возникает задача выбора шихты минимальной стоимости, в состав которой должны входить в заданных количествах необходимые химические вещества.
К задачам на составление смесей относится также определенный тип задач на использование заменителей. Например, проблема замены одних средств производства другими с целью достижения оптимального эффекта производства.
Задачи на смеси приходится решать при определении рациональных норм потребления продуктов питания и в связи с этим при составлении перспективного плана развития пищевой промышленности или при планировании централизованного снабжения продуктами питания детских учреждений, спортивных и оздоровительных лагерей, больниц, войсковых частей и т.д. Встречаются подобные задачи и в сельскохозяйственной практике, например, при выборе оптимального рациона для откорма скота. В простейшей постановке эта задача формулируется следующим образом.
Пусть хозяйство располагает п видами кормов (сено, силос, концентраты и т.д.), каждый из которых содержит в различных пропорциях m видов питательных веществ (белки, кальций, фосфор, витамины и др.). Известно, что в единице корма j-го (j=1,…, n). вида содержится аij единиц i-го питательного вещества (i=1,…, m). Минимальная суточная потребность в i-ом питательном веществе составляет biединиц, себестоимость производства единицы корма j-го вида равна cj, а выделяемый суточный объем ограничен величиной aj. Требуется выбрать рацион — набор и количество кормов — так, чтобы количество каждого питательного вещества было не меньше требуемого, а суммарная стоимость рациона была минимальной.
Построим математическую модель данной задачи.
Обозначим через xj (j=1, …n) количество единиц корма j-го вида, включаемого в суточный рацион. Тогда общее количество i-го питательного вещества, содержащегося в рационе (х1; …; хn), выразится суммой:
.
Эта сумма не должна быть меньше нужного минимума bi по всем видам питательных веществ, что математически выразится следующей системой неравенств:
.
С другой стороны, суточное потребление каждого корма ограничено имеющимися запасами ai. Отсюда дополнительные условия на компоненты рациона: .
Суммарная стоимость кормов, составляющих суточный рацион, определится выражением:
Таким образом, оптимальным рационом будет такой набор (х1; …; хn) кормов, который обращает в минимум линейную функцию f при соблюдении ограничений, а математическая модель задачи о рационе будет иметь вид:
Если учесть обусловленное зоотехническими требованиями определенное соотношение в рационе объемов сочных и грубых кормов, то придется дополнить модель соответствующими ограничениями. Чтобы обеспечить разнообразие рациона, следует иметь в наличии не менее а0j единиц j-го вида корма, а в модель задачи придется включить условия:
.
Иногда приходится учитывать ограничения сверху (величиной ) на потребление некоторых питательных веществ. Тогда необходима модификация одного из условия системы ограничений модели, а именно следует рассматривать ограничения вида:
.
В итоге математическая модель задачи о рационе примет обобщенный вид:
Пример 2.3 Задача о рационе
При откорме каждое животное ежедневно должно получить не менее 60 единиц питательного вещества А, не менее 50 ед. вещества В. Указанные питательные вещества содержат три вида корма. Содержание единиц питательных веществ в 1 кг каждого из видов кормов приведено в таблице:
| Тип вещества | Кол-во единиц питательных веществ в 1 кг корма вида | |
| І | ІІ | ІІІ |
| А | ||
| В |
Составить дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах, если цена 1 кг корма 1 го вида составляет 19 грн., корма 2 го вида – 24 грн., корма 3 го вида – 25 грн.
Построим математическую модель задачи. Пусть Хi – количество корма iго вида, включаемого в дневной рацион животных, i = 1, 2, 3.
Целевая функция задачи выражает суммарные денежные затраты на составление рациона, которые должны быть минимальными:
F = 19X1 + 24X2 + 25X3 ® min
На переменные задачи накладываются ограничения на количественное содержание питательных веществ А и В в дневном рационе животного.
для вещества А: X1 + 3X2 + 4X3 ³ 60,
для вещества В: 2X1 + 4X2 + 2X3 ³ 50.
Левая часть каждого из ограничений формально выражает то количество единиц соответствующего питательного вещества, которое животное фактически получит в результате составления некоторого рациона Х=(Х1, Х2, Х3). Правая же часть того же ограничения – это требуемое количество единиц соответствующего питательного вещества. Учитывая требование условия задачи: животное должно получить необходимое количество единиц питательных веществ, выбираем знак неравенств “³”.
Кроме того, значения переменных Хi, i = 1, 2, 3 , не могут принимать отрицательные значения, т.е. Хi ³ 0, i = 1, 2, 3.
Таким образом, математическая модель исходной задачи будет иметь вид:
Источник