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

Подбор параметра

Инструмент Подбор параметра (вкладка Данныегруппа Работа с данными пиктограммаАнализ “что-если” пунктПодбор параметра) разрешает определить значение довода, удовлетворяющее желаемому значению функции. С его помощью возможно приобретать результаты, каковые тяжело либо нереально взять прямо.

Замечание. Тут и потом клетки, которые содержат формулы выделены фоном (в электронной версии – желтым).

Задача 1. Пускай расчет заработной плата выполняется следующим образом (рис.1-1а). Налогом облагается не вся заработная плат. Сумма обложения меньше дохода на налоговый вычет (1000р) на самого работника и на каждого ребенка. Тут же учитываются вычеты медицинской страховки (2%). Что бы избежать отрицательности суммы обложения, в D3 употребляется функция МАКС(), которая снабжает равенство нулю суммы обложения, если она делается отрицательной. На рис. 1-1а представлены формулы. На рис. 1-1в – итог для штатного работника Ивана. Для него расчет ведется в простом порядке – вводится доход (30000р) и машинально вычисляется итог (26060р).

Сейчас решим обратную задачу. Пускай вы договорились с некоторым исполнителем (Петром) о исполнении разовой работы за 5000 руб. “чистыми” и с Олегом за 500р. Дабы совершить эти выплаты в бухгалтерии направляться выяснить исходную заработную плат до изъятия всех вычетов. Т.е. решить обратную задачу – выяснить малоизвестную исходную заработную плат Петра по известной сумме “на руки”. Приведя к Подбору параметра,зададим (рис.1-1б) доводы: Установить в ячейке:G4 , в новое Значение:5000 , Изменяя значение ячейки: B4 . По окончании нажатия ОK, Excel выдает окно Итог подборапараметра, где отображаются ожидаемые результаты операции. В этом случае совокупности удалось подобрать довод (B4=5663) при котором для Петра итог равен 5000. Потом, в случае если Решениенайдено и пользователь согласен с ними, направляться надавить ОК, в случае если нет – кнопку Отмена (случится возврат к исходным значениям).Подобные действия совершаем для Олега. Тут (маленькая заработная плат) видим, что налог с него не удерживается

При комплекте, клетки в строчках 4 и 5, заполняются формулами, скопированными из строчка 3. Клетки В4 и В5не заполняются в ручную, а вычисляются компьютером.

A B C D E F G Подбор параметра Установить в ячейке:
G4

Значение:

Изменяя значение ячейки:

$B$4
ОК
Отмена
Вычет: Расчет заработной плата Рис. 1-1а Имя Заработная плат Дети Сумма обложения Налог Страховка НА РУКИ Иван =МАКС(B3-B$1*C3;0) =13%*D3 =1%*B3 =B3-E3-F3 Рис. 1-1в Иван Петр Олег Рис.1-1б

Как видим, предложенное средство удобно для разнообразные обратных расчетов.

A B C D Подбор параметра
Продуктовый расчет
Количество сырья: Установить в ячейке: $D$6
Этап Коэфф. утрат Количество утрат Выход Значение:
Изменяя значение ячейки: $C$2
0,05 ? ?
0,11 ? ?
0,02 ? ?
Рис. -2
A B C Подбор параметра
Вклад:
Сложные проценты Установить в ячейке: $C$7
Норма Доход Сумма Значение:
10% ? ? Изменяя значение ячейки: $B$1
12% ? ?
15% ? ?
18% ? ? Рис. -3

Задача 2. Продуктовый расчет. Пускай (рис. 1-2) необходимо по известному количеству применяемого сырья (С2) вычислить выход некоего продукта на каждом этапе обработки (столбец D) и итоговый выход D6. Известны утраты продукта на каждом этапе обработки довольно прошлого этапа (столбец В). Написать формулы расчета. Это была формулировка прямого продуктового расчета. Но довольно часто необходимо вычислить требуемый количество сырья для производства заданного количества продукта (обратный продуктовый расчет). Пускай, мы хотимвыяснить, сколько сырья требуется для выпуска 2000 единиц продукции. Дляэтого в окне Подбор параметра необходимо задать доводы. В следствии мы должны взять количество потребного сырья в 2414. Также, будет произведен перерасчет остатков и потерь на выходе для всех этапов технологического процесса. Введите необходимые формулы. Выполните подбор.

Задача 3. Расчет дохода.В большинстве случаев требуется отыскать сумму на счету от начального вклада (у нас 100 т. руб.) в течение нескольких лет при известной ежегодной норме прибыли. Заполните таблицу рис.1-3 нужными формулами. Поставим задачу обратным образом. Пускай необходимо узнать, сколько средств направляться положить на счет, дабы в конце расчетного периода накопить 500т.руб. (клетка С7). Применяя Подбор параметра. возможно узнать, что необходимо положить 299,1т.руб. Введите формулы. Сделайте подбор.

Задача 4. Пускай необходимо узнать возможности производства некоего продукта. Как мы знаем, что пригодятся начальные инвестиции на закупку и строительство цеха минимального оборудования в количестве 50000$ для выпуска первых 1000 единиц продукции в месяц. Изготовление одного изделия требует сырья на 5$. Расширение выпуска вероятно лишь партиями до 1500 штук для чего любой раз требуется приобретение оборудования (станка) на 7000$. Известна рыночная цена изделия 20$. Необходимо отыскать уровень производства, снабжающий его безубыточность, и графически проанализировать динамику доходов, затрат, себестоимости и прибыли в зависимости от количества выпущенного товара.Отобразим формулы и наши данные в таблице на рис. 1-4а.

Тут: Затраты=Строительство+Сырье+Затраты_на_расширение

илиG2=A2+E2*C2+ОКРУГЛВВЕРХ((E2-B2)/1500;0)*D2.

Последнее слагаемое в формуле учитывает дискретный темперамент затрат на расширение производства. Любой раз, в то время, когда число единиц товара, на которое возрастает выпуск, превышает 1,5 тыс. к расходам добавляется 7000$ на приобретение нового станка. Остальные формулы:

Себестоимость=Затраты/Произведено_товара либо H2=G2/E2.

Доход=Произведено_товара*Рыночная_цена либо I2=E2*F2.

Прибыль=Доход–Затраты илиJ2=I2-G2.

Начальный выпуск установлен в 1000 штук. Видим, что наряду с этим результаты отечественной деятельности принесут лишь убытки в количестве 35000$.

Задача пребывает в том, дабы выяснить предельное число единиц производимого товара, которое обеспечит безубыточность производства, т.е. когдаприбыль=0 либо, что также самое, в то время, когда себестоимость=рыночная цена.

Это значение возможно взять посредством Подбора параметра (рис. 1-4в). Итог на рис. 1-4б. Видим, что для окупаемости производства нужен выпуск не меньше чем 4733 штук товара. Превышение этого значения уже будет приносить прибыль обладателям предприятия. Замечание. Запустив первый раз Подбор параметра, вы вероятно не получите желаемый итог, но согласитесь с ним и опять запустите Подбор. Потому, что задача значительно нелинейна итог тут зависит от стартовых значений.

A B C D E F светло синий светло синий I J
Строи- тельство Начальный выпуск Затраты сырья на 1 штуку Затраты на следующие 1,5 тысячи Произведено единиц товара Рыночная цена единицы ВСЕГО затрат Себестоим. единицы Доход Прибыль
50000$ 5$ 7000$ 20$ 55000$ 55$ 20000$ -35000$ Рис.1-4а
50000$ 5$ 7000$ 20$ 94667$ 20$ 94667$ 0$

Рис.1-4б

Подборпараметра
Установить в ячейке:
$L$2
Рис.1-4в

Значение:

Изменяя значение ячейки:

$E$2
ОК
Отмена
Рис.1-4в

Для того, чтобы проанализировать динамику бизнеса в наглядном виде, на том же странице ниже выстроим таблицу (рис.1-4г), содержащую формулы

B6=ОКРУГЛВВЕРХ((A6-$B$2)/1500;)*$D$2+$A$2+A6*$C$2,C6=A6*$F$2,D6=C6-B6,E6=B6/A6.

A B C D E
Единиц Затраты Доходы Прибыль Себест.
-35000 55,0
-34500 43,0
-27000 33,5
-19500 27,8
-19000 26,3
-11500 23,3
-4000 21,0
-3500 20,8
19,2
17,9
18,0
17,0
16,1
Рис.1-4г
Точка безубыточности

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

Рис.1-4д

Доводом таблицы есть количество выпуска товара, начиная с 1000 шагом 500. Из нее выстроим (рис.1-4д) графики трансформации затрат, доходов, прибыли (единицы измерения слева) и себестоимости (единицы справа) товара. Ступенчатый темперамент кривых объясняетсяприобретением станков, которыене смогут быть приобретены частично.

Инструмент Подбор параметра разрешает решать относительно простые задачи с единственным малоизвестным значением. Ниже будет рассмотрено более сильное средство.

Поиск ответа

Задачи линейного программирования Инструмент Поиск ответа из вкладки Эти(несколько Анализ) предоставляет пользователю значительно более замечательное аналитическое средство. Тут возможно искать ответ неравенств и систем уравнений, каковые к тому же смогут содержать ограничения.К таким задачам относятся серьёзные для планирования коммерческой деятельности задачи оптимизации.

Замечание. В случае, если вы не найдёте Поиск решенияна лентеExcel, необходимо щелкнуть покнопке Office, далеечерез кнопку Параметры Excelвойти в меню, выбрать пунктНадстройки, в разделе Управление выбрать кнопкуПерейти и загрузить его.

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

Такие задачи описываются совокупностями линейных уравнений и линейными целевыми функциями.

Задача 1. Планирование производства. Допустим,цех создаёт два вида продукции Продукт1 и Продукт2 (П1и П2). Вычислить оптимальные недельные количества производства этих продуктов с позиций максимизации прибыли. Прибыль (целевая функция – F) первого продукта образовывает – 5 единиц, второго – 5,5.

На производстве действуют ограничения по сырью, транспортным расходам и трудовым ресурсам:

?. Для Продукта1 требуется 3 единицы сырья, для Продукта2 – 6. Всего цех располагает 18 единицами сырья.

?. Для изготовления Продукта1 требуется 6 рабочих, для Продукта2 – 4. В цехе 24 рабочих.

?. Транспортные затраты на перевозку Продукта1 составляют 2 единицы, Продукта2 – 1 единицу. Эти затраты не смогут быть менее 2 единиц согласно соглашению с автокомбинатом.

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

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

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

Область ответов ограничена прямыми (пронумерованы), взятыми из условий, в которых символы неравенств заменены на символ “=”. Ответ ищется в той полуплоскости, все точки которой удовлетворяют неравенству. Дабы выяснить эту полуплоскость, для каждого из неравенств направляться приравнять нулю значения П1и П2. В случае если получено соотношение вида 0?Const для прямой, значит начало координат входит в полуплоскость, в противном случае – нет. На рисунке штриховка для ограничивающих прямых направлена в сторону допустимыхрешений.Т.о. возможно выяснен выпуклый многоугольник, удовлетворяющий всем ограничениям (заштрихован). Все вероятные ответы находятся в него, но оптимальное ответ в обязательном порядке лежит на границе данной области, в большинстве случаев в одной из ее вершин.

3П1 + 6П2?18 ?потребность в сырье 6П1+ 4П2? 24 ?трудовые ресурсы 2П1+ 1П2³ 2 ?транспортные затраты 5П1+5,5П2?F=maxцелевая функция (прибыль) П1³ 0, П2³ 0 условие положительности
1 2 3 4 5 6
1,5
П2
П1
min(1;0))
max(3;1,5)
Рис. 2-1а
Направление перемещения целевой функции
?
?
?
A B C D E F направляться D E
Вид ресурса П1 П2 Вычисл. значения Заданные огранич. П1 П2 Вычисл. значения
Сырье 18,0
Труд 24,0
Транспорт 7,5
Прибыль: Прибыль:
Целевая функция 5,0 5,5 5,0 5,5 23,25
Итог Рис. 2-1б 3,0 1,5 Рис. 2-1в

Для его поиска воспользуемся целевой функцией F. Строго говоря, она не есть функцией, потому, что ее правая часть малоизвестна. Другими словами, это нескончаемое множество функций, о которых нам известно лишь, что они имеют однообразный наклон. Определим его. ВозьмемF=0. Тогда преобразуя выражение 5П1+5,5П2=0, можем записать что П1/П2=–5,5/5. Это тангенс наклона F. Сейчас совершим любую прямую с таким наклоном. Ну пускай она и будет проходить через точки П1=5 и П2=5,5 (изображена пунктиром). Но такое положение области решений и целевой функции нас не устраивает. Нужно, дабы эти объекты соприкасались. Для этого будем перемещать Fпараллельно самой себе до пересечения с областью ответов. Разумеется, что максимум и минимум находятся на границе многоугольника в точках выхода и входа из него. Как видим, их две. Одна из них – точка пересечения прямых? и ?. Дабы отыскать ее координаты, совместно решим уравнения 1 и 2:3П1+6П2=18;6П1+4П2=24. Тогда возьмём П1=3 и П2=1,5. Наряду с этим прибыль цеха будет равна F=5*3+5,5*1,5=23,25. Еще, но, не известно максимум ли это. Перемещая потом прямую ЦФ, отыщем второе крайнее ответ. Это точка, где П1=1 и П2=0 (где F=5*1+5,5*0=5). Потому, что 23,255, делаем вывод о том, что первая точка есть хорошим решением, вторая – минимальным. Появляется вопрос – из-за чего минимальное значение прибыли 5, а не ноль (т.е. полное сворачивание производства). Дело в том, что условия отечественной задачи предопределяют необходимые транспортные затраты в количестве не меньше 2-х единиц, потому, что согласно соглашению с компанией-перевозчиком машины арендуются в любом случае. Т.е. какую-то продукцию мы должны производить.

А на данный момент решим эту задачу вExcel. (рис. 2-1б). Ограничения вносим в верхнюю часть таблицы. Коэффициенты уравнений– в C2:D4, правые части уравнений – в F2:F4. Коэффициенты целевой функции – в C6:D6. В процессерасчетов в области Е2:Е4 отобразятся вычисляемые (фактические) значения правой части неравенств. В E2вводимE2=C2*С$7+D2*D$7, и копируем ее доE6.Итог (оптимальное количество П1 и П2) формируется в С7:D7. Клетки, в которых вычисляются какие-то значения, выделены жирным шрифтом. На рис. 2-1б продемонстрирована таблица в исходном состоянии, на рис. 2-1в – готовый итог.

Для оптимизации воспользуется инструментомПоиск решения, вызываемым через вкладку Эти, что предъявляет окно поиска рис. 2-1г (сначала безлюдное). Тут задаем ячейку, где будет формироваться оптимизируемое значение (Е6), после этого показываем, что это максимум. Возможно задать не только большое/минимальное значения, но и любую произвольную величину, введя ее в поле (Равной значению:). Ограничения устанавливаются с кнопкойДобавить, которая приводит к окну их ввода (рис. 2-1д).

Поискрешения
Установитьцелевуюячейку:
Равной: ?большому значению ?значению: ?минимальному значению
$C$7:$D$7
$C$7:$D$7 =0 $E$2
Предположить
Добавить
Поменять
Удалить
Изменяяячейки:
Ограничения:
Выполнить
Закрыть
Параметры
Вернуть
Справка
$E$6
прибыль
продукция
ресурсы
Ссылка на ячейку: Ограничение:
ОК
Отмена
Добавить
Справка
$C$7:$D$7
= ?
Добавить ограничения
Ответ отыскано. Все условия и ограничения оптимальности исполнения. Тип отчета
ОК
Отмена
Сохранить сценарии…
Справка
Результаты поиска ответа
Рис. 2-1е
?Сохранить отысканное ответ ?Вернуть исходные значения
Результаты? Устойчивость Пределы?
Рис. 2-1г
Рис. 2-1д

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

Как видим, результаты (П1=3, П2=1,5), вычисленные в таблице, совпали с результатами, отысканными вручную посредством графика. Тут же попутно мы можем сравнить предельные и практически затребованные значения ресурсов (Сырье: 18 из 18; Труд: 24 из 24; Транспорт: 7,5). Само собой разумеется, нельзя отгрузить клиенту полтора изделия. В примере все единицы измерения условны (1,5 в действительности вероятно значит и 150 и 1500). В случае если же все-таки итог должен быть строго целым, при расчете на компьютере следует в окне ограничений указать это событие.

В отличие от графического метода, Excel дает возможность приобрести оптимальное ответ без ограничения размерности совокупности неравенств.

Указания. Графические построения возможно вести и посредством средств рабочий графики Excel для чего выстроим таблицу (рис.2-1ж). В первом столбце размещаем довод П1от 1 до 6. В следующих трех столбцах разместим функции-ограничения, разрешенные довольно П2. Так в В2 поместим функцию (18-3*A2)/6. Потому, что П2 и П1 не смогут отрицательными, сделаем так, что в случае если это случится, клеточная функция выработает значение #Н/Д (нет данных). Такие значения будут игнорироваться при построении графика. Подобно запишем и другие уравнения

A B C D E F
П1 Сырье Труд Трансп. F Мax
5,0 5,0
2,5 4,5 4,1
#Н/Д 3,2
1,5 1,5 #Н/Д 2,3
#Н/Д 1,4
0,5 #Н/Д #Н/Д 0,5
#Н/Д #Н/Д -0,5
Рис. 2-1ж

В2=В случае если(18-3*A2=0;(18-3*A2)/6;#Н/Д),

С2=В случае если(24-6*A2=0;(24-6*A2)/4;#Н/Д),

D2=В случае если(2-2*A2=0;2-2*A2;#Н/Д).

В Е2 поместим выражение для целевой функции, кроме этого разрешенной довольно П2: E2=-5*A2/5,5+$F$2.Потому, что правая часть целевой функции (т.е. искомый максимум) не задана, тут возможно указать до тех пор пока любую константу, к примеру 5. Потом возможно изменять ее произвольным образом, получая нужного положения целевой функции F на графике.

Приступим к созданию диаграммы, в качестве диапазона построения указав область А1:Е8. Выберем Точечнуюдиаграммусо значениями, соединенными отрезками без маркеров.На мониторе видно, что целевая функция проходит над областью ответов. Опустить функцию возможно неспешно уменьшая значение в клетке F2 до пересечения с границей многоугольника. Найдя точку касания области решений и целевой функции, совершим (уже руками) из нее стрелки до координатных осей. С их помощью установим приблизительные значения П2 и П1, дающие максимум целевой функции (максимум содержимого клетки F2). Подобно возможно отыскать минимум. Сейчас сделаем диаграмму более наглядной. Уже на готовом графике удалим цветовой фон, и установим ход трансформации меток, равным 0,5. Сообразуясь с видом ограничивающих уравнений, обведем область допустимых ответов (применяя фигуруПолилиния Задачи линейного программирования )и закрасим в какой-нибудь цвет.

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

Задача 2. Расфасовка товара. Допустим, требуется максимально полно выполнить заказ на поставку некоего однородного жидкого материала (к примеру, машинного масла) в количестве 1400 кг. в имеющуюся у продавца тару (контейнеры емкостью по 270 кг., бочки по 130 кг.и канистры по 90 кг.). Думаем, что отгружать товар возможно в любой таре в любой комбинации так, дабы, по возможности, целый товар был размещен без остатка, т.е. отгружено ?вес_заказа.

Из этого можно организовать еще пара ограничений:

число_контейнеров=целое, число_бочек=целое, число_канистр =целое,

число_контейнеров³0, число_бочек³0, число_канистр³0,

емкость_контейнера*число_контейнеров +емкость_бочки*число_бочек+

емкость_канистры*число_канистр?вес_заказа.

На рис. 2-2а продемонстрирована таблица оптимизации, содержащаяисходные формулы и данные:

E2=B2*B3+C2*C3+D2*D3, G2=F2–E2.

Опять используем Поиск ответа, где введем следующие параметры:

Лекция 2: Задача линейного программирования. Задача о ресурсах


Понравилась статья? Поделиться с друзьями: