Формализация моделей линейного программирования

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Задача поиска оптимального решения как раз и является экстремальной – необходимо найти экстремум (максимум или минимум) целевой функции. А если используемая модель представлена системой линейных уравнений, неравенств, ограничений (во многих случаях это так), то она является моделью линейного программирования. Таким образом, задача поиска оптимального решения сводится к задаче линейного программирования. Здесь под программированием понимается определение набора значений переменных решения, соответствующих экстремуму целевой функции.

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

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

Ограничения – система неравенств и (или) равенств, которым должны удовлетворять значения переменных модели. Ограничения сужают множество допустимых решений и имеют различную природу: экономическую, физическую и даже политическую. Например, увеличение объёмов производства ограничено запасами ресурсов, снижение объёмов закупок ограничено необходимостью обеспечения заданного уровня снабжения, изменение расписания или маршрута не должно приводить к появлению неудовлетворённых потребностей перевозок.

Интересные люди и интересные факты. Леони́д Вита́льевич Канторо́вич (6 (19) января 1912, Санкт-Петербург — 7 апреля 1986, Москва) — советский математик и экономист, пионер и один из создателей линейного программирования. Лауреат Нобелевской премии по экономике 1975 года «за вклад в теорию оптимального распределения ресурсов». После того, как Л. В. Канторовичем был предложен оптимальный метод распила фанерного листа, этот метод в том числе попытались применить к разрезанию стальных листов. После внедрения методов оптимизации на производстве одной из фабрик инженерам удалось улучшить показатели, что привело, однако, к негативным последствиям: а) система социалистического планирования требовала, чтобы в следующем году план был перевыполнен, что было принципиально невозможно при имеющихся ресурсах (поскольку найденное решение было абсолютным максимумом); б) фабрика не выполнила план по металлолому, львиная доля которого складывалась из обрезков стальных листов. Руководство фабрики получило выговор от партии и больше с математиками не связывалось.

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

1) Описать словами цель и целевую функцию, отражающую показатель эффективности.

2) Дать словесное описание каждого ограничения, обращая особое внимание на то, является ли данное ограничение требованием в форме неравенств или равенством.

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

Теперь, имея словесное описание, можно переходить к составлению математической модели. Для этого нужно выполнить следующие действия:

4) Присвоить переменным решения условные обозначения (имена).

5) Выразить все ограничения через переменные решения.

6) Выразить через переменные решения целевую функцию.

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

Рассмотрим создание математической модели на примере задачи, связанной с торговой деятельностью. Итак, эксклюзивный представитель неких лиц торгует двумя видами продукции – П1 и П2. Для этого необходимо использовать четыре вида ресурсов, например, Р1 – закупка (себестоимость); Р2 – расходы на продвижение (целевая реклама, личные продажи); Р3 – сбыт (хранение, доставка, продажа) и Р4 – обеспечение гарантийного обслуживания продукции. Запасы ресурсов, число единиц ресурсов, затрачиваемых на единицу реализуемой продукции, приведены в таблице 1 (единицы измерения условные). Прибыль, получаемая от единицы продукции П1 и П2, – 2 и 3 руб. соответственно. Необходимо произвести поиск такого плана реализации продукции, при котором прибыль будет максимальной.

Таблица 1

1) Цель – максимизация прибыли

2) Ограничения представлены имеющимися запасами ресурсов. Этих запасов должно хватить, следовательно, по каждому виду ресурсов затратить можно такое количество, которое не больше (меньше, либо равно), чем имеющиеся запасы.

3) Переменные решения – план реализации (количество единиц каждого вида реализуемой продукции).

4) Обозначим планируемое количество единиц каждого вида реализуемой продукции П1 и П2 как х₁ и х₂, соответственно

5) Во-первых, по смыслу задачи изменяемые параметры х₁ и х₂ должны быть целыми и неотрицательными. Во-вторых, ограничение на потребление ресурсов выразится системой неравенств:

(1)

6) Целевая функция, которую нужно максимизировать (суммарная прибыль от обоих видов продукции):

F=2x₁ +3x₂. (2)

Итак, математическая модель задачи: найти такой план выпуска продукции (подобрать целые неотрицательные х₁ и х₂), удовлетворяющий системе ограничений (1), при котором целевая функция (2) принимает максимальное значение.

Рассмотрим ещё один пример, в котором формализация сводится к табличной модели. Требуется составить график занятости работников торгового предприятия с пятидневной рабочей неделей и двумя выходными подряд, обеспечивающий удовлетворение заданной потребности в персонале (Пн - 22, Вт - 17, Ср - 13, Чт - 14, Пт - 15, Сб - 18, Вс - 24) при минимальных затратах на оплату труда, определяемых дневной ставкой заработной платы 1000 руб. (одинаковой для всех работников).

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

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

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

4) Существует семь возможных вариантов пятидневной рабочей недели с двумя выходными подряд – по одному для каждого дня недели, соответствующего первому выходному, что показано в таблице. В графах Пн – Вс представлены нули и единицы, соответствующие выходным и рабочим дням. Поэтому в этой задаче семь переменных решения, обозначим их Р1 – Р7, каждая из которых определяет количество работников для соответствующего варианта пятидневки.

5) Чтобы выразить через Р1 – Р7 ограничения, задаваемые потребностью по дням недели, нужно найти фактическое количество работников для каждого дня недели (просуммировать значения только тех переменных Р1 – Р7, для которых текущий день является рабочим). Для этого сначала для каждой строки графика нужно найти произведение соответствующей переменной (Р1 – Р7) на число, обозначающее занятость работников для каждого дня (0 или 1), после чего найти сумму полученных произведений по каждой из граф (Пн – Вс). Найденные суммы (строка КР) должны быть больше либо равны заданной потребности в работниках (ПР) по каждому дню недели, соответственно.

6) Целевая функция – недельная заработная плата НЗ определяется как произведение ставки дневной заработной платы (ДО) и общего количества работников (суммы переменных Р1 – Р7):

НЗ=ДО

4.3 Представление модели линейного программирования в электронных таблицах

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

Представим в электронной таблице последний пример из предыдущего подраздела:

Небольшое отличие заключается в том, что для функции ограничения использована функция СУММПРОИЗВ, а не СУММ, что позволило убрать таблицу с промежуточными расчётами количества работников по дням недели. В этой же строке КР, в графе Работн. добавлена функция для расчёта общего количества работников (суммы переменных Р1 – Р7).

При создании табличной модели целесообразно использовать следующие рекомендации.

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

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

- Коэффициенты целевой функции хранятся в отдельных ячейках. В нашем примере это ставка дневной оплаты ДО. Такие коэффициенты легко изменять, не редактируя формул.

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

- Коэффициенты перед переменными решения в ограничениях заносятся в ячейки на пересечении соответствующих переменным и ограничениям строк и столбцов. В нашем примере это график выходных/рабочих дней.

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

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

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