Работа с оптимизатором

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

КЫРГЫЗСКОЙ РЕСПУБЛИКИ

КЫРГЫЗСКИЙ ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА ПРИКЛАДНОЙ ИНФОРМАТИКИ

Курсовая работа

ИНФОРМАЦИОННЫЙ МЕНЕДЖМЕНТ

Работа с оптимизатором

Бишкек – 2007

Работа с оптимизатором для задач оптимального размещения производства

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

 

Постановка задачи

Требуется найти максимальное или минимальное значение следующей линейной формы:

, при следующих ограничениях:

 или в скалярной форме:

Данная задача (если существует решение) решается симплексным методом.

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

Для решения данной задачи с использованием компьютерных технологий в MS EXCEL существует программа-оптимизатор SOLVER (поиск решений). Она позволяет эффективно находить решения для задач линейного программирования со многими переменными.

Пример 1: Задача об оптимальном планировании производства.

Имеется два вида деталей в количестве 8 и 24 единиц, из которых изготавливаются два вида изделий. На единицу 1-го вида изделий расходуется деталей первого вида в количестве 2 и второго - 4, а второго вида изделий – 1 и 6 единиц деталей. Цена первого изделия 4 тыс. сомов, второго – 5 тыс. сомов. Отсюда возникает задача, в каких количествах следует изготавливать изделия, чтобы обеспечить максимальную выручку от их продажи?

Построим математическую модель этой задачи.

Обозначим через Х₁ и Х₂ числа производимых изделий первого и второго видов, тогда расход деталей 1-го вида равен (2Х₁ + Х₂), второго вида - (4Х₁ +6Х₂) , доход от их реализации – (4Х₁ +5Х₂).

Учитывая ограничения на используемые материалы, сформулируем задачу:

Z_max = 4Х₁ +5Х₂ , при ограничениях (1)

2Х₁ + Х₂ ≤ 8, 4Х₁ +6Х₂ ≤ 24, Х₁ ≥ 0, Х₂ ≥ 0.

Решение этой задачи с помощью оптимизатора SOLVER программы EXCEL. Если в меню «Сервис» нет подпункта «Поиск решения», то при нажатии пункта «Надстройка» из этого же меню, получим следующее окно надстройки:

 

В этом окне отмечаем «галочкой» строку «Поиск решения» и нажимаем мышью кнопку ОК. Далее из пакета Microsoft Office устанавливается программа и соответствующие файлы для поиска решения.

На EXCELе в первых двух строках назначаем столбцы для переменных Х₁, Х₂ (т.е. шапки столбцов), как показано на след.рис:

В третьей строке по адресу А3 и В3 вводим начальные значения переменных Х₁, Х₂ , которые равны нулю. По адресу В4 вводим выражение целевой функции (1): =4*А3+5*В3. Далее в ячейку А6 и А7 вводим формул ограничений из (1): =2*А3+В3 и =4*А3+6*В3 соответственно. А в ячейки В6 и В7 вводим конечные значения 8 и 24 соответственно переменных Х₁, Х_2.

Как формулы заполняются показано на следующем рисунке:

Затем ставим курсор в ячейку В4 (т.е. ячейка целевой функции) и выбираем из меню «Сервис» пункт «Поиск решения», тогда открывается следующее окно

Если в окошечке "Изменяя ячейки" будет пусто, то нажимая это окошечко мышкой устанавливаем курсор, затем мышкой отмечая ячейку А3 и В3 (не отпуская мышку) получим вышеприведенное окно.

Теперь нажимаем мышкой кнопку "Добавить" и всплывает следующее окно оптимизатора:

После чего мышкой нажимая ячейку А3 протягиваем курсор мышкой до ячейки В3 не отпуская курсор, т.е. отмечаем ячейки А3 и В3, затем отпускаем кнопку мышки и получим следующее окно:

В этом окне выбираем знак >= , а в правом окошке "Ограничение" ставим клавиатурой значение 0 (ноль). Вид окна примет, следующий вид:

То есть мы таким образом вводим ограничение Х₁ ≥ 0, Х₂ ≥ 0 из (1). Затем нажимаем кнопку "ОК" и тогда мы получим следующее окно:

Далее, аналогично нажимая кнопку "Добавить" получим окно "Добавление ограничения", затем мышкой (не отпуская левую мышку) отмечаем ячейки А6 и А7. Потом отпуская мышку подводим курсор к окошку "Ограничение" и нажимая мышку ставим курсор в этой окошке. После чего мышкой отмечаем ячейки В6 и В7.

В этом окошке нажимая кнопку "ОК" добавляем это ограничение в окно оптимизатора:

Теперь мы все ограничения (1) ввели в окно оптимизатора. Нажимая далее кнопку "Выполнить" получаем оптимальное решение заданной задачи:

Из этого окна оптимизатора видно, что оптимальным решением являются Х₁ =3, Х₂=2, при них достигается максимальное значение целевой функции Z=22.

 

Пример 2: Решение транспортной задачи с помощью оптимизатора. Математическая модель транспортной задачи сводится к минимизации линейной формы:

 

где С_ij – стоимость доставки единицы груза из i-го пункта отправления в j-ый пункт назначения,

Х_ij– количество единиц груза, запланированных к перевозке из i-го пункта в j-й,

А_i- количество груза в i-том пункте отправления,

В_j - количество груза в j-том пункте назначения.

Необходимым и достаточным условием разрешимости транспортной задачи является условие:

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

Решаем задачу с использованием программы Microsoft EXCEL. Для решения транспортной задачи с помощью оптимизатора «Поиск решения» введем данные как показано ниже на рисунке. Из рисунка видно, что вместо переменных В_j из вышестоящей таблицы используются имена столбцов EXCEL: A-E, а вместо переменных А_iиспользуются номера строк от 1 и далее.

В ячейки А1:Е4 введем стоимость перевозок. Ячейки А6:Е9 отведены под значения объемов перевозок, пока неизвестных, но в этих ячейках после решения оптимизатора появятся оптимальный план перевозок. В ячейки G6:G9 введены объемы производства или запасы продукции на складах, а в ячейках А11:Е11 введены потребности (спрос) в продукции в пунктах потребления (или торговые точки).

В ячейку F10 вводится целевая функция: =СУММПРОИЗВ(А1:Е4; А6:Е9), как показано на след. рисунке:

В ячейки А10:Е10 вводятся формулы: А10 → = СУММ (А6:А9)

В10 → = СУММ (В6:В9)

С10 → = СУММ (С6:С9)

D10 → = СУММ (D6:D9)

Е10 → = СУММ (Е6:Е9)

определяющие объемы продукции, ввозимые в пункты потребления (реализации).

В ячейки F6:F9 вводятся формулы:

F6 → = СУММ (А6:Е6)

F7 → = СУММ (А7:Е7)

F8 → = СУММ (А8:Е8)

F9 → = СУММ (А9:Е9)

характеризующие объем производства (или наличие на складах).

Далее ставим курсор в ячейку целевой функции (F10) выбираем команду «Поиск решения» из меню «Сервис» и заполняем открывшееся диалоговое окно «Поиск решения», как показано ниже:

В окошке «Установить целевую ячейку» должен быть абсолютный адрес целевой функции $F$10. Так как нам нужно минимальное значение целевой функции F10, т.е. сумма произведений объема перевозок продукции на стоимости перевозок между пунктами должно быть минимальным, поэтому выбираем мышкой вариант «минимальному значению».

В окошке «Изменяя ячейки:» вводим абсолютные адреса ячеек $А$6:$Е$9, т.е. в этих ячейках объемы перевозок продукции будут изменяться с учетом ограничений, пока значения в этих ячейках равны нулю.

В окошке «Ограничения» вводим ограничения, которые были заданы в начале примера, т.е. значения ячеек А6:Е9, т.е. объемы перевозок продукции должны быть >=0, значения ячеек А10:Е10, т.е. по каждому потребителю продукции должны быть равны потребностям пунктов реализации, которые находятся в А11:Е11. Суммы объемов перевозок произведенных продукций по каждому производителю (или запасы на каждом сладе) в F6:F9 должны быть равны значениям G6:G9.

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

 

В этом окошке отмечаем «галочкой» пункт «Линейная модель» и нажмем кнопку «ОК».

Далее в предыдущем рисунке нажав кнопку «Выполнить» получим следующий рисунок-окно:

На этом рис. Видно, что найдено оптимальное решение: оптимальные объемы перевозок приведено в ячейках А6:Е9, а оптимальное значение целевой функции дано в ячейке F10 равной значению 1430

Подбор параметра для решения задач моделирования

В экономике чаще используется математическое моделирование с помощью описания экономических задач математическими зависимостями.

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

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

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

Здесь мы рассмотрим решения моделей описываемых уравнением

(1)

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

 

Пример 3. Решить уравнение:

 (2)

Нам известно, что это уравнение имеет единственное решение и оно расположено на отрезке [-1; 0]. В качестве начального значения можно выбирать любую точку отрезка. Мы положим начальное значение  и поместим ее в ячейку В2 на листе EXCEL, а в ячейку В3 вводим функцию  и тем самым получая в этой ячейке ее значение.

В ячейку А2 введем текстовое выражение «х=», а в ячейки А1 и А3 соответственно введем следующие текстовые строки: «Начальное значение аргумента» и «Значение функции» и получим следующее окно в EXCELе:

Далее выделив ячейку В3 мышкой, где хранится значение функции, используем команду «Подбор параметра» из меню «Сервис» главного меню EXCEL.

Тогда получим следующее окно на EXCELе:

В этом окне в ячейке «Установить в ячейке» вводим адрес В3, где хранится значение функции, а в ячейку «Значение» вводим начальное значение аргумента клавиатурой равное 0 и наконец в ячейке «Изменяя значение ячейки» нажимаем мышкой а затем нажимаем на ячейке В2 т.е. введем адрес значения переменной аргумента как показано на рисунке слева.

После этого нажимаем мышкой кнопку «ОК» и получим следующее окно:

В этом окне видно, что мы получили значение аргумента в ячейке В2 = -0,56714, а в ячейке В3 округленное значение функции 7,59Е-06, а в правом окне приведено точное значение функции с 5- знаками после запятой как «Текущее значение: 7,58615Е-06.

Итак, мы получили более точное решение уравнения (2) и соответствующее ему более точное значение функции.

 

Численные методы решения систем линейных алгебраических уравнений на EXCELе

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

Min <c, x>

X Є R₁ (1)

где R₁ = { x: Ax ≤ b, x ≥ 0 }

Задачу (1) приводим к каноническому виду: , где новые вспомогательные переменные. Здесь множество R₁ представляет множество с угловыми точками, являющимися решениями системы уравнений:

а₁₁х₁ + а₁₂х₂ + … + а_1nх_n + u₁ =b₁,

а₂₁х₁ + а₂₂х₂ + … + а_2nх_n + u₂ =b₂, (2)

а_m1х₁ + а_m2х₂ + … + а_mnх_n + u_m=b_m

Как известно, решения задач вида (1) лежат в угловых точках множества R₁ , которых необходимо вычислить.

Из курса алгебры известно, что такие системы уравнений вида (2) мы можем решать следующими методами а) метод Крамера; б) метод Обратной матрицы; 3) метод Гаусса.

Мы рассмотрим решение систем линейных алгебраических уравнений методом Гаусса в предположении, что m=n, т.е. число уравнений и неизвестных совпадают.

Пример 4: Решаем систему уравнений методом Гаусса:

х₁ + 3х₂ -2х₃ - х₄ =-3,

2х₁ - 4х₂ + х₃ + х₄ = 1, (2)

х₁ + х₂ - 3х₃ + 2х₄ = 0,

3х₁ + х₂ - 2х₃ + х₄ = 3

Откроем окно EXCEL. В диапазоны ячеек А1:D4 введем матрицы коэффициентов системы (2), а в – Е1:Е4 значения столбца свободных членов, как показано справа:

Содержимое ячеек А1:Е1 скопируем в ячейки А6:Е6, А11:Е11 и А16:Е16. В диапазон ячеек А7:Е7 введем формулу:

=А2:Е2-$A$1:$E$1*(A2/$A$1) обращающая в нуль коэффициент х₁ во втором

уравнении системы. Выделим диапазон А7:Е7 и протащим маркер заполнения этого диапазона так, чтобы заполнить диапазон А7:Е9. Это действие обратит в нуль коэффициент х₁ в третьем и четвертом уравнениях системы (см. рис. выше).

Теперь скопируем значения из диапазона ячеек А7:Е7 в диапазоны А12:Е12 и А17:Е17.

Для копирования значений без формул выделяем мышкой диапазон А7:Е7, затем из меню «Правка» нажимаем «Копировать», после этого мышкой выделяем диапазон А12:Е12 (куда мы должны вставить значения), а теперь из меню «Правка» выбираем подменю «Специальная вставка» и в открывшемся диалоговом окне «Специальная вставка» в группе «Вставить» установим переключатель в положение «Значения» и нажимаем кнопку «ОК».

В диапазон ячеек А13:Е13 вводим формулу: =А8:Е8-$A$7:$E$7*(B8/$B$7).

Результаты преобразований приведены на рисунке выше. Выделим диапазон ячеек А13:Е13 и протащим маркер заполнения этого диапазона так, чтобы заполнить диапазон ячеек А13:Е14, в результате чего вышеуказанная формула обращает в нуль коэффициенты х₂ в третьем и четвертом уравнениях системы.

Копируем значения из диапазона ячеек А12:Е12 в диапазон А18:Е18. В диапазон ячеек А19:Е19 вводим формулу: =А14:Е14-$A$13:$E$13*(С14/$С$13), которая обращает в нуль коэффициент при х3 в четвертом уравнении системы. Прямая прогонка метода Гаусса завершена.

Обратная прогонка заключается во вводе в диапазоны G4, G3; G2 и G1 соответственно следующих формул:

 = E19/D19

=(E18-D18*G4)/C18 (3)

=(E17-C17*G3-D17*G4)/B17

=(E16-B16*G2-C16*G3-D16*G4)/A16

В диапазоне ячеек: G1:G4 будет получено решение системы (2):

х₁=1, х₂=2, х₃=3, х₄=4.

Пример 5: Решаем систему уравнений (2) методом вычисления обратной матрицы. Введем матрицу коэффициентов в ячейки А1:D4 и столбец свободных членов системы (2) в ячейки F1:F4 в таблицу EXCEL, как показано ниже на рис:

 

Для вычисления обратной матрицы выделим мышкой диапазон А6:D9, затем нажимаем из меню «Вставка» подменю «Функция», после чего появляется окно «Мастер функций» и в нем в строке «Категория» выбираем «Математическое» а в нижнем окошечке выбираем функцию «МОБР» и получим след. вид экрана:

В этом окошке далее нажимаем кнопку «ОК», после этого появится следующее окошко ввода аргумента функции и далее мышкой выбираем диапазон А1:D4, как показано на след. рисунке:

После этого в этом окошке нажимаем кнопку «ОК» и тогда ячейка А6 будет иметь следующий вид:

Затем нажимаем кнопку F2, тогда вид экрана примет следующий вид:

Далее нажимаем три следующие клавиши «Ctrl+Shift+ Enter» одновременно и получим значения коэффициентов обратной матрицы, приведенных ниже:

Далее вводим в ячейки А11:А14 названия переменных: Х1-Х4, затем отмечаем мышкой ячейки В11:В14, в которых будут вычисленные значения переменных Х1-Х4, введем формулу умножения значения коэффициентов обратной матрицы на вектор значений свободных членов. Для этого выделяем ячейки В11-В14, затем из меню «Вставка» выберем пункт подменю «Функция», в строке «Категория» выбираем «Математическое» а в нижнем окошечке выбираем функцию «МУМНОЖ» и получим след. вид экрана как показано в следующем рисунке:

Далее в этом окошке нажимаем кнопку «ОК» и получим окошко «Аргументы функции». В этом окошке в строке «Массив1» ставим курсор, затем выбираем мышкой диапазон значений обратной матрицы А6:D9 а в строке «Массив2» ставим курсор, затем выбираем мышкой диапазон значений свободных членов F1:F4, как показано на следующем рисунке:

В этом окошке нажимаем кнопку «ОК» и получим вид экрана:

Далее нажимаем кнопку F2 и после нажимаем три кнопки «Ctrl+Shift+Enter» одновременно и получим решение уравнения (2) в виде значений Х1-Х4 в ячейках В11:В14, как показано на след. рисунке:

 

Здесь можно проверить найденные значения Х1-Х4 умножив матрицу коэффициентов А1:D4 на матрицу обратных значений А6:D9 с помощью функции =МУМНОЖ(A1:D4;A6:D9), тогда получим единичную матрицу, где элементы по диагонали равны 1, а остальные члены равны 0. Это означает, что найденные значения обратной матрицы верные. Для этого отмечаем диапазон F6:I9, затем из меню «Вставка» выберем пункт подменю «Функция», и в окошке «Мастер функций» в строке «Категория» выбираем «Математическое» а в нижнем окошечке выбираем функцию «МУМНОЖ», после этого в окошке «Аргументы функции» и в строке «Массив1» выбираем диапазон А1:D4 а в строке «Массив2» выбираем диапазон А6:D9. И наконец нажимая F2 и затем «Ctrl+Shift+Enter» одновременно получим следующий вид экрана, где в диапазоне F6:I9 получили единичную матрицу:

 

Корреляционно – регрессионный анализ

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

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

Известны два типа связей: функциональные и регрессионные.

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

Уравнение регрессии составляется исследователем на основе характера связи между функцией и аргументами. Вопрос о форме связи решается, как правило, поэтапно.

 

Линейная форма связи

Широкое распространение в практике математического моделирования получило уравнение регрессии вида:

у=f(x),

где х - величина, рассматриваемая как случайная независимая переменная;

у - случайная зависимая величина.

При линейной форме связи эту зависимость можно выразить уравнением прямой:

у = в₀ + в₁х (1)

Для ее построения требуется провести N экспериментов, в каждом из которых должна фиксироваться пара значений (x_i ; y_i). Результаты экспериментов представляются либо в виде таблицы, либо в виде графика.

Значение фактора xi	х1	х2	…	хi	…	хn
Значение фактора yi	y1	y2	…	yi	…	yn

Наша задача состоит в том, чтобы вычислить коэффициенты в₀ и в₁.

, (2)

, (3)

В качестве меры зависимости между случайными величинами используется коэффициент корреляции, определяемый по формуле:

(4)

Если случайные величины x и y независимы, то r = 0, если связь между y и x функциональная, то r = │1│.

 

Пример. В результате эксперимента зафиксированы пары значений (x_i,y_i) приведенные в таблице:

x_i 1 3 2 5 2 5 6 2 3 6 4 1 3 4 6 5 1 4

y_i 3 5 3 4 3 6 7 2 3 8 6 2 4 4 8 6 1 5

Построить уравнение регрессии вида у = в₀ + в₁х. Решение.

Для вычисления коэффициентов уравнения регрессии составляем статистическую таблицу. По вычисленным суммам определяем:

b₀ = (80*273 – 336*63)/(18*273-63²) = 0,71;

b₁ = (18*336 – 63*80)/(18*273-63²) = 1,07;

Тогда уравнение регрессии будет иметь вид: у = 0,71 + 1,07х.

 

Определяем коэффициент корреляции:

= 0,987,

Отсюда следует, что y и x тесно связаны друг с другом, т.к. коэффициент корреляции близок к единице.