Типовые задачи оптимизации и их экономико-математические модели

Постановка задач оптимизации В общем виде задача оптимизации, или задача определения экстремума, ставится следующим образом.

Пусть заданы:

функция f (X), определенная на множестве RN ;

множество D RN.

Найти точку Y = (y1, y2,…, yN) D, в которой функция f (X) достигает экстремального (минимального или максимального) значения, т. е. f (X) = extr f (X) и Y D.

Функция f (X) называется целевой функцией, переменные X — управляемыми переменными, D — допустимым множеством и любой набор значений Y управляемых переменных, принадлежащий D (Y D), — допустимым решением задачи оптимизации [3].

Понятно, что искомая точка Y, в которой f (X) достигает своего экстремума, должна принадлежать пересечению области определения O функции f (X) и допустимого множества D (Y O D). Если множества O и D совпадают со всем пространством RN (O = D = RN), то такая задача называется задачей на безусловный экстремум. Если хотя бы одно из множеств O или D является собственным подмножеством пространства RN (O RN, D RN) или множества O и D пересекаются (O D), то такая задача называется задачей на условный экстремум, в противном случае (O D =) точка экстремума Y не существует. Подчеркнем один частный случай: если множества O и D пересекаются в одной точке Y, то эта точка Y является единственным допустимым решением.

Методы линейного программирования.

Оптимизационная задача — это экономико-математическая задача, которая состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений.

В самом общем виде задача математически записывается так:

U = f (X) max; X W,.

Где X = (Х1, Х2,…, Хn);

W — область допустимых значений переменных Х1, Х2,…, Хn;

f (X) — целевая функция [3].

Для того, чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение, т. е. указать X () W такое, что f (X ()) f (X), при любом X W, или для случая минимизации — что f (X ())? f (X), при любом X W.

Оптимизационная задача является неразрешимой, если она не имеет оптимального решения. В частности, задача максимизации будет неразрешима, если целевая функция f (X) не ограничена сверху на допустимом множестве W.

Методы решения оптимизационных задач зависят как от вида целевой функции f (X), так и от строения допустимого множества W. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.

В математическом программировании принято выделять следующие основные задачи в зависимости от вида целевой функции f (X) и от области W:

• · задачи линейного программирования, если f (X) и W линейны;
• · задачи целочисленного программирования, если ставится условие целочисленности переменных Х1, Х2,…, Хn;
• · задачи нелинейного программирования, если форма f (X) носит нелинейный характер.

Задачи линейного программирования.

Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:

f (X) = СjXj max (min);

При этом система линейных уравнений и неравенств, определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f (X) называется целевой функцией или критерием оптимальности.

Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалентна минимизации той же функции, взятой с противоположным знаком, и наоборот [4].

Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

• 1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
• 2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;
• 3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
• 4) если некоторая переменная Хk не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными:

Постановка задачи линейного программирования Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), но n потребителям этих ресурсов [3].

На автомобильном транспорте часто встречаются следующие задачи, относящиеся к транспортным:

• · прикрепление потребителей ресурса к производителям;
• · привязка пунктов отправления к пунктам назначения;
• · взаимная привязка грузопотоков прямого и обратного направлений;
• · задачи оптимальной загрузки промышленного оборудования;
• · оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями.

Транспортным задачам присущи следующие особенности:

• · распределению подлежат однородные ресурсы;
• · условия задачи описываются только уравнениями;
• · все переменные выражаются в одинаковых единицах измерения;
• · во всех уравнениях коэффициенты при неизвестных равны единице;
• · каждая неизвестная встречается только в двух уравнениях системы ограничений.

Транспортные задачи могут решаться симплекс-методом.

Симплекс-метод решения задач линейного программирования.

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

Реализация алгоритма симплекс-метода.

• 1. Записать задачу в канонической форме: заменить все ограничения-неравенства с положительной правой;
• 2. Разделить переменные на базисные и свободные: перенести свободные переменные в правую часть ограничений-неравенств.
• 3. Выразить базисные переменные через свободные: решить систему линейных уравнений (ограничений-неравенств) — относительно базисных переменных;
• 4. Проверить неотрицательность базисных переменных: убедиться в неотрицательности свободных членов в выражениях для базисных переменных. Если это не так, вернуться к пункту 2, выбирая другой вариант разделения переменных на базисные и свободные.
• 5. Выразить функцию цели через свободные переменные: базисные переменные, входящие в функцию, выразить через свободные переменные;
• 6. Вычислить полученное базисное решение и функцию цели на нем: приравнять к 0 свободные переменные;
• 7. проанализировать формулу функции цели: если все коэффициенты свободных переменных положительны (отрицательны), то найденное базисное решение будет минимально (максимально) и задача считается решенной;
• 8. Определить включаемую в базис и исключаемую из базиса переменные: если не все коэффициенты при свободных переменных в функции цели положительны (отрицательны), то следует выбрать свободную переменную, входящую в функцию цели с максимальным по модулю отрицательным (положительным) коэффициентом, и увеличивать ее до тех пор, пока какая-нибудь из базисных переменных не станет равной 0. Свободную переменную рассматриваем как новую базисную переменную (включаемую в базис), а базисную переменную рассматриваем как новую базисную переменную (исключаемую из базиса);
• 9. Используя новое разделение переменных на базисное и свободное, вернуться к пункту 3 и повторять все этапы до тех пор, пока не будет найдено оптимальное решение [4].

В заключение отметим, что определение оптимального решения распадается на два этапа:

• · нахождение какого-либо допустимого решения с положительным свободным членом;
• · определение оптимального решения, дающего экстрему целевой функции.

Задание 2

Решить графическим методом типовую задачу оптимизации. Осуществить проверку правильности решения с помощью средств MS Excel (надстройки Поиск решения).

Совхоз для кормления животных использует два вида корма. В дневном рационе животного должно содержаться не менее 6 единиц питательного вещества, А и не менее 12 единиц питательного вещества В. Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальными? Использовать данные таблицы:

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

Решение:

Экономико-математическая модель задачи Переменные: х1 — 1 вид корма; х2 — 2 вид корма.

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

F (Х) = 0,2×1+0,3×2>min.

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

Графический метод.

Первое ограничение (по питательному веществу А) имеет вид 2×1+х2?6. Найдем пересечение с осями координат. Прямая 2×1+х2=6 проходит через точки (3;0) и (0;6). Второе ограничение (по питательному веществу В) имеет вид 2×1+4×2?12. Прямая 2×1+4×2=12 проходит через точки (6;0) и (0;3).

Для определения направления движения к оптимуму построим вектор-градиент, координаты которого являются частными производными целевой функции: (0,2;0,3) [2].

Для нахождения координат точки максимума решаем систему.

3х2=6 > х2=2.

Подставляем в систему и получаем, что х1=2.

Ответ: (2;2).

F (min)=0,2*2+0,3*2=0,4+0,6=1.

Проверка правильности решения с помощью средств MS Excel.

1.

Введение

исходных данных (рис.1).

Рис. 1. данные введены.

2. Введем зависимость для целевой функции (рис.2).

Рис. 2. введена зависимость для целевой функции.

3. Введем зависимости для ограничений (рис.3).

Рис. 3. Введены зависимости для ограничений.

4. Запустим команду поиск решения (рис.4).

Рис. 4. Введены все условия задачи.

• 5. Найдем решение. После нажатия кнопки Выполнить запускается процесс решения задачи (рис.5).
• 6.

Рис. 5. Решение получено.

Ответ: Чтобы затраты были минимальными необходимо расходовать 2 единицы первого корма и 2 единицы второго корма. Если задачу решать на максимум то задача не имеет решения, так как целевая функция не ограничена сверху.

Задание 3

Рассчитать параметры моделей экономически выгодных размеров заказываемых партий.

Цветочный магазин использует 600 глиняных цветочных горшков в месяц. Годовая стоимость хранения одного горшка составляет 1 руб. 50 коп., стоимость одного заказа 150 руб. Магазин работает 365 дней в году. Доставка заказа занимает 1 день. Определите экономичный объем заказа, годовые расходы на хранение запасов, период поставок, точку заказа.

Решение:

Оптимальный размер заказа (Н=Th — удельные издержки хранения за период, h — в единицу времени).

.

Число заказов в течение года.

Поскольку средне суточный спрос равен 7200/365=20, точка восстановления запаса (уровень запасов, при котором делается новый заказ) составит 20*1=20 [1].

Минимальные издержки заказа и хранения.

Задание 4.

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

В бухгалтерии организации в определенные дни непосредственно с сотрудниками работают два бухгалтера. Если сотрудник заходит в бухгалтерию для оформления документов (доверенностей, авансовых отчетов и пр.), когда оба бухгалтера заняты обслуживанием ранее обратившихся работников, то он уходит из бухгалтерии, не ожидая обслуживания. Статистический анализ показал, что среднее число сотрудников, обращающихся в бухгалтерию в течение часа, равно; среднее время, которое затрачивает бухгалтер на оформление документа, равно Тср мин. (значения и Тср по вариантам даны ниже в таблице).

Оценить основные характеристики работы данной бухгалтерии как СМО с отказами (указание руководства не допускать непроизводительных потерь рабочего времени!). Сколько бухгалтеров должно работать в бухгалтерии в отведенные дни с сотрудниками, чтобы вероятность обслуживания сотрудников была выше 85%?

Решение:

1. Рассчитаем вероятность отказа в обслуживании по формуле:

Ротк=Рn=Р0 ,.

P0=;

— нагрузка на систему[1].

· Расчет нагрузки на систему (рис.6);

Рис. 6. Расчет нагрузки на систему.

· Расчет вероятности Р0 ячейке С5 без степени -1, для 1 числа канала (рис.7);

Рис. 7. Расчет вероятности.

Рассчитаем вероятность Р0 для остальных каналов меняя в формуле 1 на ячейку С5, и скопируем для ячеек С6-С14 (рис.8).

• · Рассчитаем вероятность Р0 в ячейке D5 ставя ячейку С5 в степень -1, и скопируем формулу в ячейки D6-D14 (рис.9);
• · Рассчитаем вероятность Ротк в ячейке Е5, и скопируем формулу в ячейки Е6-Е14 (рис.10).

Рис. 8. Расчет вероятности Р0.

Рис. 9. Расчет вероятности Р0.

Рис. 10. Расчет вероятности отказа в обслуживании.

2. Относительная пропускная способность В, т. е. вероятность того, что заявка будет обслужена (рис.11),.

Рис. 11. Расчет вероятности обслуживания заявки.

3. Абсолютная пропускная способность, А получим, умножая интенсивность потока заявок на В (рис.12):

.

Рис. 12. Расчет абсолютной пропускной способности.

4. Среднее число занятых каналов (рис.13);

.

Рис. 13. Расчет среднего числа занятых каналов.

Рис. 14. График вероятности отказа в обслуживании.

Рис. 15.Расчет характеристик системы массового обслуживания.

Из графика на рис. 14 видно, что минимальное число каналов обслуживания, при котором вероятность обслуживания работника будет выше 85%, равно n=3.

Задание 5. Организуйте датчики псевдослучайных чисел для целей статистического моделирования (для использования метода Монте-Карло).

Статистический анализ показал, что случайная величина Х длительности обслуживания клиента в парикмахерской следует показательному закону распределения с параметром м, а число поступающих в единицу времени клиентов (с.в. У) — закону Пуассона с параметром. Значения параметров и м повариантно даны ниже в таблице.

Получите средствами MS Excel 15 реализаций с.в. Х и 15 реализаций с.в. У.

Решение:

Для получение случайных чисел с показательным законом распределения использовано соотношение.

1. Получим случайные числа от 0 до 1 в ячейках $С$ 3:$Q$Q. При использовании функции =СЛЧИС () (рис.16).

Рис. 15. Случайные данные.

2. Расчитаем время между очередными поступлениями в ячейках $C$ 4:$Q$ 4. Для их получения используем следующие функцию (рис.16).

Рис. 16. Расчет времени между поступлениями.

3. Расчитаем время обслуживания округленное (в строках 7 и 9) с помощью формулы (рис. 17 и рис.18).

Рис. 17. Расчет времени обслуживании по работнику 1.

Рис. 18. Расчет времени обслуживания по работнику 2.

4. Расчитаем время окончания обслуживания работника 1 строчку 6 складываем со строкой 7 (рис.19) и работника 2 строку 6 складываем со строкой 9 (рис.20).

Рис. 19. Расчет окончания обслуживания первого работника.

Рис. 20. Расчет окончания обслуживания второго работника.

5. Далее последовательно сравниваются время окончания обслуживания каналами (строки 8 и 10) и время поступления требований (строка 6); соответственно, в счетчике отказов (строка 11) фиксируется 0 (требование принято к обслуживанию) или 1 (требование отказано в обслуживании) (рис.21)[1].

Рис. 21. Табличное представление имитации.

В соответствии со счетчиком отказов (в ячейках $C$ 11:$Q$ 11) зафиксировано 8 отказов, т. е. статистическая оценка вероятности отказав данной системы массового обслуживания при N=15 равна (8/15)=0,53.