Общие понятия оптимизационной задачи

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

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

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

1) наличие системы взаимосвязанных факторов;

2) строго определенный критерий оценки оптимума;

3) точная формулировка условий, ограничивающих использование ресурсов или факторов.

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

Для численного решения уравнений с несколькими неизвестными и ограничениями в Excel существует инструмент Поиск решения.

Если целевая функция и ограничения линейные, то решение заключается в нахождении множества чисел (х₁, х₂ .. х_n), которые минимизируют (максимизируют) линейную целевую функцию f(х_1, х₂ .. х_n)= c₁х₁+c₂х₂+. +c_nх_n при m<n линейных ограничениях-уравнениях а_i1х₁+а_i2х₂+. +а_inх_n (где i=1,2...m) и n линейных неравенствах х_k>=0 (где k=1, 2 ... n).

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

- экономическая постановка (анализ задачи, определение свойств, параметров, ограничений);

- математическая постановка (математическое описание модели, введение обозначений, ограничений, и построение целевой функции);

- реализация задачи в среде Microsoft Excel.

6.2 Основные типы задач планирования

Задача оптимизации использования ресурсов(задача планирования производства).

В математической поставке задача формулируется таким образом. Обозначим X_j (j=1,2.,n) – число единиц продукции P_j, запланированных к производству; b_i (i=1,2.,m) – запас ресурса S_i; a_ij – число единиц ресурса S_i, затраченного на изготовление единиц продукции P_j (числа a_ij – коэффициенты прямых затрат, которые называют технологическими коэффициентами); c_j – доход от реализации единицы продукции P_j. Тогда математическая модель задачи об использовании ресурсов в общей постановке примет вид: найти такой план X=(x₁, x₂,.x_n) выпуска продукции, который удовлетворит системе

и условии

,

при котором функция

принимает максимальное значение.

Рассмотрим конкретную задачу.

Для изготовления двух видов продукции P₁ и P₂ используют четыре вида ресурсов S₁, S₂, S₃, S₄. Запасы ресурсов, число единиц ресурсов, потраченных на изготовление единицы продукции, приведены в табл. 6.1 (цифры условные).

Цена реализации единицы продукции Р₁ и Р₂ соответственно, и составляет 2 и 3 у.д.е..

Необходимо составить такой план производства продукции, при котором доход от реализации будет максимальным.

Таблица 6.1 – Данные для решения задачи

Составим оптимизационную модель задачи.

Обозначим х₁, х₂ – число единиц продукции соответственно Р₁ и Р₂, запланированных к производству. Для их изготовления (табл. 1) нужно (1* х₁+3* х₂) единиц ресурса S₁, (2* х1+1* х2) единиц ресурса S₂, (1* х2) единиц ресурса S₃ (3* х1) единиц ресурса S₄. Поскольку ресурсов потребления S₁, S₂, S₃, S₄ не должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выражается системой неравенств:

Переменные положительные x1³0, x2³0.

Суммарная доход F от реализации продукции составляет:

.

Задача оптимизации составления рациона(задача о диете, задача о смесях).

Обозначим x_j (j=1,2., n) – число единиц корма n - го вида; b_i (i=1,2., m) – необходимый минимум содержания в рационе питательного вещества S_i; a_ij – число единиц питательного вещества S_ij в единице корма j-го вид; c_j - стоимость единицы корма j-го вида. Математическая модель задачи составления рациона в общей постановке примет вид. Найти такой рацион X=(x₁, x₂.,x_j,.,x_n), удовлетворяющий системе:

и условию

,

при котором функция

принимает минимальное значение.

Рассмотрим конкретную задачу.

Имеется два вида корма I и II, содержащие питательные вещества (витамины) S₁, S₂, S₃, содержащих. Содержание числа единиц питательных веществ в 1 кг каждого вида корма, необходимый минимум питательных веществ приведен в табл. 6.2 (цифры условные).

Таблица 6.2 – Данные для решения задачи

Стоимость 1 кг корма I и II соответственно равна 4 и 6 у.д.е.

Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела.

Составим оптимизационную модель задачи.

Обозначим x₁, x₂ – количество кормов I и II, входящих в дневной рацион. Тогда этот рацион будет включать (3* x₁+1* x₂) единиц питательного вещества S₁, (1* x₁+2* x₂) единиц веществ S₂, (1* x₁+6* x₂) единиц питательного вещества S₃. Так как содержание питательных веществ S₁, S₂, S₃ в рационе должно быть не менее соответственно 9, 8 и 12 единиц, то получим систему неравенств:

(1)

Переменные положительные x₁³0, x₂³0.

Общая стоимость рациона F составит:

. (2)

Задача оптимизации транспортных затрат (задача коммивояжёра)

Для математической постановки транспортной задачи в общей постановке обозначим через сіј коэффициенты затрат, через M_i – мощности поставщиков, через N_j – мощности потребителей, (i=1,2.,m)., (j=1,2.,n, m – число поставщиков, n – число потребителей. Тогда система ограничений принимает вид:

(7)

Система (7) включает в себя уравнения баланса по строкам и по столбцам.

При этом суммарная мощность поставщиков равна суммарной мощности потребителей, то есть

Целевая функция в данном случае следующая:

(8)

Таким образом, на множестве положительных решений системы ограничений (7) найти такое решение, при котором значение целевой функции (8) будет минимальное.

Рассмотрим конкретную задачу.

Есть три поставщика и четыре потребителя. Мощность поставщиков и спрос потребителей, а также затраты на перевозку единицы груза для каждой пары «поставщик - потребитель» сведены в таблицу поставок (табл. 6.3).

Таблица 6.3 – Данные для решения задачи

В левом верхнем углу произвольной (i,j) ячейки стоит коэффициент затрат – затраты на перевозку единицы груза от i-го поставщика до j-го потребителя. Задача формулируется таким образом: найти объемы перевозок для каждой пары «поставщик - потребитель» так, чтобы: мощности всех поставщиков были реализованы, спросы всех потребителей были удовлетворены, суммарные затраты на перевозку были бы минимальны. Обозначим через x_ij объем перевозки от i-го поставщика до j-го потребителя. Заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных x_ij. Чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнения баланса для каждой строки таблицы поставок:

Аналогично, чтобы спрос каждого из потребителей был удовлетворен, подобные уравнения баланса составляются для каждого столбца таблицы поставок:

Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует ввести ограничение положительности переменных: x_ij ≥0.

Суммарные затраты F на перевозку выражаются через коэффициенты затрат следующим образом: