Установить целевую ячейку С8 равной максимальному значению.

D3:D5=целоеи F3:F5=целое.

Установить целевую ячейку С8 равной минимальному значению. Изменяя ячейки: D3:D5;F3:F5.

Транспортная задача

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

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

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

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

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

Решение систем линейных уравнений

Пусть нужно найти решение системы:

Внесем коэффициенты системы в ячейки диапазона А2:А4, свободные члены в Е2:Е4, в ячейки А6:С6 внесем нули (после решения туда будут помещены значения корней системы), в столбец D внесем формулы вычисления свободных членов:

D2=СУММПРОИЗВ($A$6:$C$6;A2:C2).

Наша задача – добиться совпадения значений в столбцах D и E.

В окне Поиск решения вводятся только значения параметров: Изменяемые ячейки ($A$6:$C$6) и Ограничения ($D$2:$D$4=$E$2:$E$4). После выполнения расчета получим значения корней 1, 2 и 3.

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

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

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

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

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

цехе 24 рабочих.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

E2=C2*C$7+D2*D$7, ЕЗ=СЗ*С$7+РЗ*Р$7,

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

Для оптимизации в Excel используется инструмент Поиск решения,вызываемый через меню Сервис:

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

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

Очень часто возникает проблема оптимальной (самой дешевой) доставки некоторого объема груза из нескольких исходных пунктов (например, складов) в несколько пунктов доставки (например, магазинов).

Получим решение такой задачи средствами Excel на следующем примере. Пусть с трех складов требуется развезти закупленные в них грузы в объемах 50, 30 и 40 тонн потребителям в два пункта доставки в объеме 40 и 80 тонн соответственно. Известна цена перевозки единицы груза с каждого склада в каждый пункт доставки. Наша задача заключается в том, чтобы определить такие объемы перевозок со складов в пункты доставки, чтобы стоимость транспортировки была минимальной. В таблице искомые значения уже вычислены и обведены жирной рамкой. Видим, что стоимость всего "мероприятия" составляет 13000 руб.

Рассмотрим, как были получены искомые значения. Прежде всего в ячейку С8 заносим целевую функцию (единственную функцию в таблице). Здесь это общая стоимость всех "элементарных" перевозок, вычисляемая как сумма произведений цены доставки одной тонны груза на объем груза, перевозимого в данном направлении

C8=C3*D3+E3*F3+C4*D4+E4*F4+C5*D5+E5*F5.

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

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

B3=D3+F3распределение груза, вывозимого с 1-го склада

B4=D4+F4распределение груза, вывозимого со 2-го склада

B5=D5+F5распределение груза, вывозимого с 3-го склада

D6=D3+D4+D5состав груза, доставленного в 1-й пункт

F6=F3+F4+F5состав груза, доставленного во 2-й пункт

F3:F5>=0условие положительности объемов доставки

D3:D5>=0условие положительности объемов доставки.

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

В рассмотренной задаче подразумевается, что вес имеющегося для покупателя груза на складах равен весу запрошенного (сбалансированная задача). Это может быть в случае, когда товар предварительно отобран и закуплен у продавца именно в таких объемах на каждом из его складов. Если общий вес товара на складах превышает запрошенный и продавцу и покупателю безразлично с какого из складов осуществляется его вывоз, вероятно можно найти более дешевое решение. Пусть на складах имеется товар в объеме 30т+200т+100т=330т.

При такой постановке задачи нам придется изменить только условия, связывающие объемы наличного товара с объемами поставок, заменив знак ">" на ">=", т.е.

B3>=D3+F3, B4>=D4+F4, B5>=D5+F5.

Полученный результат равен 12500 руб.

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

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