Методы принятия управленческих решений

Вариант 1

 

Задача 1

На  трех хлебокомбинатах ежедневно производится 110, 190 и 90 т муки. Эта мука потребляется  четырьмя хлебозаводами, ежедневные потребности которых равны соответственно 80, 60, 170 и 80 т. Тарифы перевозок 1 т муки с хлебозаводов задаются матрицей:

Составить такой план доставки муки, при котором  общая стоимость перевозок является минимальной.

 

Для решения задачи на ПК с использованием  пакета EXCEL необходимо:

1. Ввести исходные данные в ячейки рабочего листа EXCEL.
2. Разметить блоки ячеек на рабочем листе EXCEL, необходимые для моделирования объемов выпуска продукции, а также для формирования элементов математической модели и целевой функции.
3. Сформировать на рабочем листе EXCEL элементы математической модели  и целевую функцию.
4. Настроить программу «Поиск решения» и выполнить ее.
5. Провести анализ отчетов по результатам, по устойчивости, по пределам

 

1 Ввод исходных данных

 

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

- целевой функции, 

- области допустимых решений и 

- системы ограничений, определяющих  эту область. 

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

Транспортная  задача представляет собой частный  вид задачи линейного программирования с особой структурой.

По  исходным данным существует n=4 потребителя – хлебозаводы В1, В2, В3 и В4, причём их потребности в муке известны и равны b₁, b₂, ..., b₄. Мука поставляется от m=3 производителей A₁, A₂, ..., A_3, которые производят муку в количестве, равном соответственно a₁, a₂, ..., a₃ . Числа c_ij показывают стоимость перевозки, которые определены для каждого производителя муки ко всем хлебозаводам - потребителям, а x_ij – соответствующее количество перевозимой муки. В качестве целевой функции выступает суммарная стоимость перевозки муки в день, которую нужно минимизировать:

 

Поставки  муки для одного хлебозавода В_j должны быть равны дневной потребности данного завода, т.е.:

 

Аналогично, отгрузки муки с одного хлебокомбината - поставщика Аi, должны быть равны дневной мощности производства муки для этого хлебокомбината, т.е.:

 

По  условиям транспортная задача является закрытой, так как суммарный объем потребности в муке равен суммарному объему ее производства, т.е.:

 

или 80 т + 60 т + 170 т + 80 т = 110 т + 190 т + 90 т

390 т = 390 т

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

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

 

 

Составим  транспортную таблицу на рабочем листе электронной таблицы EXCEL. Рабочий лист EXCEL с введенными исходными данными для решения задачи показан на рис.1.1.

Рис.1.1.

 

 

 

 

 

2 Разметка блоков ячеек рабочего листа EXCEL

 

Кроме исходных данных на рабочем листе  EXCEL для решения задачи необходимо предусмотреть:

- блок ячеек «Матрица перевозки муки», в котором будут моделироваться объемы перевозок;

- блок ячеек «Фактически отгружено», в котором будет моделироваться объемы фактически перевезенной муки по всем хлебозаводам для каждого хлебокомбината - поставщика;

- блок ячеек «Фактически поставлено муки», в котором будет моделироваться объемы фактически доставленной муки от всех поставщиков для каждого из заводов-потребителей;

- блок ячеек «Стоимость перевозки по хлебозаводам», в котором будут подсчитываться стоимости перевозки от всех поставщиков для каждого из заводов-потребителей;

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

Рабочий лист EXCEL с размеченными блоками ячеек показан на рис.1.2.

Рис.1.2

 

 

3 Формирование элементов математической модели

 

Элементами  математической модели задачи являются следующие суммы:

- фактически отгружено муки для всех потребителей от конкретного поставщика:

 

- фактически поставлено муки от всех поставщиков конкретному потребителю:

 

Сначала сформируем для каждого хлебокомбината - поставщика в блоке «Фактически отгружено». Для этого выберем первую ячейку блока «Фактически отгружено» - H14. На панели инструментов выберем кнопку «автосуммирование»               ( ) и укажем диапазон ячеек «Матрицы перевозки муки», соответствующий первому хлебокомбинату – это С14:F14. Скопируем формулу «=СУММ(С14:F14)» из первой ячейки блока «Фактически отгружено» на все остальные ячейки этого блока.

Теперь  сформируем  для каждого хлебозавода - потребителя в блоке «Фактически поставлено муки». Для этого выберем первую ячейку блока «Фактически поставлено» - С18. На панели инструментов выберем кнопку «автосуммирование» ( ) и укажем диапазон ячеек «Матрицы перевозки муки», соответствующий первому хлебозаводу – это С14:С16. Скопируем формулу «=СУММ(С14:С16)» из первой ячейки блока «Фактически поставлено муки» на все остальные ячейки этого блока.

Результат формирования элементов математической модели показано на рис.1.3.

Рис.1.3

 

 

4 Формирование целевой функции

 

Для формирования целевой функции введем вначале в блоке ячеек «Стоимость перевозки по хлебозаводам» формулы, отражающие общую стоимость доставленной муки каждому из четырех потребителей. Для этого активизируем ячейку С20, на панели инструментов выберем кнопку «автосуммирование» ( ) и укажем сначала диапазон ячеек «Матрицы перевозки муки», соответствующий первому хлебозаводу – это С14:С16, а затем введем знак * (умножение) и диапазон ячеек «Матрицы стоимости доставки муки», соответствующий первому хлебозаводу – это С5:С7. Далее активизируем строку формул и нажмем одновременно Ctrl+Shift+Enter. Нажмем Enter. Таким образом, в ячейке С20 получим:

{ =СУММ(C14:C16*C5:C7)}

Скопируем формулу в ячейке С20 на ячейки D20, E20 и F20.

Сформируем  теперь целевую функцию транспортной задачи в ячейку «Общая стоимость», для этого активизируем ячейку H20,  на панели инструментов выберем кнопку «автосуммирование» ( ) и укажем диапазон ячеек «Стоимость перевозки по хлебозаводам» - это С20:F20.

После формирования элементов математической модели и целевой функции рабочий лист EXCEL примет вид, показанный на рис.1.4.

Рис.1.4

 

 

 

 

 

 

5 Настройка и выполнение программы «Поиск решения»

 

Активизируем  ячейку целевой функции H20. На панели инструментов выберем вкладку меню «Данные» и в группе кнопок «Анализ» нажмем «Поиск решения». Откроется диалоговое окно (рис.1.5), где в поле «Оптимизировать целевую функцию» будет указана ячейка $H$20.

Рис.1.5

 

Установим переключатель «Минимум», так как по условиям задачи целевая функция минимизируется.

Перейдем  в поле «Изменяя ячейки переменных»  и укажем диапазон ячеек «Матрицы перевозки муки» - это $C$14:$F$16.

Теперь  введем ограничения задачи, нажав кнопку «Добавить»:

- во первых, ограничение по количеству отгруженной муки каждым поставщиком – выделим диапазон ячеек «Фактически отгружено» - это H14:H17, установим знак «=» и введем диапазон ячеек «Производство муки» - это H5:H7 (рис.1.6). Нажмем «Добавить»;

Рис.1.6

 

- во-вторых, ограничение по количеству поставленной муки – выделим диапазон ячеек «Фактически поставлено муки» - это С18:F18, установим знак «=» и введем диапазон ячеек «Потребление муки» - это С9:F9 (рис.1.7). Нажмем «Добавить»;

Рис.1.7

- в-третьих, ограничение неотрицательности переменных - выделим диапазон ячеек «Матрицы перевозки муки» - это С14:F16, установим знак «>=» и введем в поле «Ограничение» число 0 (рис.1.8).

Рис.1.8

Нажмем  «ОК». В поле «Выберете метод решения» установим «Поиск решения линейных задач симплекс-методом. Диалоговое окно «Параметры поиска решения» примет вид как показано на рис. 1.9.

Рис.1.9

 

Нажмем  «Найти решение». Для проведения анализа отчетов по результатам, по устойчивости, по пределам в диалоговом окне «Результаты поиска решения» выделим в меню «Отчеты» поочередно строки «Результаты», «Устойчивость» и «Пределы» (рис.1.10).

Рис.1.10

 

Нажмем  ОК в окне «Результаты поиска решения» и «Закрыть» в окне «Параметры поиска решения». На рабочем листе имеем результат решения задачи (рис.1.11).

 

Рис.1.11

 

 

 

6 Анализ отчетов по результатам, по устойчивости, по пределам

 

Применяя  «Поиск решения», кроме нахождения оптимального решения получены 3 листа с отчетами: Отчет по результатам, Отчет по пределам, Отчет по устойчивости. Используя эти отчеты можно проанализировать поведение оптимального плана в различных изменениях.

1) Отчет по результатам (рис.1.12).

 

Рис.1.12

Отчет по результатам состоит из 3 таблиц.

1 – Целевая ячейка. В ней отображается начальное значение целевой функции и оптимальное (результат). В нашем случае 0 и 1280.

2 - Изменяемые ячейки. В ней отражены исходные значения переменных и результирующие (оптимальные). В нашей задаче исходные значения количества перевозимой муки от поставщиков к потребителям равно 0, а оптимальные значения, соответственно, равны:

- 1-й хлебокомбинат – 2-му хлебозаводу по 60 т в день;

- 1-й хлебокомбинат – 4-му хлебозаводу по 50 т в день;

- 2-й хлебокомбинат – 1-му хлебозаводу по 20 т в день;

- 2-й хлебокомбинат – 3-му хлебозаводу по 170 т в день;

- 3-й хлебокомбинат – 1-му хлебозаводу по 60 т в день;

- 3-й хлебокомбинат – 4-му хлебозаводу по 30 т в день.

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

3 - Ограничения. Кроме имени ограничения, ячейки, в которую вписана левая часть ограничения, в ней отображены столбцы:

- Значение – значение левой части ограничения при оптимальном плане, т.е. сколько фактически использовано ресурса.

- Формула – отображается знак ограничения (больше или равно, меньше или равно и т.д.)

- Состояние – отображено «привязка» или «без привязки» ограничение. Если статус «привязка», то ресурс использован полностью. Если же статус – «без привязки», то ресурс использован не полностью.

- Допуск – отображено количество оставшегося не использованным ресурса.

 

2) Отчет по устойчивости (рис.1.13).

 

Рис.1.13

Отчет по устойчивости состоит из 2 таблиц.

1 – ячейки переменных.  Кроме имени переменных и адресов ячеек в ней присутствуют столбцы:

- Окончательное значение – это оптимальный план.

- Приведенная стоимость – показывает, на сколько изменится целевая функция после принудительного включения единицы этой продукции в оптимальный план. Если продукт рентабелен, то нормированная стоимость будет равна 0.

- Целевой коэффициент – значения коэффициентов целевой функции. В нашем примере – стоимость доставки муки от поставщиков потребителям.

- Допустимое увеличение, допустимое уменьшение – показывает границы изменений коэффициентов целевой функции, при которых сохраняется набор переменных, входящих в оптимальное решение. Например, если стоимость доставки муки от 1-го хлебокомбината 3-му хлебозаводу увеличится на 10 д.ед. и более, то изменится набор переменных, входящих в оптимальное решение. Какой именно будет оптимальный план, нужно пересчитывать заново.

2 – Ограничения.  Кроме имени переменных и адресов ячеек в ней присутствуют столбцы:

- Окончательное значение - значение левой части ограничения при оптимальном плане, т.е. сколько фактически использовано ресурса.

- Теневая цена – изменение целевой функции при изменении дефицитного ресурса на 1 единицу. Теневая цена недефицитного ресурса будет равна 0. Если увеличить ресурс – потребность 1-го хлебозавода в муке на 20 т в день ( до 100 т), то целевая функция увеличится на   20 * 4 = 80 д.ед. и  станет равной 1280 + 80 = 1360 д.ед..

- Ограничение Правая часть – запас ресурса.