Задачи оптимизации

Задача № 1. Решить графическим методом типовую задачу оптимизации.

Некоторая фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений, а в улучшенный – 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений. Известно, что для некоторого газона требуется по меньшей мере 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Обычный набор стоит 3 ден. ед., а улучшенный – 4 ден. ед. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на максимум и почему?

Решение:

1.  Введем переменные:

– количество обычных наборов;

– количество улучшенных наборов.

2.  Зададим целевую функцию. Задача на минимизацию затрат. Запишем уравнение, описывающее затраты

3.  Ограничения:

Найдем решение сформированной задачи, используя ее геометрическую интерпретацию. Сначала определим область допустимых решений. Для этого в неравенствах системы ограничений знаки неравенств заменим на знаки точных равенств, и найдем соответствующие прямые:

Выразим через

Для построения прямой достаточно двух точек, найдем их координаты:

Эти прямые изображены на рисунке 1. Условие неотрицательности показывает, что искомая область располагается в первой четверти.

Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой – нет. Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка, в противном случае – другая полуплоскость.

Рисунок 1. Графический метод решения

На рисунке 1, область допустимых решений не ограничена и отмечена штрихом. Координаты любой точки, принадлежащей этой области, удовлетворяют данной системе неравенств и условию неотрицательности переменных. Поэтому сформулированная задача будет решена, если мы сможем найти точку, принадлежащую области допустимых решений, в которой целевая функция принимает минимальное значение. Чтобы найти указанную точку, построим вектор и линию уровня, которая перпендикулярна этому вектору.

Так как задача на минимум, то линию уровня будем двигать по направлению вектора. Первая точка касания и будет оптимальным решением. Координаты этой точки и определяют оптимальные количества обычных и улучшенных наборов удобрений, при которых затраты являются минимальными.

В данном примере это точка пересечения прямых I и Следовательно, ее координаты удовлетворяют уравнениям этих прямых

Следовательно, если фирма купит 2 обычных и 2 улучшенных набора удобрений, то минимальные затраты составят

Если данную задачу решать на максимум, то линия уровня будет сдвигаться вправо до бесконечности (так область решений не ограничена). Таким образом, конечного решения не будет.

Задача № 2. Предложить оптимальное управленческое решение в следующих типовых хозяйственных ситуациях.

Металлургическому заводу требуется уголь с содержанием фосфора не более 0,03% и с долей зольных примесей не более 3,25%. Завод закупает три сорта угля , , с известным содержанием примесей. В какой пропорции нужно смешивать исходные продукты , , чтобы смесь удовлетворяла ограничениям на содержание примесей и имела минимальную цену? Содержание примесей и цена исходных продуктов приведены в таблице

Решение:

Введем следующие обозначения: – содержание угля в смеси; – содержание угля в смеси; – содержание угля в смеси. Тогда ограничения примут вид:

Целевая функция задачи:

Таким образом, ЭММ задачи имеет вид:

Решим данную задачу симплекс-методом. Преобразуем исходную модель. В ограничения типа добавим дополнительные переменные . В равенство добавим искусственную переменную Модель задачи будет выглядеть так:

При условиях:

Заполним первую симплекс-таблицу.

В среди оценок есть положительные значения, следовательно, план не является оптимальным. Среди значений находим наибольшее , столбец выбираем в качестве ведущего. Для положительных элементов ведущего столбца находим наименьшее из симплексных отношений – ведущая строка. Элемент 1 на пересечении ведущего столбца и ведущей строки – разрешающий элемент. После перехода к следующей симплексной таблице, в базисном плане отсутствует искусственная переменная.

В среди оценок есть положительные значения, следовательно, план не является оптимальным. Среди значений находим наибольшее , столбец выбираем в качестве ведущего. Для положительных элементов ведущего столбца находим наименьшее из симплексных отношений – ведущая строка. Элемент 1 на пересечении ведущего столбца и ведущей строки – разрешающий элемент. Переходим к следующей симплексной таблице.

В среди оценок есть положительное значение, следовательно, план не является оптимальным. Столбец выбираем в качестве ведущего. Для положительных элементов ведущего столбца находим наименьшее из симплексных отношений – ведущая строка. Элемент 0,06 на пересечении ведущего столбца и ведущей строки – разрешающий элемент. При переходе к следующей симплексной таблице, получаем оптимальное решение.

В среди оценок нет отрицательных, следовательно, план является оптимальным.

Полученное оптимальное решение означает, что для получения 1 т угля необходимо взять т первого компонента, т второго, т третьего. При этом его цена будет минимальной и составит Руб.

Задача № 3. Провести моделирование и решить специальную задачу линейного программирования.

Компания, занимающаяся ремонтом автомобильных дорог, в следующем месяце будет проводить ремонтные работы на пяти участках автодорог. Песок на участки ремонтных работ может доставляться из трех карьеров, месячные объемы предложений по карьерам известны. Из планов производства ремонтных работ известны месячные объемы потребностей по участкам работ. Имеются экономические оценки транспортных затрат (в у. е.) на перевозку 1тонны песка с карьеров на ремонтные участки.

Числовые данные для решения содержатся ниже в Матрице планирования. Требуется:

1) Предложить план перевозок песка на участки ремонта автодорог, который обеспечивает минимальные совокупные транспортные издержки.

2) Что произойдет с оптимальным планом, если изменятся условия перевозок: а) появится запрет на перевозки от первого карьера до второго участка работ?; б) по этой коммуникации будет ограничен объем перевозок 3 тоннами?

Матрица планирования:

Участки работ

Карьеры

Предложение

4

2

3

4

1

60

2

4

3

5

6

90

6

5

4

6

2

140

Потребности

40

30

90

80

50

290

290

Решение:

Суммарные объемы предложений по карьерам равны суммарным объемам потребностей по участкам работ, т. е. выполняется условие общего баланса Следовательно, данная задача закрытого типа.

Построим начальный базисный план Методом минимальной стоимости. Назначение перевозок начинаем с клетки (1,5), имеющей минимальную стоимость перевозки (1). В клетку (1,5) записываем наименьшее из значений и и исключаем из дальнейшего рассмотрения пятый участок. Корректируем предложение первого карьера на величину

Следующая поставка осуществляется от первого карьера второму участку. В клетку (1,2) назначаем перевозку исключаем из дальнейшего рассмотрения первый карьер. Корректируем потребности второго участка С оставшейся матрицей поступаем аналогично предыдущему:

План перевозок, построенный методом минимальной стоимости:

Построенный начальный план перевозок является невырожденным, так как число назначенных перевозок равно Определим полную стоимость перевозок по найденному опорному плану:

Определим оптимальность полученного плана. С помощью Метода потенциалов вычислим потенциалы строк и столбцов по стоимости перевозок в загруженных клетках. Если известен , то если известен , то Положим, например, Тогда будут вычислены и остальные потенциалы строк и столбцов.

Для незагруженных клеток вычислим величины превышения стоимости

Полученный план не оптимален. Среди оценок имеются отрицательные значения. Потенциальной является клетка . От клетки строим замкнутый контур: Начиная с клетки разметим вершины контура попеременно знаками плюс «+», минус «-», обходя замкнутый контур в любом направлении. Из клеток, помеченных знаком «-», выбираем наименьшее значение объема перевозки Сформируем новый улучшенный план: на 20 увеличим перевозки в клетках, помеченных знаком «+», и уменьшим в клетках, помеченных знаком «-».

Определим полную стоимость перевозок по новому плану

Вычислим потенциалы и величины превышения стоимости для незагруженных клеток:

Полученный план не оптимален. Среди оценок имеется отрицательное значение. Потенциальной является клетка . От клетки строим замкнутый контур: Выбираем наименьшее значение объема перевозки Сформируем новый улучшенный план: на 30 увеличим перевозки в клетках, помеченных знаком «+», и уменьшим в клетках, помеченных знаком «-».

Определим полную стоимость перевозок по новому плану

Вычислим потенциалы и величины превышения стоимости для незагруженных клеток:

Характеристики свободных клеток не отрицательны, следовательно, текущий план оптимален.

Выясним, что произойдет с оптимальным планом, если появится запрет на перевозки от первого карьера до второго участка работ. В этом случае, будем считать, что транспортные затраты на перевозку от первого карьера до второго участка работ бесконечно большая . Составим начальный план методом минимальной стоимости в столбце.

Построенный начальный план перевозок является невырожденным, так как число назначенных перевозок равно Определим полную стоимость перевозок по найденному опорному плану:

Определим оптимальность полученного плана с помощью Метода потенциалов.

Для незагруженных клеток вычислим величины превышения стоимости

Полученный план не оптимален. Среди оценок имеется отрицательное значение. Потенциальной является клетка . От клетки строим замкнутый контур: Выбираем наименьшее значение объема перевозки Сформируем новый улучшенный план: на 60 увеличим перевозки в клетках, помеченных знаком «+», и уменьшим в клетках, помеченных знаком «-».

Определим полную стоимость перевозок по новому плану

Для незагруженных клеток вычислим величины превышения стоимости

Характеристики свободных клеток не отрицательны, следовательно, текущий план оптимален. Таким образом, при запрете на перевозку с первого карьера на второй участок, транспортные расходы вырастут на

Выясним, что произойдет с оптимальным планом, если перевозка от первого карьера до второго участка работ будет ограничена объемом 3 тонны. Составим начальный план произвольным образом, учитывая данное ограничение.

Построенный начальный план перевозок является невырожденным, так как число базисных клеток (без ограничений на перевозку) равно Определим полную стоимость перевозок по найденному опорному плану:

Определим оптимальность полученного плана с помощью Метода потенциалов.

Для незагруженных клеток вычислим величины превышения стоимости

Характеристики свободных клеток не отрицательны, следовательно, текущий план оптимален. Таким образом, при ограничении на перевозку с первого карьера на второй участок тремя тоннами, транспортные расходы вырастут на

Задача № 4. Рассчитать характеристики системы массового обслуживания. Поток требований является простейшим (пуассоновским), а продолжительность обслуживания распределена по экспоненциальному закону.

Поток клиентов, прибывающих в банк, имеет интенсивность 9 клиентов в час. Продолжительность обслуживания одного клиента в среднем длится 8 мин. Сколько операционистов должно обслуживать клиентуру, чтобы среднее число клиентов, ожидающих обслуживания, не превышало 3?

Решение:

Данная задача относится к многоканальным СМО с ограниченной длиной очереди.

Имеем

Тогда интенсивность обслуживания равна

Интенсивность нагрузки равна

Пусть количество операционистов тогда вероятность состояния :

Пусть количество операционистов тогда вероятность состояния :

Вычислим среднее число клиентов в очереди:

Таким образом, чтобы среднее число клиентов, ожидающих обслуживания, не превышало 3, достаточно двух операционистов.

Задача № 5. Построить диаграмму Ганта и найти критический путь задачи управления проектом организации выступления хора.

Решение:

Построим диаграмму Ганта с помощью Project Office и найдем его критический путь.

Таким образом, критический путь состоит из следующих работ:

Продолжительность пути составляет

Яндекс.Метрика