Математическая постановка задачи оптимизации




Матричные операции

Матрицей размера m * n называется прямоугольная таблица чисел, содержащая m строк и n столбцов.

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

· МУМНОЖ(М 1, М 2) – Количество столбцов матрицы М 1 должно быть равно количеству строк матрицы М 2. Результатом является матрица М = М 1* М 2, т.е. произведение матриц М 1 размера m * n и М 2 размера n * p; размер матрицы М равен m * p.

· ТРАНСП(М) – Результатом является матрица М Т размера n * m, получающаяся транспонированием матрицы М размера m * n. При транспонировании i -тая строка матрицы М становится i -тым столбцом матрицы М Т.

· МОБР(М) – Результатом является матрица М -1, обратная квадратной матрице М. Обе матрицы имеют один и тот же размер. Обратная матрица существует тогда и только тогда, когда определитель исходной матрицы отличен от нуля.

· МОПРЕД(М) – Результатом является число – определитель квадратной матрицы М.

Особенность применения матричных операций в Excel следующая:

Если результатом формулы является матрица размера m * n, которая должна быть помещена в диапазон такого же размера, то

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

2. введите формулу в строке формул,

3. закончите ввод формулы нажатием комбинации клавиш CTRL+SHIFT+ENTER (формула при этом будет взята в фигурные скобки {}).

Если Вы неправильно выделили диапазон или нажали просто ENTER, но формулу ввели правильно, то

1. выделите диапазон для результата (он должен содержать ячейку с формулой),

2. щёлкните в строке формул (там должна быть требуемая формула),

3. нажмите CTRL+SHIFT+ENTER.


Задание 1 (типовое). Оптимальное планирование выпуска
продукции при ограниченных ресурсах

Целью данной задачи является нахождение такого плана выпуска продукции, при котором была бы достигнута максимальная прибыль от её реализации. Естественным ограничением роста производства и прибыли является ограниченность запасов сырья, комплектующих, трудовых и других ресурсов, которые можно использовать. При широкой номенклатуре продукции и большом разнообразии используемых ресурсов задача может оказаться слишком сложной для людей. На помощь приходят математические методы и информационные технологии – программа Поиск решения (Solver), входящая в Excel.

Математическая постановка задачи оптимизации

 

В рассмотренной выше задаче планирования выделим следующие параметры:

Xi – искомое плановое задание производства i -го продукта; полный план – это вектор X = á X 1, X 2, …, Xm ñ, который в данной задаче является независимым внутренним параметром, значения которого нужно найти;

Pi – прибыль (profit) на единицу i -го произведённого и реализованного продукта; вектор P = á P 1, P 2, …, Pm ñ представляет внешние условия рынка и задаётся соответствующими числами;

Pr – общая прибыль от реализации запланированного объёма продукции – внутренний (зависимый) параметр задачи, полностью определяемый параметрами X и P: Рr = , или в терминах Excel Рr = СУММПРОИЗВ(X; P) – это и есть формула, вносимая в ячейку параметра Рr;

Bj – ограниченный (boundary) запас j -го ресурса; вектор B = á B 1, …, Bn ñ в данной задаче представляет внешние условия, ограничивающие возможности производства;

Rij – норма (rate) расхода j -го ресурса на единицу i -го продукта; матрица R = ║ Rij представляет технологические условия производства и в данной задаче является внешним параметром, позволяющим определить потребность ресурсов для выполнения предложенного плана;

Cj – сумма расхода (consumption) j -го ресурса на весь запланированный объём продукции; вектор C = á C 1, …, Cn ñ – это внутренний (зависимый) параметр, полностью определяемый параметрами X и R: Cj = ; с помощью матричных операций это можно записать, как C = ХT * R, или в терминах Excel: C = МУМНОЖ(ТРАНСП(Х); R).

Сформулированная модель позволяет, задав некоторые значения независимых внутренних параметров (в примере – плана X), вычислить значения зависимых внутренних параметров (в примере – расхода C и прибыли Рr). Но задача требует, чтобы внутренние параметры удовлетворяли некоторым ограничениям, диктуемым внешними условиями через внешние параметры задачи.

Excel допускает использование ограничений следующего вида:

Yk = Zk, Yk £ Zk, YkZk,

где Yk – параметр (т.е. адрес соответствующей ячейки или диапазона), а Zk – число или параметр. Допускаются также ограничения вида «Yk = целое», или в векторной форме Y = целое.

В нашей задаче планирования можно сформулировать следующие ограничения:

1. Расходы ресурсов не должны превосходить запасов, т.е. Cj £ Bj, или в векторной форме C £ B.

2. Объём планируемой продукции должен быть неотрицательным, т.е. Xi ≥ 0, или в векторной форме X ≥ 0.

3. Если объём продукции измеряется в целых числах, то добавляется векторное ограничение X = целое.

В нашей задаче целевым параметром является ожидаемая прибыль Pr от реализации всей запланированной продукции, а критерий оптимизации имеет вид Prmax, т.е. решается задача максимизации прибыли. Целевой функцией является СУММПРОИЗВ(X; P) – формула в ячейке Pr.

Задача оптимизации может иметь одно, много или ни одного решения. Бывают случаи, когда Excel не может найти решение, даже если оно существует (например, из-за ограниченности отведённого времени). Завершив работу, Solver даёт один из трёх ответов:

1. «решение найдено»,

2. «решения не существует» и

3. «решение не найдено из-за ограничения времени».

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

Для начала решения задачи Solver требует задание каких-нибудь значений изменяемых (т.е. искомых) параметров (в нашем примере это вектор X). Эти значения используются в качестве начального приближения. Если решение задачи неединственное (т.е. одно и то же оптимальное значение целевого параметра может быть получено при разных значениях изменяемых параметров), Solver выдаст только одно решение, определяемое выбором начального приближения. Изменив начальное приближение, можно найти другое решение, дающее то же оптимальное значение целевого параметра.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-06-13 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: