Установка параметров решения задачи

Задача запускается на решение в окне "Решатель". Но предварительно для

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

класса необходимо нажать кнопку "Параметры" и заполнить некоторые поля окна

"Параметры".

Параметр "Ограничение поиска решения по времени" служит для назначения времени (в секундах), выделяемого на решение задачи. Можно установить время, не превышающее 32 767 секунд (более 9 часов).

Параметр "Ограничить глубину ветвей и границ" служит для управления временем решения задачи путем ограничения числа промежуточных вычислений.

Параметр "Принять переменные как не отрицательные" служит для задания неотрицательности переменных.

Параметр "Принять переменные как целочисленные" служит для задания целочисленности переменных.

Подтвердите установленные параметры нажатием кнопки OK.

Другой вариант

В этом диалоговом окне пользователь должен:

· Назначить целевую ячейку. Для этого в поле «Целевая ячейка» вводится адрес ячейки, содержащей целевую функцию. Затем устанавливается направление последней – значение, к которому она должна стремиться исходя из условий задачи (минимальное, максимальное, конкретное, задаваемое пользователем).

· В поле «Изменяя ячейки» ввести адреса ячеек, зарезервированных для искомых переменных.

· Ввести ограничения. Для этого в области Ограничительные условия (см. рис. 7.2.):

· в поле «Ссылка на ячейку:» ввести адрес ячейки листа, содержащей формулу для расчета показателя, используемого в качестве левой части неравенства,

· из списка знаков неравенств выбрать необходимый знак,

· в поле «Ограничение:» указать адрес ячейки, содержащей показатель, используемый в качестве правой части неравенства.

Добавление каждого последующего ограничения осуществляется с помощью кнопки Добавить. После окончания ввода ограничений необходимо нажать Ok

 

36. Транспортная задача: стандартная постановка и особенности решения.

Для решения задачи построим ее математическую модель. Обозначим количество заводов N, а количество магазинов M. Для нумерации заводов и магазинов введем индексы i и j. Индекс i пробегает целочисленные значения от 1 до N и указывает номер завода, индекс j принимает значения от 1 до M и соответствует номеру магазина. Объем производства i -го завода обозначим a_i, объем спроса j -го магазина - b_j. Условие баланса спроса и предложения имеет вид

. (7.1)

Неизвестными величинами в данной задаче являются объемы перевозок, которые мы обозначим x_ij. Величина x_ij – это объем перевозок с i -го завода в j -й магазин. Затраты на перевозку единицы продукции из пункта i в пункт j по аналогии обозначим c_ij. Очевидно, что величины x_ij и c_ij в нашей задаче могут принимать лишь неотрицательные значения

, (7.2.)

. (7.3)

Стоимость одной перевозки составит x_ijc_ij, а общие транспортные расходы Z будут складываться из затрат по каждому маршруту:

. (7.4)

По условию задачи требуется минимизировать совокупные затраты на перевозки. В нашей модели оптимальному графику перевозок соответствует минимальное значение функции Z. Если не накладывать на величины x_ij и c_ij дополнительных условий и попытаться минимизировать целевую функцию (3.5.4), то в результате мы получим Z = 0 и x_ij = 0. Такой результат, очевидно, не может быть удовлетворительным ответом. Для правильного решения поставленной задачи необходимо ввести ограничения на объемы вывозимой и ввозимой продукции. Объем вывозимой с i -го завода продукции должен быть равен объему производства a_i, объем ввозимой продукции должен соответствовать объему спроса b_j:

, (7.5)

. (7.6)

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

Рассмотрим решение сбалансированной транспортной задачи средствами OpenOffice.org Calc. Пусть имеется 3 завода (N =3) и 4 магазина (M =4). Введем в рабочий лист данные об объемах производства и спроса как показано на рис. 7.4. Для проверки баланса (выражение (7.1)) просуммируем значения в диапазонах B4:B6 и G4:G7, затем сравним вычисленные суммы в ячейке C10 с помощью формулы

«=IF(B7 = G8;"Задача сбалансирована";"Нарушен баланс!")».

Далее в диапазон B14:E16 вводим данные о себестоимости перевозок между заводами и магазинами.

Для распределения объемов перевозок между экономическими объектами создадим таблицу «Объемы перевозок» (рис. 7.5). Для проверки условий (7.5) и (7.6) в ячейках B23:E23 и F20:F22 вычислим суммы строк и столбцов таблицы «Объемы перевозок». Суммы по столбцам соответствуют объемам ввозимой продукции, а по строкам – объемам вывозимой продукции. Значения объемов перевозок заранее неизвестны, для определенности в качестве начального приближения вводим в ячейки B20:E22 нулевые значения. Для вычисления целевой функции (7.4) введем в ячейку E25 формулу

«=SUMPRODUCT(B14:E16; B20:E22)».

Теперь рабочий лист содержит всю необходимую информацию для «Поиска решения». Выполним команду «Сервис|Решатель» и заполним поля открывшегося диалогового окна (рис. 7.6). Условия (7.2), (7.5) и (7.6) вводим в диалог «Решатель» в виде ограничений. Для корректного решения линейной задачи выберем соответствующий алгоритм в диалоговом окне «Параметры» и установим все необходимые параметры. После нажатия кнопки «Решить» «Решатель» находит оптимальный план перевозок грузов, показанный на рисунке

1. Задача о назначениях: стандартная постановка и особенности решения.

В распоряжении бригадира имеются N рабочих, каждого из которых нужно назначить на выполнение одной из N работ. Рабочие имеют разную квалификацию, поэтому стоимости c_ij выполнения i -м рабочим j -й работы различны. Бригадир должен распределить рабочих так, чтобы общая стоимость работ Z была минимальной. При этом каждый рабочий должен быть загружен только на одной работе и все работы - выполнены. Заметим, что в данной задаче число рабочих и работ совпадает, т.е. задача является сбалансированной. В случае несбалансированной задачи ее необходимо предварительно сбалансировать путем введения фиктивных рабочих или видов работ с достаточно высокими штрафными стоимостями работ.

Построим математическую модель данной задачи. Введем бинарные переменные x_ij так, что x_ij = 1, если i -й рабочий выполняет j -ю работу, и x_ij = 0, если не выполняет. Суммарная стоимость работ (целевая функция) вычисляется по формуле

. (7.7)

Для контроля условия «одна работа – один рабочий» дополним модель ограничениями

, (7.8)

, (7.9)

. (7.10)

Реализация задачи о назначениях в среде MS Excel показано на рис. 7.7. Ячейки B4:E7 содержат значения стоимостей выполнения работ, а ячейки B10:E13 – таблицу назначений. Для проверки условий (7.8) и (7.9) в ячейках F10:F13 и B14:E14 вычисляются контрольные суммы по строкам и столбцам таблицы назначений. Суммарная стоимость работ вычисляется в ячейке D15 по формуле

«=SUMPRODUCT(B4:E7; B10:E13)».

После подготовки рабочего листа выполняем команду «Сервис|Поиск решения» и заполняем поля диалога (рис. 7.8) и устанавливаем необходимые параметры. Результаты оптимизации (таблица назначений и общая стоимость работ)

 

1. Задача планирования штатного расписания.

Для формулировки математической модели введем обозначения. Пусть M₀ – исходное количество штатных сотрудников, M_i - количество штатных сотрудников в i -м месяце, N_i - количество стажеров в i -м месяце, S_i - объем необходимого рабочего времени в i -м месяце. Размер оплаты труда стажеров и штатных сотрудников обозначим A и B соответственно. Количество рабочего времени в месяц для стажеров обозначим C, и для штатных сотрудников - D.

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

,. (7.11)

а в последующие месяцы к нему добавляются стажеры

, i = 2, 3, …, n, (7.12)

где n – количество планируемых месяцев.

Затраты на оплату труда (R_i) и объем фактических затрат рабочего времени (T_i) в i -м месяце составят

(7.13)

и

(7.14)

соответственно. Сумма общих затрат (целевая функция) за планируемый период будет

. (7.15)

Для корректного решения задачи добавим ограничения на возможные значения N_i и M_i:

, , N_i и M_i – целые. (7.16)

Условие выполнения ежемесячного плана имеет вид

. (7.17)

Рассмотрим решение этой задачи с помощью OpenOffice.org Calc. На рисунке 7.9 показан фрагмент рабочего листа с исходными данными и результатами оптимизации. Вычисление количества постоянных сотрудников производится в ячейках C11 и C12:C16 по формулам (7.11) и (7.12) соответственно:

«= $D$7»,

«= C11 + B11» (в ячейке C13).

Количество отработанного времени по месяцам определяется в ячейках E11:E16 в соответствии с выражением (7.14):

«= C11 * $E$5 + B11 * $D$5» (в ячейке E11).

Ежемесячные затраты на оплату труда вычисляются в диапазоне F11:F16 по формуле (7.13):

«= C11 * $B$5 + B11 * $A$5» (в ячейке F11).

Общие расходы (целевая функция) за весь период планирования подсчитываются в ячейке F17 по формуле

«=SUM(F11:F16)».

Условия введены в качестве ограничений в диалоге «Решатель». Не забудьте установить все необходимые параметры. Результатом оптимизации будет полугодовой план приема и обучения стажеров, находящийся в диапазоне A11:B16.