Решение задач ЛП в табличном редакторе OpenOffice.Org Calc
Для того чтобы решить задачу ЛП в табличном редакторе OpenOffice.org Calc, необходимо выполнить следующие действия:
1) создать экранную форму для ввода условия задачи;
2) ввести исходные данные в экранную форму;
3) ввести зависимости из математической модели в экранную форму;
4) задать ЦФ и ввести ограничения (в окне «Поиск решения»);
5) запустить задачу на решение (в окне «Поиск решения»).
Создание экранной формы и ввод в нее условия задачи
Рассмотрим процесс нахождения оптимального решения с помощью табличного редактора на примере решения транспортной задачи. Экранная форма для ввода условий задачи вместе с введенными в нее исходными данными представлена на рис. 1.
Рис. 1. Ввод исходных данных.
В экранной форме на рис. 1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка в OpenOffice.org Calc. Имя ячейки состоит из буквы, обозначающей столбец, и цифры, обозначающей строку, на пересечении которых находится объект задачи ЛП. Так, например затратам cij по перевозке единицы продукции соответствует диапазон ячеек B13:E16, количеству произведенной поставщиком продукции соответствуют ячейки B9:E9, а количеству продукции, требуемому потребителем, соответствуют ячейки H3:H6. В эти ячейки вносятся данные, соответствующие условию задачи.
Кроме того, для решения задачи необходимы следующие данные, для которых тоже нужно зарезервировать ячейки таблицы:
- объемы продукции xij, перевозимой из каждого пункта производства в каждый пункт потребления – B3:E6;
- суммарные затраты на транспортировку – C18;
- сумма объемов производства на всех m пунктах-поставщиках – F9;
- сумма объемов потребления на всех n пунктах-потребителях – H7;
- объемы продукции, поступившей потребителям – G3:G6;
- объемы продукции, отгруженной поставщиками – B8:E8.
Ввод зависимостей из математической модели в экранную форму
Для вычисления объемов отгруженной и поступившей, а также суммарных объемов требуемой и имеющейся продукции, используется функция суммирования SUM() со ссылкой на соответствующие ячейки (рис. 2). Для вычисления суммарных затрат на перевозку нужно воспользоваться мастером функций (рис. 3). В окне мастера выбирается нужная функция, в данном случае SUMPRODUCT(), которая возвращает сумму произведений соответствующих элементов заданных массивов – матрицы перевозок и матрицы затрат на перевозку.
Рис. 2. Ввод формул.
Рис. 3. Мастер функций.
Поиск решения
После ввода исходных данных и зависимостей приступаем к решению задачи. Для этого в меню Сервис выбирается пункт Поиск решения (рис 4).
Рис. 4. Поиск решения.
В окне решателя делаются следующие установки:
- ссылка на целевую ячейку и результат оптимизации – минимум для транспортной задачи;
- ссылка на изменяемые ячейки – матрицу перевозок;
- ввод ограничительных условий в соответствии с изложенным выше описанием математической модели транспортной задачи.
Последний шаг – запуск задачи на решение – производится с помощью кнопки «Решить». В результате получаем вычисленное оптимальное значение суммарных затрат на перевозку (рис. 5).
Рис. 5. Результат решения транспортной задачи.
Порядок выполнения работы
1. Согласно номеру своего варианта (табл. 1), сформулируйте условия задач и постройте их модели.
2. Найдите оптимальное решение задач в OpenOffice.org Calc.
3. Оформите отчет по лабораторной работе, который должен содержать: титульный лист; экранные формы, демонстрирующие математические модели задач и процесс их решения; результаты решения задач.
Таблица 1
| № вари-анта | Оптимизация | ||
| Распределение ресурсов (ИхР)* | Транспортная задача (ПхПотр)* | График занятости (ДхГ)* | |
| 3х6 | 4х5 | 10х3 | |
| 3х6 | 5х4 | 10х3 | |
| 4х5 | 3х6 | 10х3 | |
| 4х5 | 6х3 | 10х3 | |
| 5х4 | 3х6 | 10х3 | |
| 5х4 | 6х3 | 10х3 | |
| 6х3 | 4х5 | 10х3 | |
| 6х3 | 5х4 | 9х4 | |
| 3х6 | 4х5 | 9х4 | |
| 3х6 | 5х4 | 9х4 |
Продолжение табл. 1
| 4х5 | 3х6 | 9х4 | |
| 4х5 | 6х3 | 9х4 | |
| 5х4 | 3х6 | 9х4 | |
| 5х4 | 6х3 | 9х4 | |
| 6х3 | 4х5 | 8х5 | |
| 6х3 | 5х4 | 8х5 | |
| 3х6 | 4х5 | 8х5 | |
| 3х6 | 5х4 | 8х5 | |
| 4х5 | 3х6 | 8х5 | |
| 4х5 | 6х3 | 8х5 | |
| 5х4 | 3х6 | 8х5 | |
| 5х4 | 6х3 | 7х6 | |
| 6х3 | 4х5 | 7х6 | |
| 6х3 | 5х4 | 7х6 | |
| 3х6 | 4х5 | 7х6 | |
| 3х6 | 5х4 | 7х6 | |
| 4х5 | 3х6 | 7х6 | |
| 4х5 | 6х3 | 7х6 |
* Обозначения: И – количество типов изделий; Р – количество типов ресурсов; П – количество поставщиков; Потр – количество потребителей; Д – количество дней в смене; Г – количество групп.
Лабораторная работа № 2.
«Решение задач прогнозирования с помощью табличного процессора»
Цель работы
Приобретение навыков использования в OpenOffice.org Calc математических методов прогнозирования.
Методы прогнозирования
Прогнозирование является одной из главных и наиболее востребованных экономических задач. Основная причина этого в том, что, зная характер развития событий в будущем, можно принимать более обоснованные управленческие решения.
Данные, собираемые и используемые для разработки прогнозов, чаще всего представляют собой временной ряд, то есть последовательность наблюдений за изменениями во времени значений параметров некоторого объекта или процесса. Эти значения фиксируются в некоторые, обычно равностоящие, моменты времени, называемыми моментами отсчета, или периодами. Интервал между отсчетами зависит от степени детальности анализа, например, неделя, день, месяц и т. д. Все временные отсчеты нумеруются в порядке возрастания и представляются в следующем виде: Y = {y1, y2, y3,…, yt}.
Скользящее среднее и экспоненциальное сглаживание
Самой простой моделью прогнозирования, основанной на простом усреднении является:
Pt+1 = (Yt + Yt-1 + … + Y1)/t,
где t – количество периодов наблюдений за параметром Y, Pt+1 – прогноз значения параметра на период t+1.
В приведенной выше формуле предполагалось, что ряд усредняется по достаточно длительному интервалу времени. Однако, как правило, значения временного ряда из недалекого прошлого лучше описывают прогноз, чем более старые значения этого же ряда. Тогда можно использовать для прогнозирования скользящее среднее:
Pt+1 = (Yt + Yt-1 + … + Yt-n-1)/n,
Где n – количество периодов скользящего среднего.
Смысл его заключается в том, что модель видит только ближайшее прошлое на n отсчетов по времени в глубину и, основываясь только на этих данных, строит прогноз.
При прогнозировании довольно часто используется метод экспоненциального сглаживания, который постоянно адаптируется к данным за счет новых значений. Формула, описывающая эту модель записывается так:
Pt+1 = (1-k)×Yt + k×Pt ,
где Pt+1 – прогноз на следующий период времени, Yt – реальное значение в момент времени t, Pt – прошлый прогноз на момент времени t, k – коэффициент, называемый фактором затухания (0£k£1)). Если значения прогноза на предыдущий период не существует, то текущий прогноз повторяет реальное значение на предыдущий период, т.е. P2 = Y1.
В этом методе есть внутренний параметр k, который определяет зависимость прогноза от более старых данных, причем влияние данных на прогноз экспоненциально убывает с «возрастом» данных.
Описанные выше модели используются при бизнес-прогнозировании в не очень сложных ситуациях, например, при прогнозировании продаж на спокойных и устоявшихся рынках.
Регрессионные методы прогнозирования
Наряду с описанными выше методами, уже достаточно долгое время для прогнозирования используются регрессионные алгоритмы. Коротко суть алгоритмов такого класса можно описать так.
Существует прогнозируемая переменная Y (зависимая переменная) и отобранный заранее комплект переменных, от которых она зависит – X1, X2, ..., XN (независимые переменные). Природа независимых переменных может быть различной. Например, если предположить, что Y – уровень спроса на некоторый продукт в следующем месяце, то независимыми переменными могут быть уровень спроса на этот же продукт в прошлый и позапрошлый месяцы, затраты на рекламу, уровень платежеспособности населения, экономическая обстановка, деятельность конкурентов и многое другое. Главное - уметь формализовать все внешние факторы, от которых может зависеть уровень спроса, в числовую форму.
Модель множественной регрессии в общем случае описывается выражением:
Y = F(X1, X2, ..., XN) + e
Здесь – вид функции, показывающей зависимость зависимой переменной от независимых. В более простом варианте линейной регрессионной модели эта зависимость имеет вид:
Y = b0 + b1X1 + b2X2 +, ...,+ bN XN + e,
где b0, b1, b2,..., bN – подбираемые коэффициенты регрессии, e –
компонента ошибки. Предполагается, что все ошибки независимы и нормально распределены. С помощью таблицы значений прошлых наблюдений можно подобрать (например, методом наименьших квадратов) коэффициенты регрессии, настроив тем самым модель.
Помимо линейной, существуют другие виды регрессионных моделей: степенная, логарифмическая, экспоненциальная и т.д.
OpenOffice.org Calc
Для того чтобы решить задачу прогнозирования в табличном редакторе OpenOffice.org Calc, необходимо выполнить следующие действия:
1) ввести временной ряд наблюдаемого параметра;
2) ввести зависимости из математической модели в экранную форму;
3) проиллюстрировать наблюдения и полученные прогнозные значения с помощью диаграмм.
Ввод наблюдений и зависимостей
Рассмотрим процесс прогнозирования с помощью табличного редактора на примере модели скользящего среднего. Для ввода наблюдаемого параметра и функциональных зависимостей создается таблица, первый столбец которой отводится под обозначения периодов (номера, дни недели, названия месяцев и т.д.), второй – под сам наблюдаемый параметр, последующие – под прогнозы. Вычисление прогнозных значений производится путем ввода в соответствующие ячейки функции, вычисляющей среднее значение, например, AVERAGE() из мастера функций (рис. 6).
Готовой функции для вычисления прогноза по методу экспоненциального сглаживания нет. Формула вводится непосредственно в ячейку в режиме ее редактирования в соответствии с правилами создания формул.
Для регрессионных моделей предварительных вычислений делать не нужно. В данной работе исследуется зависимость наблюдаемого параметра только от времени, т.е. номера периода.
Рис. 6. Вычисление прогноза методом скользящего среднего
Создание диаграмм и линий трендов
Для демонстрации степени близости прогнозных и реальных значений используется их графическое представление с помощью диаграмм. Для этого в меню Вставка выбирается пункт Диаграмма, и далее на каждом из шагов ее создания вводятся и выбираются соответствующие установки и параметры. В результате получаем окончательно оформленную иллюстрацию создания прогноза с помощью метода скользящего среднего (рис. 7).
Создание прогнозов с помощью регрессионных моделей осуществляется непосредственно на построенных по реальным значениям диаграммах (рис. 8). Для этого нужно двойным щелчком активировать диаграмму, затем вызвать контекстное меню к линии наблюдаемого параметра и выбрать пункт Вставить линию тренда. В появившемся окне выбирается тип линии тренда, т.е. регрессионной модели, а также установки показа уравнения регрессии.
Рис. 7. Создание диаграммы
Рис. 8. Создание линии тренда
Порядок выполнения работы
1. Создайте в OpenOffice.org Calc временной ряд наблюдаемого параметра размером в 20-25 значений.
2. Согласно номеру своего варианта (табл. 2), найдите прогнозируемые значения, используя все перечисленные методы.
3. Оформите отчет по лабораторной работе, который должен содержать: титульный лист; экранные формы, демонстрирующие применение каждого из методов прогнозирования.
Таблица 2
| № вари-анта | Прогнозирование | ||
| Тип линии тренда | Количество интервалов скользящего среднего | Факторы затухания экспоненциального сглаживания | |
| Линейная линия тренда и любые 2 типа линий на выбор | 2 и любой на выбор | 0,7 и любой на выбор | |
| 3 и любой на выбор | 0,6 и любой на выбор | ||
| 4 и любой на выбор | 0,5 и любой на выбор | ||
| 5 и любой на выбор | 0,4 и любой на выбор | ||
| 2 и любой на выбор | 0,3 и любой на выбор | ||
| 3 и любой на выбор | 0,7 и любой на выбор | ||
| 4 и любой на выбор | 0,6 и любой на выбор | ||
| 5 и любой на выбор | 0,5 и любой на выбор | ||
| 2 и любой на выбор | 0,4 и любой на выбор | ||
| 3 и любой на выбор | 0,3 и любой на выбор | ||
| 4 и любой на выбор | 0,7 и любой на выбор | ||
| 5 и любой на выбор | 0,6 и любой на выбор | ||
| 2 и любой на выбор | 0,5 и любой на выбор | ||
| 3 и любой на выбор | 0,4 и любой на выбор | ||
| 4 и любой на выбор | 0,3 и любой на выбор | ||
| 5 и любой на выбор | 0,7 и любой на выбор | ||
| 2 и любой на выбор | 0,6 и любой на выбор | ||
| 3 и любой на выбор | 0,5 и любой на выбор | ||
| 4 и любой на выбор | 0,4 и любой на выбор | ||
| 5 и любой на выбор | 0,3 и любой на выбор | ||
| 2 и любой на выбор | 0,7 и любой на выбор | ||
| 3 и любой на выбор | 0,6 и любой на выбор | ||
| 4 и любой на выбор | 0,5 и любой на выбор | ||
| 5 и любой на выбор | 0,4 и любой на выбор | ||
| 2 и любой на выбор | 0,3 и любой на выбор | ||
| 3 и любой на выбор | 0,7 и любой на выбор | ||
| 4 и любой на выбор | 0,6 и любой на выбор | ||
| 5 и любой на выбор | 0,5 и любой на выбор |
Рекомендуемая литература
1. Автоматизированные информационные технологии в экономике / Под. ред. Титоренко Г.А. – М.: ЮНИТИ-ДАНА, 2002.
2. Курицкий, Б. Я. Поиск оптимальных решений средствами Excel 7.0.-С-П.:BHV, 1997.-384с.:ил.
3. Компьютерные технологии обработки информации: Учеб. пособие / С.В.Назаров, В.И.Першиков, В.А.Тафинцев и др.; под. ред. С.В. Назарова. - М.: Финансы и статистика, 1995. - 248с. :ил.
4. Макарова, Н. В. Информатика: Учебник / под ред. проф. Н. В. Макаровой. – М.: Финансы и статистика, 1997.–768 с.:ил.
5. Уткин, В. Б. Информационные системы и технологии в экономике: Учебник для вузов / В. Б. Уткин, К. В. Балдин. – М.: ЮНИТИ–ДАНА, 2003. – 335 с.