Инструкция по использованию MS Excel для решения задач оптимального линейного программирования

ОБЩИЕ ПОЛОЖЕНИЯ

Лабораторные работы проводятся в рамках изучения дисциплины “ЭММ в социально-экономических исследованиях” с целью получения студентами навыков и умений в построении, решении и анализе экономико-математических моделей с помощью современных программных средств и вычислительной техники.

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

ПЕРЕЧЕНЬ ТЕМ ЛАБОРАТОРНОГО ПРАКТИКУМА

Таблица 1.1

Номер темы	Наименование тем дисциплины	Темы лабораторных работ
	Системные аспекты моделирования	Построение и решение простейшей линейной модели
	Методология моделирования экономических систем	Исследование межотраслевого баланса
	Информационные аспекты моделирования	Решение многокритериальных задач линейного программирования
	Экономико-математические методы и модели в логистике	Исследование эффективности вовлечения финансовых средств

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

Студенты выполняют лабораторные работы в отведенные аудиторные часы, по каждой лабораторной работе оформляется отчет, образец титульного листа приведен в Приложении 1.

Лабораторные работы по курсу “ЭММ в социально-экономических исследованиях” выполняются на базе MS Excel. Для решения оптимизационных задач необходимо использовать надстройку “Поиск решения”.

ЛАБОРАТОРНАЯ РАБОТА №1. Построение и решение простейшей линейной модели оптимального программирования

Содержание лабораторной работы

1. По условию задачи построить модель линейного программирования:

2. Ввести исходные данные для расчета по модели в таблицы MS EXCEL, сформировать таблицы промежуточной информации.

3. Решить задачу с помощью модели. Проанализировать решение на основе информации подготовленных отчетов о результатах и устойчивости.

4. Выполнить по аналогии индивидуальное задание.

4. Написание отчета по лабораторной работе сделанной на основе индивидуальных данных.

В отчет входит построенная модель (скрин модели сделанной в «поиске решения»), скрин таблиц MS EXCEL, результаты решения задачи

 

2.2 Рекомендации по выполнению лабораторной работы

Рассмотрим выполнение данной лабораторной работы на следующем примере.

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

Таблица 2.1

Количество человек в группе

 

Номер группы	1	2	3	4	5
Количество человек в группе

 

1. Ввести исходные данные в форме таблиц в MS Excel (таблицы 2.1. и 2.2.).

 

 

Таблица 2.2

Информация по гостиницам

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

 

3. Сформировать таблицу переменных модели (табл. 2.3). В ячейках таблицы по результатам расчета модели будут записаны значения переменных xij - количество человек j -ой группы размещаемых в i -ой гостинице.

Таблица 2.3

Переменные модели

Гостиницы	Количество размещаемых (чел.)
	Туристические группы
						Всего
						=сумм(…)
						=сумм(…)
						=сумм(…)
Всего	=сумм(…)	=сумм(…)	=сумм(…)	=сумм(…)	=сумм(…)

4. Построить ограничения. В ячейках MS Excel сформировать выражение левой части ограничений. Например, для данной задачи суммы по столбцам таблицы 3, будут ограничениями по количеству человек в группе, а суммы по строкам - ограничения по числу свободных мест в гостиницах. Для этого использовать встроенную функцию MS Excel “СУММ()” (см. таблицу 2.3.). В качестве аргумента функции указать диапазон суммируемых значений.

5. Построить целевую функцию. Для простоты формирования выражения целевой функции создать таблицу промежуточных расчетов.

 

Таблица 2.4

Расходы на размещение туристических групп

Гостиницы	Количество размещаемых (чел.)
	Туристические группы
						Всего
						=сумм(…)
						=сумм(…)
						=сумм(…)
Всего	=сумм(…)	=сумм(…)	=сумм(…)	=сумм(…)	=сумм(…)	=сумм(…)

 

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

 

6. Далее необходимо перейти к поиску решения. Выделяем в окне ввода параметров в качестве целевой ячейки ячейку, в которой находятся общие затраты на размещение всех туристов. Выбираем критерий поиска «Минимум», в качестве изменяемых ячеек выбираем ячейки, в которых показано размещение туристов в той или иной гостинице (таблица 2.3.). Далее добавляем ограничения:

A) все изменяемые ячейки должны быть не отрицательными

Б) все изменяемые ячейки должны быть целыми

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

Г) Количество размещаемых туристов по гостинице должно быть меньше или равно количеству мест в гостинице (левая часть ограничений – последний столбец из таблицы 2.4.; правое ограничение – второй столбец, таблицы 2.2.)

Индивидуальные задания к лабораторной работе №1

 

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

 

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

Вар1					Вар11
Вар2					Вар12
Вар4					Вар13
Вар3					Вар14
Вар5					Вар15
Вар6					Вар16
Вар7					Вар17
Вар8					Вар18
Вар9					Вар19
Вар10					Вар20

 

Стоимость размещения в гостинице.

Вар1		Вар2
Вар3		Вар4
Вар5		Вар6

 

 

Содержание лабораторной работы

1. Построить параметрическую модель оптимизации прибыли в соответствии с индивидуальным заданием.

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

структура оптимального плана,

требуемые объемы ресурсов,

двойственная оценка (теневая цена) ресурса.

3. Подготовка и написание отчета. В отчет входит: модель, таблица, график.

 

Описание задачи

На предприятии в процессе производства используется два технологических способа I и II. При этом расходуются сырье, трудо­вые ресурсы и учитываются накладные расходы. Известны удель­ные затраты а_ij (i = 1,2,3; j = 1,2) каждого ресурса, запасы ресурсов b_i (i = 1,2,3), а также удельная прибыль с_j (j = 1,2) при исполь­зовании каждого технологического способа. Необходимо найти такой план производства, чтобы прибыль от реализации продукции была максимальна.

3.3 Рекомендации по выполнению лабораторной работы

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

В лабораторной работе исследуется влияние параметров одного из ограничений модели на оптимальное решение, т.е. параметр b_i (объем дефицитного) ресурса – переменная величина. В общем виде модель выглядит:

Для решения индивидуального задания необходимо использовать следующую модель:

 

2. Необходимо решить поставленную задачу используя MS Excell используя пооиск решения

3. Показать решение графическим способом.

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

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

 

 

Индивидуальные задания к лабораторной работе №2

 

Показатели

Значение показателей по вариантам

Цены продукции

продукция 1

продукция 2

Трудозатраты

продукция 1

продукция 2

Нормы расхода сырья

продукция 1

продукция 2

Нормы расхода материалов

продукция 1

продукция 2

Общие объемы ресурсов в плановом периоде

фонд времени

объем сырья

объем материалов

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

Вар.	Ресурс
	Трудозатраты
	Нормы расхода сырья
	Нормы расхода материалов
	Трудозатраты
	Нормы расхода сырья
	Нормы расхода материалов

 

 

Содержание лабораторной работы

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

 

2. Найти субоптимальные решения по каждой целевой функции. Результаты занести в матрицу значений.

3. Сформировать матрицу оценок. Выбрать компромиссное решение

а) по критерию максимизации минимальной степени достижения цели,

б) по критерию максимальной суммы степеней достижения цели.

4. Сконструировать новый критерий максимальной суммы степени достижения цели путем свертывания. Найти оптимальный план.

5. Построить модель l - оптимизации. Найти оптимальное решение. Определить степень достижения показателями своих оптимальных значений в старой и новой шкалах.

6. В отчете привести исходную модель, матрицы значений и оценок, дать краткие комментарии по результатам.

Рекомендации по выполнению лабораторной работы

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

В: 30· х ₁ + 60 х ₂ → max

ЧП: 10· х ₁ + 40 х ₂ → max

П: 10· х ₁ + 4 х ₂ → max

х ₁ + 3· х ₂ ≤ 21

2· х ₁ + 3· х ₂ ≤ 24

2· х ₁ + х ₂ ≤ 16

х ₁ ≤ 7

где В – выручка предприятия

ЧП – чистая прибыль

П – прибыль

После решения данной модели по каждому критерию матрица значений примет вид:

Таблица 4.1

Матрица значений

	Значения показателей
Вариант	В	ЧВ	П
В →max
ЧВ →max
П →max
Fi
fi
Δ i

F_i – наилучшее значение показателя;

f_i – наихудшее значение показателя;

Δ i – разброс между наилучшим и наихудшим

значениями.

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

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

В рассматриваемом примере матрица оценок примет вид:

Таблица 4.2

Матрица оценок

j i
В →max		0.96	0.89
ЧВ →max	0.93		0.35
П →max	0.73	0.53

 

Критерии выбора оптимального варианта по матрице оценок могут быть различными.

По максимальной из минимальных оценок

Результат поиска оптимального решения по данному критерию можно отразить в матрице оценок:

Таблица 4.3

Результат поиска по максимальной из минимальных оценок

 

j i				Критерий 2.1
В →max		0.96	0.89	0.89
ЧВ →max	0.93		0.35	0.35
П →max	0.73	0.53		0.53

 

Критерий максимальной сумме оценок

Фактически, речь идет о сопоставлении построчных сумм матрицы оценок, что с помощью рассматриваемого примера можно изобразить следующим образом (Табл.4.4):

 

Таблица 4.4

Результата поиска по максимальной сумме оценок

 

j i				Критерий 2.2
В →max		0.96	0.89	2.85
ЧВ →max	0.93		0.35	2.28
П →max	0.73	0.53		2.26

 

2. Свертывание критериев и выбор нового компромиссного варианта.

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

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

Для рассматриваемого примера такая функция примет вид:

Получаем:

0.231 · х ₁ + 0.327 · х ₂

и далее поставленная задача должна быть решена.

3. Выбор компромиссного варианта на множестве Паретто по λ критерию осуществляется следующим образом: поскольку матрица значений определяет множество Паретто в пространстве критериев, то текущее значение критерия f_i (x) при всех i находится между f_i и F_i. Вводится показатель, характеризующий степень удаления i критерия от наихудшего значения

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

f_i (x) ≥ f_i + λ ·Δ i, где Δ i = F_i – f_i

Для выполнения требования для каждого критерия необходимо максимизировать удаление всех показателей от их наихудшего значений, для чего вводится единая для всех показателей переменная λ Î [0;1]. Таким образом в рамках выбора оптимального варианта с использованием λ критерия решается задача:

 

λ →max

f_i (x) – λ ·Δ i ≤ f_i, " i

Таким образом, для рассматриваемого примера поиск оптимального решения с помощью λ критерия можно отобразить следующим образом:

В: 30· х ₁ + 60 х₂ – 120 · λ ≥ 330

ЧВ: 10· х ₁ + 40 х ₂ – 130 · λ ≥ 150

П: 10· х ₁ + 4 х ₂ – 50 · λ ≥ 28

х ₁ + 3 х ₂ ≤ 21

2· х ₁ + 3 х ₂ ≤ 24

2· х ₁ + х ₂ ≤ 16

х ₁ ≤ 7

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

Индивидуальное задание к лабараторной работе №3

 

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

 

Необходимо решить многокритериальную задачу для всех ограничений описанных выше, для критериев, которые выбираются по варианту (см. ниже[1]). Для упрощения решения задания необходимо, чтобы все критерии либо максимизировались либо минимизировались (сделать это можно путем добавления знака «-» перед критерием, например, чтобы получить из F₂→min, необходимо чтобы было -F₂→max

 

Номер варианта

1. Критерии F₁→max, F₂→min

2. Критерии F₁→max, F₃→min

3. Критерии F₁→max, F₂→max

4. Критерии F₁→max, F₃→max

5. Критерии F₂→max, F₃→max

6. Критерии F₂→max, F₃→max

7. Критерии F₂→min, F₃→min

8. Критерии F₂→min, F₃→max

9. Критерии F₁→min, F₂→max

10. Критерии F₁→min, F₃→max

СПИСОК ЛИТЕРАТУРЫ

Власов М.П. Моделирование экономических процессов: Учебное пособие/ СПбГИЭУ; М.П.Власов, П.Д. Шимко.- СПб: СПбГИЭУ, 2006.- 387 с.

Дорохина Е.Ю., Халиков М.А. Моделирование микроэкономики. Учебное пособие для вузов / Под общ. ред. Н.П. Тихомирова – М.: Издательство “Экзамен”, 2003. – 224 с.

Конюховский П.В. Математические методы исследования операций в экономике – Спб.: Изд-во “Питер”, 2000. – 208 с.

Кундышева Е.С. Математическое моделирование в экономике: Учебное пособие / Под науч. ред. проф. Б. А. Суслакова. – М.: “Дашков и К^о”, 2004. – 352 с.

Самарский А.А., Михайлов А.П. Математическое моделирование: Идеи. Методы. Примеры. – 2-е изд, испр. – М.: ФИЗМАТЛИТ, 2002. – 320 с.

Таха Х. Введение в исследование операций: В 2-х книгах. Пер. с англ. – М.: Мир, 1985.

Шимко П.Д. Оптимальное управление экономическими системами: Учеб. пособие. – СПб.: Издательский дом “Бизнес-пресса”, 2004. – 240 с.

 

ПРИЛОЖЕНИЕ 1

Санкт-Петербург

 

[1] Для тех у кого вариант больше 10 из своего варианта необходимо вычесть 10.

ОБЩИЕ ПОЛОЖЕНИЯ

Лабораторные работы проводятся в рамках изучения дисциплины “ЭММ в социально-экономических исследованиях” с целью получения студентами навыков и умений в построении, решении и анализе экономико-математических моделей с помощью современных программных средств и вычислительной техники.

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

ПЕРЕЧЕНЬ ТЕМ ЛАБОРАТОРНОГО ПРАКТИКУМА

Таблица 1.1

Номер темы	Наименование тем дисциплины	Темы лабораторных работ
	Системные аспекты моделирования	Построение и решение простейшей линейной модели
	Методология моделирования экономических систем	Исследование межотраслевого баланса
	Информационные аспекты моделирования	Решение многокритериальных задач линейного программирования
	Экономико-математические методы и модели в логистике	Исследование эффективности вовлечения финансовых средств

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

Студенты выполняют лабораторные работы в отведенные аудиторные часы, по каждой лабораторной работе оформляется отчет, образец титульного листа приведен в Приложении 1.

Лабораторные работы по курсу “ЭММ в социально-экономических исследованиях” выполняются на базе MS Excel. Для решения оптимизационных задач необходимо использовать надстройку “Поиск решения”.

ИНСТРУКЦИЯ ПО ИСПОЛЬЗОВАНИЮ MS EXCEL ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМАЛЬНОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

2. Для формирования модели в меню «Данные» выберите команду “Поиск решения ” (справа в Инструментальной панели в блоке «Анализ»):

 

3. В случае отсутвия блока «Анализ» или отсутви кнопки «Поиск решения» необходимо зайти в главное меню MS Excell:

После чего нужно войти в «Параметры Excell»

 

В появившемся окне слева необходимо нажать на кнопку «Настройки»

 

Справа снизу появится поле сосписком, в котором необходимо выбрать «Надстройки Excell» и нажать на кнопку «Перейти»

 

 

В появившемся окне поставить галочку напротив «Пакета анализа» и нажать на кнопку «ОК»

 

4. Далее переходим в «Поиск решения» (см. п. 2)

На экране появится диалоговое окно “Поиск решения” (рис 1):

 

Рис. 1

5. Описание использования диалогового окна “ Поиск решения ”.

5.1. В поле “Установить целевую ячейку” введите адрес или имя ячейки, в которой находится формула целевой функции оптимизируемой модели.

5.2. Выберите режим максимизации или минимизации целевой функции. Возможно установление конкретного значения целевой функции.

5.3. В поле “Изменяя ячейки” укажите диапазон изменяемых ячеек (переменных модели). Изменяемые ячейки должны быть связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.

5.3.1. Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку “Предположить”.

5.4. В поле “Ограничения” введите все ограничения, накладываемые на поиск решения. Использовать клавиши “Добавить”, “Удалить”, “Изменить”. При нажатии клавиш “Добавить” и “Изменить” появляется диалоговое окно “Добавить ограничение” и “Изменить ограничение” (рис.2):

 

Рис. 2

Описание диалогового окна “Добавить ограничение” и “Изменить ограничение”:

5.4.1. “Ссылка на ячейку”

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

5.4.2. “Ограничение”

Служит для задания условия, которое накладывается на значения ячейки или диапазона, указанного в поле “Ссылка на ячейку”. (Правая часть ограничения модели оптимального линейного программирования). Правую часть ограничения можно задать конкретным числом или ссылкой на ячейку. Для линейных задач ограничений на количество граничных условий не налагается.

5.4.3. При задании граничных условий можно использовать следующие операторы:

Оператор Значение

<= меньше или равно

>= больше или равно

= равно

цел целое число (применимо только к изменяемым ячейкам)

бин двоичное (применимо только к изменяемым ячейкам)

5.5 Для запуска поиска решения нажмите кнопку “Выполнить” диалогового окна “Поиск решения”

Для вывода итогового сообщения и найденного решения используется диалоговое окно “Результаты поиска решения” (рис.6):

 

Рис. 5

5.5.1. Чтобы сохранить найденные значения переменных в указанных ячейках, установите переключатель в диалоговом окне “Результаты поиска решения” в положение “Сохранить найденное решение”.

5.5.2. Переключатель “Восстановить исходные значения” служит для восстановления исходных значений влияющих ячеек модели.

5.5.3. “Тип отчета” Служит для указания типа отчета (“Результаты”, “Устойчивость” и/или “Пределы”). Каждый отчет размещается на отдельном листе книги.

5.5.3.1. Отчет “Результаты”.

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

5.5.3.2. Отчет “Устойчивость”.

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

5.5.3.3. Отчет “Пределы”.

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