Методы нелинейной и дискретной оптимизации

Аналогичным образом построим области решения двух других неравенств

200x1+100x2-60 000=0; x1 = 0, x2 = 600

x1 = 300, x2 = 0 (на рисунке прямая II);

200x1+100x2-60 000<0 при x1 = x2 = 0, -60 000<0 выполняется, берется левая полуплоскость.

30x1+60х2-21 000=0 x1 = 0, x2 = 350

x1 = 700, x2 = 0 (на рисунке прямая III);

30x1+60x2-21 000<0 при x1 = x2 = 0, -21 000<0 выполняется, берется нижняя полуплоскость.

Заштрихуем общую область  для всех неравенств. Обозначим вершины  области латинскими буквами и  определим их координаты, решая систему  уравнений двух пересекающихся соответствующих  прямых. Например, определим координаты точки B, являющейся точкой пересечения первой и третьей прямой:

x1+x2-400=0, x1 = 100; x2 = 300

30x1+60х2 - 21 000=0.

Вычислим значение целевой  функции в этой точке:

f(Х)= 90x1+120x2=90∙100 + 120∙300 = 45000.

Аналогично поступим для  других точек, являющихся вершинами  области АВСDO, представляющей собой область допустимых решений рассматриваемой ЗЛП. Координаты этих вершин имеют следующие значения: т. А(0;350), т. В(100;300), т.С(200;200), т. D(300;0), т. О(0;0).

Этап 2. Приравняем целевую функцию постоянной величине а: 90x1+120x2 = а.

Это уравнение является множеством точек, в котором целевая функция принимает значение, равное а. Меняя значение а, получим семейство параллельных прямых, каждая из которых называется линией уровня. Пусть а=0, вычислим координаты двух точек, удовлетворяющих соответствующему уравнению90x1+120x2 = 0. В качестве одной из этих точек удобно взять точку О(0;0), а так как при x1 = 4, x2 = -3 то в качестве второй точки возьмем точку G(4;-3).

Через эти две точки  проведем линию уровня f(Х)= 90x1+120x2 = 0.

Этап 3. Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными функции f(X), т.е. ОN =(90;120) Чтобы построить этот вектор, нужно соединить точку (90;120) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации — в противоположном направлении.

В нашем случае движение линии уровня будем осуществлять до ее пересечения с точкой В, далее  она выходит из области допустимых решений. Следовательно, именно в этой точке достигается максимум целевой функции. Отсюда легко записать решение исходной ЗЛП: max f(Х) =45000 и достигается при x1 = 100, x2=300.

Следовательно, чтобы получить максимальную прибыль, фермер должен засеять 100 га земли кукурузой, 300 га – соей. При этом он получит 45 тыс. ден. ед. при реализации зерна по договору.

Если поставить задачу минимизации функции f(Х) = 90x1+120x2 при тех же ограничениях, линию уровня необходимо смещать параллельно самой себе в направлении, противоположном вектору-градиенту. В нашем случае минимум функции будет в точке О (0;0). Это означает, что фермер не получит ни чего, если не засеет поле зерновыми культурами.

 

 

 

 

 

 

 

 

 

3.4. Торговая компания собирается приобрести новый товар – комплекты постельного белья. Ожидаемая потребность – 800 единиц в месяц. Товар можно приобрести у поставщика. Стоимость заказа – 150 руб., годовая стоимость хранения единицы товара –6 руб. Доставка товара осуществляется в течение двух дней. Компания работает 300 дней в году.

Рассчитайте объем заказа, минимизирующий общие годовые расходы  компании. Определите:

а) годовые расходы на хранение запасов;

б) период поставок;

в) точку заказа.

Решение. Параметры работы торговой компании: V=800 единиц в месяц, К=150 руб.. h=6 руб., t=2.

Узнаем М=800*12=9600 единиц в год.

1. Найдем оптимальный объем заказываемой партии , эта формула называется формулой Уилсона.

== 692,82 комплекты постельного белья нужно заказывать в одну партию.

2. Найдем годовые издержки хранения запасов:  
   

Z= 150*9600/693+6*693/2=4156 руб./год.

3. Найдем период доставки:

Т(опт)=Q/М= 693ед/9600ед в год=0,072 года, 0,072*300дней= 21,622 дня.

4. Найдем точку заказа Н=М* t/кол-во дней в году=9600*2/300=64 комплекта постельного белья.

Решение задачи в Excel

Рис. 2.

 

Рис.  3.

Рис. 4.

 

Рис. 5.

 

Ответ:

Объем заказа 693 комплекта постельного белья.

а) годовые расходы на хранение запасов 4156 руб./год;

б) период поставок – 22 дня;

в) точку заказа 64 комплекта постельного белья.

 

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

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

Решение. Рассчитаем μ=1/Tоб=1/7/60==8,57, затем рассчитаем нагрузку на систему α = λ / μ = 8/8,57=0,933

Рис. 6.

Расчёты проведем в Excel. Видно, что СМО загружена не сильно: из двух бухгалтеров занято в среднем М=0,76, а из обращающихся в бухгалтерию людей около Р отказов=18% остаются незагруженными.

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

Рис. 7.

5.4. Статистический анализ показал, что случайная величина Х (длительность обслуживания клиента в парикмахерской) следует показательному закону распределения с параметром, а число клиентов, поступающих в единицу времени (случайная величина Y), – закону Пуассона с параметром λ=1,9 и μ=0,6.

Организуйте датчики псевдослучайных  чисел для целей статистического  моделирования (использования метода Монте-Карло). Получите средствами MS Excel 15 реализаций случайной величины Х  и 15 реализаций случайной величины Y.

Решение. Имитационный эксперимент  проведем с использованием MS Excel.

Табличная имитационная модель двухканальной СМО с отказами

На рисунке представлен  моделирующий алгоритм (табличная имитационная модель) при числе испытаний N=15.

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

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

 

 

 

 

 

Рис. 8.

Пятнадцать реализаций с.в. длительность интервала τ (в часах) между очередными поступлениями  требований $C$4:$Q$4.  Для получения, содержимого ячейки С4 использовать функции = (-1/C1)*LN(B3).

Соответственно, кумулятивным образом (строка 6) на временной оси [0, Т] зафиксировано время Тi  (i=1,2,…,15) поступления требований (в минутах, с округлением).

Для получения реализаций с.в. длительности обслуживания t (в минутах, с округлением) в соответствующую ячейку электронной таблицы (строки 7 и 9) записывается формула =60*(-1/6)*LN(СЛЧИС()).

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

В соответствии со счётчиком  отказов (в ячейках $C$12:$Q$12) зафиксировано 7 отказов,  т.е. статистическая оценка вероятности отказа в данной СМО при N=15 равна (7/15)=0,47.

 

 

 

 

 

 

Литература

1. Федосеев В.В., Гармаш  А.Н., Орлова И.В. Экономико-математические  методы и прикладные модели: учебник  для бакалавров. –3-е изд., перераб.  и доп. – М.: Юрайт, 2012.

2. Гармаш А.Н., Орлова И.В.  Математические методы в управлении: учебное пособие. – М.: Вузовский  учебник, 2012.

3. Ильина М.А., Копылова  Ю.Н., Копылова Н.Т. Методы оптимальных решений. Конспект лекций. Учебно-методичекое пособие. – Барнаул: Изд-во АлтГТУ, 2012.-112 с.