Задача распределения ресурсов

Поиск решения

Инструмент Поиск решенияпредоставляет пользователю гораздо бо­лее мощное аналитическое средство. Здесь можно искать решение сис­тем уравнений, которые к тому же могут содержать ограничения. К та­ким задачам относятся важные для планирования коммерческой дея­тельности задачи линейного и нелинейного программирования.

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

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

Задача распределения ресурсов

Рассмотрим постановку задачи на следующем примере. Положим, цех предприятия производит два вида продукции (Продукт1 и Про­дукт!). Следует рассчитать оптимальные недельные объемы производ­ства этих продуктов с точки зрения максимизации прибыли. Прибыль (Целевая функция - F) от первого продукта составляет - 5 единиц, от второго- 5,5.

На производстве действуют ограничения по сырью, трудовым ре­сурсам и транспортным расходам: ©.Для Продукта1 требуется 3 единицы сырья, для Продукта2 - 6.

Всего цех располагает 18 единицами сырья. (2). Для изготовления Продукта 1 требуется 6 рабочих, для Продукта2 – 4. В цехе 24 рабочих.

(3). Транспортные расходы на перевозку Продукта 1 составляют 2 еди­ницы (тыс. руб.), а Продукта2 - 1 единицу. Эти затраты не могут быть менее 2 единиц (цена аренды одного автомобиля минимальной грузо­подъемности в течение дня). Полагаем, что вся дневная продукция цеха может быть вывезена на одном грузовике. Кроме того, очевидно, что ни одна из переменных (число единиц продукции) не может быть менее нуля.

Отсюда запишем соотношения, из которых можно вычислить оп­тимальные объемы производства Продукта1 и Продукта2 (виды про­дукции обозначены как Х1и Х2).

3X₁+6X₂<18 (1) потребность в сырье

6X₁ + 4X₂ < 24 (2) трудовые ресурсы

2X₁ + 1X₂ > 2 (3) транспортные расходы

F=5X₁+5,5X₂ max целевая функция

X₁>0, X₂>0 условие положительности

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

MIN(1; 0)

Область поиска решения ограничена прямыми (пронумерованы), полученными из условий, в которых знаки неравенств заменены на знак "=". Решение ищется в той полуплоскости, все точки которой удовлетворяют неравенству. Чтобы определить эту полуплоскость, следует приравнять нулю значения X} и Х2- Если получено соотноше­ние вида 0<Const для прямой, лежащей над началом координат, значит начало координат входит в полуплоскость (аналогично, при 0>Const для прямой, проходящей под пересечением координат). В остальных случаях полуплоскость решений не включает точку начала координат. На рисунке штриховка у ограничивающих прямых направлена в сторону области решений.

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

Прямая целевой функции изображена жирной пунктирной линией. Первоначально она проводится произвольно (в графике - через точки Х]=5 и Х2⁼5,5). Поскольку у целевой функции отсутствует правая часть, мы можем однозначно определить только наклон прямой. Для нахождения максимально возможного допустимого значения целевой функции ее следует перемещать параллельно самой себе до пересече­ния с точкой на границе многоугольника решений, где ее значение максимально. Как видим, в нашем случае, это точка пересечения пря­мых 1 и 2. Чтобы найти ее координаты и значение целевой функции, следует совместно решить уравнения 1 и 2:

3X₁ + 6X₂ = 18

6X₁ + 4X₂ = 24

В результате получим X₁=3 и Х₂=1,5. Это и есть оптимальное ре­шение. При этом прибыль цеха будет равна F=5*3+5,5*1,5=23,25. Пе­ремещая прямую целевой функции, здесь же можно найти и мини­мальное значение. Это точка, где X₁=l и Х₂=0.

Замечание.Конечно, нельзя отгрузить покупателю полтора изде­лия. Следует иметь в виду, что здесь рассматривается пример, где все единицы измерения условны (1,5 на самом деле может означать и 150 и 1500). Если же все-таки результат должен быть строго целым, при расчете на компьютере следует в окне формирования ограничений (см. ниже) указать это обстоятельство.

Рис. 2

Excel позволяет легко получить оптимальное решение без ограни­чения размерности системы неравенств и целевой функции. Пример построения такой таблицы применительно к рассмотренной выше за­даче приведен на рис. 9.2-2.

Ограничения вносятся в верхнюю часть таблицы. Коэффициенты отношений - в область C2:D4, правая часть уравнений - в F2:F4. Ко­эффициенты целевой функции - в C6:D6. В процессе расчетов в облас­ти Е2:Е4 отображаются вычисляемые (фактические) значения правой части неравенств. Сюда вводятся формулы:

Е2=СУММПРОИЗВ(С$7:О$7;С2:О2),

ЕЗ=СУММПРОИЗВ(С$7:О$7;СЗ:ОЗ),

Е4=СУММПРОИЗВ(С$7:О$7;С4:О4).

Аналогично значение целевой функции (прибыль) равно

Е6=СУММПРОИЗВ(С$7:О$7;С6:О6).

Если размерность системы уравнений (как в нашем случае) невелика, можно воспользо­ваться более простыми функциями (рис. 9.2-3):

E2=C2*C$7+D2*D$7, E3=C3*C$7+D3*D$7, _{Рис 9} 2 3

E4=C4*C$7+D4*D$7, E6=C6*C$7+D2*D$7.

Результат (оптимальное количество Продукта 1 и Продукта2) фор­мируется в области C7:D7. Клетки, в которых вычисляются какие-то значения, выделены жирным шрифтом. Остальное - исходные данные.

Поиск решения

Установить целевую ячейку: I $Е$6

Равной:0 максимальному значению Означению: О минимальному значению

Выполнить )

Закрыть

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

$C$7:$D$7

Предположить

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

$C$7:$D$7 >=0 $Е$2 <= $F$2 $Е$3 <= $F$3 $Е$4 >= $F$4

Добавить Изменить Удалить

Параметры

|Восстановить|

Рис. 2-4

Для оптимизации в Excel используется инструмент Поиск реше­ния,вызываемый через меню Сервис,который предъявляет окно (рис. 2-4). Сначала задается ячейка, содержащая оптимизируемое значение (здесь Е2), затем указывается его желаемое значение (у нас макси­мальное). Можно задать не только максимальное/минимальное значе­ния, но и любую произвольную величину, введя ее в специальное поле (Равной значению:).Ограничения устанавливаются с помощью кноп­ки Добавить,которая вызывает окно их ввода (рис. 9.2-5).

После ввода всех ограничений и других условий следует нажать кнопку Выполнитьдля решения поставленной задачи.

Добавить ограничения

Ссылка на ячейку:

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

ок

Отмена | Добавить") Справка |

Рис. 9.2-5

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: