Линейное программирование в Office

Введение

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

Простым примером одной из таких задач, может быть следующая проблема. Фабрика занимается выпуском различных моделей мебели, приносящих различную прибыль. Каким образом возможно обеспечение наибольшей прибыли, если появится возможность получения добавочных ресурсных возможностей для расширения производства. Необходимо составить план производства. Эта задача вполне реальная, причём вместо мебельного производства могут быть рассмотрены любые другие отрасли.

Издавна подобные задачи пытались решать методикой перебора всех вариантов. Да и сегодня многие компьютерные программы работают именно по такой методике. То есть, более просто перебрать миллионы версий, а далее осуществить выбор оптимального варианта. Но всё равно на сегодняшний день при таких начальных условиях выполняется построение математической модели, описывающей работы с реальными объектами и которая может быть достаточно легко разработана на рабочей станции. Самым важным в моделировании является определение и выделение целевой функции, которая связана с изменяемым комплектом переменных. Оптимальное значение целевой функции может быть её максимумом, минимумом или некоторым значением. Для гарантии точности и правильности итогового результата при минимальной величине погрешности, следует задать для модели правильный набор ограничений. Для примера, приведённого выше, это запас складских ресурсов, но это могут быть для других задач и людские, и временные, и финансовые ресурсы, а также многое другое.

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

Линейное программирование в Microsoft Office Excel

При практических расчётах для этих целей можно применять стандартный пакет MS Excel. У него есть меню «Сервис» с пунктом «Поиск решения». При отсутствии такого пункта, следует выполнить установку данного модуля из дистрибутива Microsoft Office. Для старых версий MS Excel, выпущенных до 2007-го года данный пункт доступен через меню Сервис → Надстройки.

В появившемся окне нужно поставить галку около параметра «Поиск решения» и нажать ОК. После этого в закладке «Данные» должна отобразиться опция «Поиск решения», как показано на рисунке ниже:

Рисунок 1. Окно программы. Автор24 — интернет-биржа студенческих работ

В ячейки таблицы следует занести в свободном формате переменные, целевую функцию и набор ограничений, затем они указываются в окошке «Поиск решения». Требуется без ошибок задать именно те ячейки, где изменяется информация, где расположена целевая функция и ограничения. Затем можно выполнить запуск расчёта. Если решение удастся найти, то записанные в ячейках формулы заменятся на определённые величины, а также будет сформирован отчёт по списку.

Рассмотрим конкретный пример. Бригада комбайнёров выполнила работы по уборке зерна. Зерно было реализовано, и бригадиру нужно распределить полагающуюся бригаде премию в размере пятьсот тысяч рублей между его комбайнёрами согласно отработанным каждым работником часам. То есть необходимо определить коэффициент для начисления заработной платы, пропорциональный отработанному времени. Прежде всего необходимо сформировать таблицу с начальными данными и выражениями, позволяющими рассчитать итоговый результат. Данная таблица приведена на рисунке ниже:

Рисунок 2. Окно программы. Автор24 — интернет-биржа студенческих работ

Для нашего примера итог должен равняться общей сумме премии, то есть пятьсот тысяч рублей. Необходимо, чтобы целевая функция, расположенная в ячейке С6, соединялась при помощи формулы с искомым коэффициентом пропорциональности, расположенным в ячейке F2. В нашем случае их связывают формульные выражения, которые позволяют вычислить размер заработной платы для каждого комбайнёра (С2:С5). Затем следует запустить «Поиск решения» и в появившемся окошке установить нужные параметры. А именно, выбираем оптимизировать целевую функцию $ C $6, как изображено на рисунке ниже:

Рисунок 3. Окно программы. Автор24 — интернет-биржа студенческих работ

Затем нужно поставить точку в «Значения» и ввести размер премии, то есть пятьсот тысяч рублей. В графу «Изменяя ячейки переменных» нужно установить коэффициент $ F $2, который нужно найти. Эту операцию можно выполнить щелчком курсора мыши по ячейке целевой функции F2. Далее следует нажать на клавишу «Найти решение», после чего можно увидеть итоговый результат:

Рисунок 4. Окно программы. Автор24 — интернет-биржа студенческих работ

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

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

Параметр «Максимальное время» позволяет задать время (секунды), которое выделяется для разрешения задачи. Задаваемое время не может превышать значение 32 767 секунд (то есть девять часов).

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

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