Решение оптимизационных задач с помощью Excel

При решении оптимизационных экономических задач необходимо пройти через следующие этапы:

· Составить математическую модель экономической задачи;

· Решить полученную экстремальную математическую задачу;

· Дать экономическую интерпретацию ответу.

Рассмотрим прохождение этих этапов на примере задачи об использовании ресурсов.

Пример. Для изготовления изделий двух видов А и В на заводе используют сырье четырех типов (І, ІІ, ІІІ, IV). Для выпуска изделия А необходимо 2 единицы сырья І типа; 1 ед. сырья ІІ типа; 2 ед. сырья ІІІ типа; 1 ед. сырья IV типа. Для изготовления изделия В требуется 3 единицы сырья І типа; 1 ед. сырья ІІ типа; 1 ед. сырья ІІІ типа. Запасы сырья составляют: І типа – 21 ед., ІІ типа – 8 ед., ІІІ типа – 12 ед., IV типа – 5 ед. Выпуск одного изделия типа А приносит 3 грн. прибыли, а одного изделия типа В – 2 грн. прибыли. Составить план производства, обеспечивающий наибольшую прибыль.

Решение.

· Составление математической модели.

Вопрос задачи, сформулированный в виде «составить план производства, обеспечивающий наибольшую прибыль», означает, что необходимо определить, какое количество изделий А и В нужно производить (для достижения наибольшей прибыли).

Так как необходимо определить количество изделий А и В, то введем следующие обозначения:

– количество изделий А, планируемое к выпуску;

– количество изделий В, планируемое к выпуску;

Z (целевая функция задачи) по своему экономическому смыслу – это прибыль. (Т.к. из условия задачи мы видим, что слово «наибольшая», связанное с экстремумом, соответствует прибыли).

Получим:

– математическая модель задачи.

· Решение полученной экстремальной задачи:

Для решения задачи воспользуемся возможностями Microsoft Excel.

§ Откройте Microsoft Excel.

§ В ячейки первой строки (в данном случае А1 и В1) введите обозначения имеющихся в задаче переменных , (язык и шрифт значения не имеют, т.к. обозначения необходимы для понимания смыслов соответствующих им чисел).

§ В ячейки второй строки (в данном случае А2 и В2), соответствующие заполненным ячейкам первой, введите произвольные значения переменных (для простоты возьмем значения 1, хотя на самом деле это могут быть любые числа). Тем самым мы присваиваем и пока значения 1.

В ячейку А4 введите обозначение целевой функции Z=.

§ В ячейку В4 введите формулу вычисления целевой функции из математической модели задачи

( ), подставляя вместо и , соответствующие им значения из ячеек А2 и В2. (Вспомните, что введение формулы начинается со знака =)

После нажатия кнопки Enter на экране монитора должно быть следующее. (Продумайте, как изменится картинка, если ввести иные значения и , к примеру, не 1, а 2. А теперь поэкспериментируйте. Оправдался ваш прогноз?)

В ячейки А5 и В5 введите соответственно слова: А5 – Ограничение, В5 – Правая часть ограничения.

§ В ячейку А6 введите формулу вычисления левой части первого ограничения , подставляя вместо и , соответствующие им значения из ячеек А2 и В2.

§ В ячейку В6 введите свободный член первого ограничения – 21. После нажатия кнопки Enter на экране монитора должно быть следующее.

§ Аналогично в ячейку А7 введите формулу вычисления левой части второго ограничения , а в В7 его свободный член – 8; в ячейку А8 введите формулу вычисления левой части третьего ограничения , а в В8 его свободный член – 12; в ячейку А9 введите формулу вычисления левой части четвертого ограничения , а в В9 его свободный член – 5;

§ После нажатия кнопки Enter на экране монитора должно быть следующее.

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

§ В меню Сервис выберите команду Поиск решения (именно она является инструментом для поиска решений задач оптимизации)

§ В этой команде вам будет предложено установить целевую ячейку. Именно слово «целевую» поможет вам в дальнейшем вспомнить, о чем идет речь. Конечно же, о значении целевой функции. Введите это значение, щелкнув левой кнопкой мышки на ячейке В4 (содержащей в данном случае числовое значение целевой функции). Получите:

§

Т.к. в данной задаче функция Z исследуется на максимум, то оставляем Равной: • максимальному значению.

Если решаем задачу на минимум, то нужно поставить метку • перед словами минимальному значению.

§ Далее нажмите на стрелку, расположенную в правой части пространства ячейки Изменяя ячейки:, в результате чего на экране должно появиться следующее

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

Т.е. заполненная ячейка должна принять вид:

§

После этого заполняют пространство ячейки Ограничения:. Для чего нужно щелкнуть по кнопке Добавить, в результате чего на экране появится новое окно:

В Ссылка на ячейку: введите номер ячейки, содержащей левую часть ограничения (в данном случае для первого ограничения – это ячейка А6).

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

В Ограничение: введите номер ячейки, содержащей свободный член ограничения (в данном случае для первого ограничения – это ячейка В6).

Т.о. перед вами на экране должна быть следующая картинка:

Это вы ввели только первое ограничение, а есть еще и другие, поэтому нажмите кнопку Добавить и аналогичным образом введите второе, третье и четвертое ограничения.

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

Поэтому после введения последнего ограничения вновь нажмите кнопку Добавить и в Ссылка на ячейку: введите номер ячейки, содержащей числовое значение ; выберите знак >=; а в Ограничение: введите 0.

Еще раз нажмите Добавить и аналогичным образом создайте условие неотрицательности для .

§ Таким образом, компьютер получил все те ограничения, которые есть в условии задачи, поэтому теперь можно нажать ОК. В результате на экране появится следующее:

Появилось? Если ДА, то нажимайте Выполнить.

И согласитесь на то, чтобы Сохранить найденное решение. Т.е. в появившемся окне нажмите ОК.

§ Обратите внимание на то, какие теперь значения принимают , и Z.

= 4; = 4; Z = 20 – Это и есть найденное оптимальное решение задачи ( ) и соответствующее

экстремальное значение целевой функции ( ).

Математически задача решена. Осталось дать экономическую

интерпретацию полученному.

· Дадим экономическую интерпретацию ответу.

Для достижения наибольшей прибыли 20 грн. необходимо производить 4 изделия А и 4 изделия В.

Литература

1. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування. – К.: КНЕУ, 2001.

2. Исследование операций в экономике/ Под ред. проф. Н.Ш.Кремера. – М.: Банки и биржи, ЮНИТИ, 2000.

3. Конюховский П.В. Математические методы исследования операций в экономике: учебное пособие. – СПб. – Москва – Харьков – Минск, 2005.

4. Кулян В.Р. и др. Математическое программирование. – К.: МАУП, 2005.

5. Таха, Хемди. Введение в исследование операций. – М.: Издательский дом «Вильямс», 2001.

Оглавление

Введение. 3

Постановка задачи линейного программирования и формы ее записи 3

Приведение задач к каноническому виду 6

Графический метод решения задач линейного программирования 9

1) Область решений линейных неравенств. 9

2) Область решений системы линейных неравенств. 10

3) Алгоритм графического метода решения ЗЛП. 10

Симплексный метод решения задач линейного программирования 14

1) Построение начального опорного плана. 14

2) Составление симплексных таблиц. Критерий оптимальности. 15

Понятие двойственности. 20

1) Симметричные двойственные задачи. 20

2) Построение модели двойственной задачи. 22

3) Применение теорем двойственности к анализу оптимальных решений пары симметричных двойственных задач 23

Транспортная задача (ТЗ) 27

1) Построение начального опорного плана. Его вырожденность или невырожденность. Ранг матрицы системы. 28

а) Метод северо-западного угла. 28

б) Метод минимального элемента (наименьшей стоимости). 29

2) Метод потенциалов. Признак оптимальности опорного плана. 29

3) Переход к нехудшему опорному плану. 30

Транспортная задача открытого типа 31

Решение оптимизационных задач с помощью Excel 36

Литература. 42

Учебное пособие

Акульшина Татьяна Сергеевна, Стебко Татьяна Владимировна

Практикум по решению линейных задач математического программирования. – Симферополь, 2006.

Корректор – Солянникова Г.Г.

Подписано к печати 12.05.2006

Формат 84 108

Объем – 2,2 усл.п.л.

Тираж – 1000 экз

Печать УЭУ

г. Симферополь

ул. Крымской правды, 4