Решения задачи планирования производства симплекс методом (стр. 5 из 10)
Шаг 3. Вычисление оценки
, удовлетворяющей условию:Если все
, то в соответствии с выполнением критерия оптимальности вектор 
— оптимальное решение, и далее следует перейти к шагу 9, иначе — к шагу 4.Шаг 4. Вычисление нового базисного решения
из условия: 
Шаг 5. Вычисление компонент нового базисного решения
по формулам: 
Шаг 6. Вычисление элементов новой симплекс-таблицы для
-й итерации метода по формулам: 
Шаг 7. Корректировка симплекс-таблицы с учетом изменений коэффициентов целевой функции, соответствующих новому базисному решению. Формируем таблицу (**).
Таблица (**)
| #№ | Базисные столбцы |  | Базисное решение Xs  | C1 | C2 | … | Cm | m+1 | … | Ck | … | Cn |
| A1 | A2 | … | Am | Am+1 | … | Ak | … | An | ||||
| 1 | A1 |  |  | 1 | 0 | … | 0 |  | … |  | … |  |
| 2 | A2 |  |  | 0 | 1 | … | 0 |  | … |  | … |  |
| … | … | … | … | … | … | … | … | … | … | … | … | … |
| l | Al |  |  | 0 | 0 | … | 0 |  | … |  | … |  |
| … | … | … | … | … | … | … | … | … | … | … | … | … |
| m | Am |  |  | 0 | 0 | … | 1 |  | … |  | … |  |
| Оценки |  |  | … |  |  | … |  | … |  |
Шаг 8. Переход к шагу 2.Шаг 9. Остановка, регистрация оптимального решения.
Таким образом, сформулированный алгоритм определяет конечную последовательность шагов, необходимых для вычисления оптимального решения.
2.4 Решение задач оптимизации при помощи средства «Поиск решения» в Microsoft Excel
Мощным средством анализа данных MS Excel является надстройка Solver (Поиск решения). С ее помощью можно определить, при каких значениях указанных влияющих ячеек формула в целевой ячейке принимает нужное значение (минимальное, максимальное или равное какой-либо величине). Для процедуры поиска решения можно задать ограничения, причем не обязательно, чтобы при этом использовались те же влияющие ячейки. Для расчета заданного значения применяются различные математические методы поиска. Вы можете установить режим, в котором полученные значения переменных автоматически заносятся в таблицу. Кроме того, результаты работы программы могут быть оформлены в виде отчета.
Программа «Поиск решений» (в оригинале Excel Solver) – дополнительная надстройка табличного процессора MS Excel, которая предназначена для решения определенных систем уравнений, линейных и нелинейных задач оптимизации, используется с 1991 года.
Размер задачи, которую можно решить с помощью базовой версии этой программы, ограничивается такими предельными показателями:
количество неизвестных (decision variable) – 200;
количество формульных ограничений (explicit constraint) на неизвестные – 100;
количество предельных условий (simple constraint) на неизвестные – 400.
Разработчик программы Solver, компания Frontline System, уже давно специализируется на разработке мощных и удобных способов оптимизации, встроенных в среду популярных табличных процессоров разнообразных фирм-производителей (MS Excel Solver, Adobe Quattro Pro, Lotus 1-2-3).
Высокая эффективность их применения объясняется интеграцией программы оптимизации и табличного бизнес-документа. Благодаря мировой популярности табличного процессора MS Excel встроенная в его среду программа Solver является наиболее распространенным инструментом для поиска оптимальных решений в сфере современного бизнеса.
Средство поиска решения Microsoft Excel использует алгоритм нелинейной оптимизации Generalized Reduced Gradient (GRG2), разработанный Леоном Ласдоном (Leon Lasdon, University of Texas at Austin) и Аланом Уореном (Allan Waren, Cleveland State University), алгоритмы симплексного метода и метода «branch-and-bound» для решения линейных и целочисленных задач с ограничениями разработаны Джоном Уотсоном (John Watson) и Деном Филстра (Dan Fylstra) из Frontline Systems, Inc.
2.4.2 Процедура поиска решения
В меню «Сервис» в разделе «Надстройки» необходимо активизировать функцию «Поиск решения».
Создайте таблицу с формулами, которые устанавливают связи между ячейками. (см. Рис.1)
Выделите целевую ячейку, которая должна принять необходимое значение, и выберите команду «Поиск решения». Поле Set Target Cell (Установить целевую ячейку) открывшегося диалогового окна надстройки Solver (Поиск решения) будет содержать адрес целевой ячейки.
Установите переключатели Equal To (Равной), задающие значение целевой ячейки, — Мах (максимальному значению), Min (минимальному значению) или Value of (значению). В последнем случае введите значение в поле справа.
Укажите в поле By Changing Cells (Изменяя ячейки), в каких ячейках программа должна изменять значения в поисках оптимального результата.
Создайте ограничения в списке Subject to the Constraints (Ограничения). Для этого щелкните на кнопке Add (Добавить) и в диалоговом окне Add Constraint (Добавление ограничения) определите ограничение.
Рис.2 Диалоговое окно надстройки «Поиск решения»
Щелкните на кнопке на кнопке Options (Параметры), и в появившемся окне установите переключатель Неотрицательные значения (если переменные должны быть позитивными числами), Линейная модель (если задача, которую вы решаете, относится к линейным моделям).
Рис.3 Окно параметров надстройки «Поиск решения»
Щелкнув на кнопке Solver (Выполнить), запустите процесс поиска решения.
Рис.4 Результаты поиска решения
2.4.3 Параметры средства «Поиск решения»
Максимальное время - служит для ограничения времени, отпущенного на поиск решения задачи. В этом поле можно ввести время в секундах, не превышающее 32 767 (примерно девять часов); значение 100, используемое по умолчанию, вполне приемлемо для решения большинства простых задач.
Предельное число итераций - управляет временем решения задачи путем ограничения числа вычислительных циклов (итераций).
Относительная погрешность - определяет точность вычислений. Чем меньше значение этого параметра, тем выше точность вычислений.