Содержание

Решение оптимизационных задач управления методом линейного программирования

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

Линейное программирование предусматривает построение математической модели рассматриваемой задачи. После чего решение может быть найдено графически (рассмотрено ниже), с использованием Excel (будет рассмотрено отдельно) или специализированных компьютерных программ. [2]

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

Рассмотрим пример построения математической модели линейного программирования

Николай Кузнецов управляет небольшим механическим заводом. В будущем месяце он планирует изготавливать два продукта (А и В), по которым удельная маржинальная прибыль оценивается в 2500 и 3500 руб., соответственно.

Николай хочет построить модель с тем, чтобы определить количество единиц продуктов А и В, которые он доложен производить в следующем месяце для максимизации маржинальной прибыли.

Линейная модель может быть построена в четыре этапа.

Существует целевая переменная (обозначим её Z), которую необходимо оптимизировать, то есть максимизировать или минимизировать (например, прибыль, выручка или расходы). Николай стремится максимизировать маржинальную прибыль, следовательно, целевая переменная:

Z = суммарная маржинальная прибыль (в рублях), полученная в следующем месяце в результате производства продуктов А и В.

х₁ = количество единиц продукта А, произведенных в следующем месяце.

х₂ = количество единиц продукта В, произведенных в следующем месяце.

Очень важно четко определить все переменные величины; особое внимание уделите единицам измерения и периоду времени, к которому относятся переменные.

Целевая функция – это линейное уравнение, которое должно быть или максимизировано или минимизировано. Оно содержит целевую переменную, выраженную с помощью искомых переменных, то есть Z выраженную через х₁, х₂… в виде линейного уравнения.

Николай стремится максимизировать этот показатель. Таким образом, целевая функция в нашей модели:

Ограничения – это система линейных уравнений и/или неравенств, которые ограничивают величины искомых переменных. Они математически отражают доступность ресурсов, технологические факторы, условия маркетинга и иные требования. Ограничения могут быть трех видов: «меньше или равно», «больше или равно», «строго равно».

Аналогичные соображения применяются к сырью и труду, что позволяет записать еще два ограничения:

Наконец следует отметить, что существует условие, согласно которому должно быть изготовлено не менее 12 единиц продукта В:

Этап 4. Запись условий неотрицательности

Искомые переменные не могут быть отрицательными числами, что необходимо записать в виде неравенств х₁ ≥ 0 и х₂ ≥ 0. В нашем примере второе условия является избыточным, так как выше было определено, что х₂ не может быть меньше 12.

Полная модель линейного программирования для производственной задачи Николая может быть записана в виде:

Рассмотрим графический метод решения задачи линейного программирования.

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

Оси на графике представляют собой две искомые переменные (рис. 2). Не имеет значения, какую переменную отложить вдоль, какой оси. Важно выбрать масштаб, который в конечном итоге позволит построить наглядную диаграмму. Поскольку обе переменные должны быть неотрицательными, рисуется только I-й квадрант.

Рассмотрим, например, первое ограничение: 3 * х₁ + 10 * х₂ ≤ 330. Это неравенство описывает область, лежащую ниже прямой: 3 * х₁ + 10 * х₂ = 330. Эта прямая пересекает ось х₁ при значении х₂ = 0, то есть уравнение выглядит так: 3 * х₁ + 10 * 0 = 330, а его решение: х₁ = 330 / 3 = 110

Аналогично вычисляем точки пересечения с осями х₁ и х₂ для всех условий-ограничений:

Область допустимых значений	Граница допустимых значений	Пересечение с осью х₁	Пересечение с осью х₂
3 * х₁ + 10 * х₂ ≤ 330	3 * х₁ + 10 * х₂ = 330	х₁ = 110; х₂ = 0	х₁ = 0; х₂ = 33
16 * х₁ + 4 * х₂ ≤ 400	16 * х₁ + 4 * х₂ = 400	х₁ = 25; х₂ = 0	х₁ = 0; х₂ = 100
6 * х₁ + 6 * х₂ ≤ 240	6 * х₁ + 6 * х₂ = 240	х₁ = 40; х₂ = 0	х₁ = 0; х₂ = 40
х₂ ≥ 12	х₂ = 12	не пересекает; идет параллельно оси х₁	х₁ = 0; х₂ = 12

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

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

Аналогично отражаем на графике остальные ограничения (рис. 4). Значения х₁ и х₂ на или внутри заштрихованной области ABCDE будут соответствовать всем ограничениям модели. Такая область называется областью допустимых решений.

Рис. 4. Область допустимых решений для модели в целом

Теперь в области допустимых решений необходимо определить значения х₁ и х₂, которые максимизируют Z. Для этого в уравнении целевой функции:

разделим (или умножим) коэффициенты перед х₁ и х₂ на одно и тоже число, так чтобы получившиеся значения попали в диапазон, отражаемый на графике; в нашем случае такой диапазон – от 0 до 120; поэтому коэффициенты можно разделить на 100 (или 50):

затем присвоим Z значение равное произведению коэффициентов перед х₁ и х₂ (25 * 35 = 875):

и, наконец, найдем точки пересечения прямой с осями х₁ и х₂:

Уравнение целевой функции	Пересечение с осью х₁	Пересечение с осью х₂
875 = 25х₁ + 35х₂	х₁ = 35; х₂ = 0	х₁ = 0; х₂ = 25

Нанесем это целевое уравнение на график аналогично ограничениям (рис. 5):

Рис. 5. Нанесение целевой функции (черная пунктирная линия) на область допустимых решений

Значение Z постоянно на всем протяжении линии целевой функции. Чтобы найти значения х₁ и х₂, которые максимизируют Z, нужно параллельно переносить линию целевой функции к такой точке в границах области допустимых решений, которая расположена на максимальном удалении от исходной линии целевой функции вверх и вправо, то есть к точке С (рис. 6).

Рис. 6. Линия целевой функции достигла максимума в пределах области допустимых решений (в точке С)

Определим, например значения х₁ и х₂ в точке С. Заметим, что точка С находится на пересечении линий: 3х₁ + 10х₂ = 330 и 6х₁ + 6х₂ = 240. Решение этой системы уравнений дает: х₁ = 10, х₂ = 30. Результаты расчета для всех вершин области допустимых решений приведены в таблице:

Точка	Значение х₁	Значение х₂	Z = 2500х₁ + 3500х₂
А	22	12	97 000
В	20	20	120 000
С	10	30	130 000
D	0	33	115 500
E	0	12	42 000

Таким образом, Николай Кузнецом должен запланировать на следующий месяц производство 10 изделий А и 30 изделий В, что позволит ему получить маржинальную прибыль в размере 130 тыс. руб.

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

Начертите на графике две оси, представляющие собою два параметра решения; нарисуйте только I-й квадрант.
Определите координаты точек пересечения всех граничных условий с осями, подставляя в уравнения граничных условий поочередно значения х₁ = 0 и х₂ = 0.
Нанести линии ограничений модели на график.
Определите на графике область (называемую допустимой областью принятия решения), которая соответствует всем ограничениям. Если такая область отсутствует, значит, модель не имеет решения.
Определите значения искомых переменных в крайних точках области принятия решения, и в каждом случае рассчитайте соответствующее значение целевой переменной Z.
Для задач максимизации решение – точка, в которой Z максимально, для задач минимизации, решение – точка, в которой Z минимально.

5 комментариев для “Решение оптимизационных задач управления методом линейного программирования”

[expert_bq id=»1570″]Вы можете Изменить или Удалить ограничение, если допустили ошибку, выбрав конкретное ограничение и нажав соответствующие кнопки в диалоговом окне. Если же вы хотите что-то уточнить, обращайтесь ко мне![/expert_bq] Мы хотим, чтобы суммы обоих групп совпадали, т.е. чтобы разница сумм была равна 0. Это может показаться странным, но нам не требуется минимизировать разницу, потому что при этом все элементы будут помещены в Группу A, что приведет к значению ячейки G11 меньше нуля.

Как Решить Оптимизационную Задачу в Excel • Проверка результатов

Поиск решений в Excel — пример использования сервиса поиск решений в Excel | Exceltip

Начертите на графике две оси, представляющие собою два параметра решения; нарисуйте только I-й квадрант.
Определите координаты точек пересечения всех граничных условий с осями, подставляя в уравнения граничных условий поочередно значения х₁ = 0 и х₂ = 0.
Нанести линии ограничений модели на график.
Определите на графике область (называемую допустимой областью принятия решения), которая соответствует всем ограничениям. Если такая область отсутствует, значит, модель не имеет решения.
Определите значения искомых переменных в крайних точках области принятия решения, и в каждом случае рассчитайте соответствующее значение целевой переменной Z.
Для задач максимизации решение – точка, в которой Z максимально, для задач минимизации, решение – точка, в которой Z минимально.

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

Область допустимых значений	Граница допустимых значений	Пересечение с осью х₁	Пересечение с осью х₂
3 * х₁ + 10 * х₂ ≤ 330	3 * х₁ + 10 * х₂ = 330	х₁ = 110; х₂ = 0	х₁ = 0; х₂ = 33
16 * х₁ + 4 * х₂ ≤ 400	16 * х₁ + 4 * х₂ = 400	х₁ = 25; х₂ = 0	х₁ = 0; х₂ = 100
6 * х₁ + 6 * х₂ ≤ 240	6 * х₁ + 6 * х₂ = 240	х₁ = 40; х₂ = 0	х₁ = 0; х₂ = 40
х₂ ≥ 12	х₂ = 12	не пересекает; идет параллельно оси х₁	х₁ = 0; х₂ = 12

Решение оптимизационных задач в excel.

Для решения задач оптимизации широкое променение находят различные средства Excel.

Основной командой для решения оптимизационных задач в Excel является команда Сервис/Подбор параметра. Эта команда определяет неизвестную величину, приводящую к требуемому результату.

Если команда Подбор параметра отсутствует в меню Сервис, выполните команду Сервис/Надстройка и установите флажок Пакет анализа в окне диалога Надстройка

Для работы с командой Подбор параметра необходимо подготовить лист, чтобы в листе находились:

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

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

Такой процесс называется итерацией, и продолжается он до тех пор, пока редактор не выполнит 100 попыток или не найдет решения, лежащее в пределах точности 0,001 от точного значения (настройка этих параметров осуществляется с помощью команды Сервис/Параметры, вкладка Вычисления)

Оптимизация с помощью команды Подбор параметров выполняется так:

1. Создайте лист, например, с формулой =B1*B2 в ячейке B3, пустой (переменной) ячейкой (B2) и другими данными (B1), которые могут понадобиться при вычислениях. Например, необходимо определить количество книг по цене 23,75 грн., которые необходимо продать, чтобы объем продаж составил 10000,00 грн.

2. Выделите ячейку листа (B3), в которой содержится формула (эта ячейка появится в поле Установить в ячейке в окне диалога Подбор параметра). Выполните команду Сервис/Подбор параметра. Открывается окно диалога Подбор параметра..

После завершения итерационного цикла в окне диалога Результат подбора параметра появляется сообщение, а результат заносится в ячейку листа. Решение показывает, что для достижения объема продаж 10000 грн. необходимо продать 421 книгу по цене 23,75 грн. Для закрытия окна диалога Результат подбора параметра щелкните на кнопке ОК.

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

В том случае, когда оптимизационная задача содержит несколько переменных величин, для анализа сценария необходимо воспользоваться надстройкой Поиск решения. “Поиск решения” позволяет использовать одновременно большое количество изменяемых ячеек (до 200) и задавать ограничения для изменяемых ячеек.

Общие свойства, которые характерны для задач, решаемых с помощью надстройки Поиск решения:

Существует единственная целевая ячейка, содержащая формулу, значение которой должно быть сделано максимальным, минимальным или же равным, какому-то конкретному значению.

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

Может быть задано некоторое количество ограничений — условий или соотношений, которым должны удовлетворять некоторые из изменяемых ячеек.

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

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

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

1. Выделите на листе целевую ячейку, в которую введена формула.

2. Выполните команду Сервис/Поиск решения. Открывается окно диалога Поиск решения. Поскольку была выделена ячейка, в текстовом поле «Установить целевую ячейку» появится правильная ссылка на ячейку. В группе «Равной» переключатель по умолчанию устанавливается в положение «Максимальному значению».

3. Перейдите к полю Изменяя ячейки и введите переменные ячейки листа

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

5. Когда оптимизационная задача будет готова к выполнению, можно нажать кнопку Выполнить для получения ответа. Появится окно диалога с описанием результатов процесса оптимизации.

6. Чтобы отобразить найденное решение в ячейках листа, установите переключатель Сохранить найденное решение и нажмите кнопку ОК. Найденная максимальная величина помещается в целевую ячейку, а переменные ячейки заполняются оптимальными значениями переменных, которые удовлетворяют установленным ограничениям.

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

Чтобы устранить эти ограничения, разработчики Excel создали Диспетчер сценариев, помогающий работать с несколькими моделями «что – если». Командой Сервис/Сценарии можно создавать новые и просматривать существующие сценарии для решения задач, и отображать консолидированные отчеты.

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

Выполните команду Сервис/Сценарии. Открывается изображение окна диалога Диспетчер сценариев.

Нажмите кнопку Добавить, чтобы создать первый сценарий. Откроется окно диалога Добавление сценария.

Введите Лучший вариант (или любое другое имя) в поле Название сценария, затем с помощью окон диалога введите изменяемые ячейки. Когда этот сценарий будет готов, введите следующий.

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

Закройте окно диалога Диспетчер сценариев кнопкой Закрыть.

Excel сохраняет сценарии вместе с листом текущей книги, и просмотр их командой Сервис /Сценарии возможен только при открытии данного листа. Просмотр сценария выполняется следующим образом:

Выполните команду Сервис/Сценарии. Открывается окно диалога:

Нажмите кнопку Вывести. Excel заменяет содержимое ячеек листа значениями из сценария и отображает результаты на листе.

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

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

Эту задачу можно выполнить с помощью кнопки Отчет в окне диалога Диспетчер сценариев. Созданный сводный отчет будет автоматически отформатирован и скопирован на новый лист текущей книги.

Создание отчета по сценарию происходит следующим образом:

Выполните команду Сервис/Сценарии. Откроется окно диалога Диспетчер сценариев.

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

Статьи к прочтению:

Excel. Задачи оптимизации. Часть 1

Презентация на тему Решение задач оптимизации в MS Excel по информатике для 10 класса

Ещё одно важное понятие, используемое в теории оптимизации – «целевая функция». Это выражение, зависящее от проектных параметров, которое надо сделать максимальным (или минимальным). К настоящему времени разработаны десятки алгоритмов, позволяющих численно решать задачи оптимизации. Часть этих алгоритмов включена в средство «Поиск решения».

Дополнительные данные → Похожие темы → Все про Exel → Как вставить значения → Как объединить ячейки → Как вставить форматы → Дополнительные данные → Вставить формулы→ Аргументы функции