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

Лекция 3: Математическое программирование. Линейное программирование. Виды задач линейного программирования. Постановка задач линейного программирования и исследование их структуры. Решение задач линейного программирования симплекс-методом

1. Понятие математического программирования

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

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

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

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

В зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:

• задачи линейного программирования,
• задачи нелинейного программирования .

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

2. Понятие линейного программирования. Виды задач линейного программирования

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования . Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина » математическое программирование «. Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программы) для ЭВМ» не имеет, т.к. дисциплина » линейное программирование » возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин » линейное программирование » возник в результате неточного перевода английского » linear programming «. Одно из значений слова «programming» — составление планов, планирование. Следовательно, правильным переводом английского » linear programming » было бы не » линейное программирование «, а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термины линейное программирование , нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

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

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

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

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

Общая форма задачи имеет вид: найти при условиях

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

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

Нужно определить максимум линейной целевой функции (линейной формы)

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

Такую задачу называют «основной» или «стандартной» в линейном программировании. Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования (ЛП) является симплекс метод.

Симплекс метод

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

Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X₁, . X_n), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X₁, . X_m), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1.

Данная формальная модель задачи линейного программирования обычно задается в форме, так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода:

Симплекс-таблица

Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует определенному ограничению-равенству задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X₁, . X_m). Сверху от таблицы приведен набор всех переменных задачи, где X_m+1, . X_n — свободные переменные задачи.

На начальном шаге алгоритма симплекс-метода должно быть выбрано базисное допустимое решение (X₁, . X_m) >= 0 при X_j = 0 (j = m+1, . n), следовательно, все свободные члены ограничений A_i,0 >= 0 (i = 1, . m). Когда это условие выполнено, симплекс-таблица называется прямо-допустимой, так как в этом случае базисные переменные, равные A_i,0, определяют допустимое решение прямой задачи линейного программирования. Если все коэффициенты целевой функции A_0,j >= 0 (j = 1, . m), то симплекс-таблица называется двойственно-допустимой, поскольку соответствующее решение является допустимым для двойственной задачи линейного программирования.

Если симплекс-таблица является одновременно прямо и двойственно допустимой, т.е. одновременно все A_i,0 >= 0 и A_0,j >= 0, то решение оптимально.

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

Столбец p симплекс-таблицы, соответствующий выбранному коэффициенту A_0,p

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

Папиллярные узоры пальцев рук — маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни.

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ — конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой.

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

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

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

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

Скачать заметку в формате Word, рисунки в формате Excel

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

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

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

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

Изготовление обоих продуктов требует затрат на машинную обработку, сырье и труд (рис. 1). На изготовление каждой единицы продукта А отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта В составляют 10, 4 и 6. Николай прогнозирует, что в следующем месяце он может предоставить 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 12 единиц продукта В необходимо изготавливать в каждый конкретный месяц.

Рис. 1. Использование и предоставление ресурсов

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

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

Этап 1. Определение переменных

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

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

Существует ряд неизвестных искомых переменных (обозначим их х₁, х₂, х₃ и пр.), чьи значения необходимо определить для получения оптимальной величины целевой функции, которая, в нашем случае является суммарной маржинальной прибылью. Эта маржинальная прибыль зависит от количества произведенных продуктов А и В. Значения этих величин необходимо рассчитать, и поэтому они представляют собой искомые переменные в модели. Итак, обозначим:

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

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

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

Этап. 2. Построение целевой функции

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

В нашем примере каждый изготовленный продукт А приносит 2500 руб. маржинальной прибыли, а при изготовлении х₁ единиц продукта А, маржинальная прибыль составит 2500 * х₁. Аналогично маржинальная прибыль от изготовления х₂ единиц продукта В составит 3500 * х₂. Таким образом, суммарная маржинальная прибыль, полученная в следующем месяце за счет производства х₁ единиц продукта А и х₂ единиц продукта В, то есть, целевая переменная Z составит:

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

Максимизировать Z = 2500 * х₁ + 3500 *х₂

Этап. 3. Определение ограничений

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

В нашем примере для производства продуктов А и В необходимо время машинной обработки, сырье и труд, и доступность этих ресурсов ограничена. Объемы производства этих двух продуктов (то есть значения х₁ их₂) будут, таким образом, ограничены тем, что количество ресурсов, необходимых в производственном процессе, не может превышать имеющееся в наличии. Рассмотрим ситуацию со временем машинной обработки. Изготовление каждой единицы продукта А требует трех часов машинной обработки, и если изготовлено х₁, единиц, то будет потрачено З * х₁, часов этого ресурса. Изготовление каждой единицы продукта В требует 10 часов и, следовательно, если произведено х₂ продуктов, то потребуется 10 * х₂ часов. Таким образом, общий объем машинного времени, необходимого для производства х₁ единиц продукта А и х₂ единиц продукта В, составляет 3 * х₁ + 10 * х₂. Это общее значение машинного времени не может превышать 330 часов. Математически это записывается следующим образом:

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

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

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

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

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

Максимизировать: Z = 2500 * х₁ + 3500 *х₂

При условии, что: 3 * х₁ + 10 * х₂ ≤ 330

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

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

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

Рис. 2. Оси графика линейного программирования

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

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

16. Целочисленные задачи линейного программирования

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

Другая сфера применения целочисленных моделей — выбор вариантов. В соответствующих задачах все или некоторые пере­менные могут принимать только два значения: 0 или 1. Такие пе­ременные носят название булевых.

Наиболее известные методы решения целочисленных задач — метод отсечения и метод ветвей и границ. Они разработаны в на­чале 60-х годов XX века и затем неоднократно усовершенствова­лись и модифицировались. Решения примеров и задач, приводи­мых в этой главе, получены с помощью метода ветвей и границ и являются точными.

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

• целочисленная и булева переменные;

• взаимоисключение и взаимообусловленность.

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

Первоначальным стимулом к изучению целочисленных и дис­кретных задач явилось рассмотрение задач линейного программи­рования, в которых переменные представляли физически недели­мые величины (скажем, количество единиц продукции разных видов). Для характеристики этого класса моделей используется термин «задачи с неделимостями».

Другим важным толчком к построению теории дискретного программирования явился новый подход к некоторым экстремаль­ным комбинаторным задачам, для решения которых приходится вводить булевы переменные, носящие логический характер (Х = 1 или Х = 0).

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

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

1) транспортная задача (см. главу 5) и ее варианты;

2) задачи с неделимостями;

3) экстремальные комбинаторные задачи;

4) задачи с неоднородной разрывной целевой функцией (см. транспортную задачу с фиксированными доплатами в главе 5);

5) задачи на неклассических областях (см. модель оптимального размера заказа с количественными скидками в главе 12).

Целочисленная задача линейного программирования (задача с неделимостями). К данному классу принадлежат Задачи распре­деления капиталовложении и Задачи планирования производства.

Целочисленная задача линейного программирования заключа­ется в максимизации функции:

(1)

(2)

Где J — некоторое подмножество множества индексов N = =<1,2. N>.

Если J = N (T. e. требование целочисленности наложено на все переменные), то задачу называют Полностью целочисленной; если же J ¹ N, она называется Частично целочисленной.

Модель (1)—(4) естественно интерпретировать, например, в следующих терминах. Пусть через I = 1. Т обозначены произ­водственные факторы, через J = 1, . П — виды конечной про­дукции.

Aij — количество факторов I, необходимое для производства единицы продукта J;

Bi — наличные ресурсы фактора I;

СI — прибыль, получаемая от единицы продукта J.

Пусть продукты J для JÎJ являются неделимыми, т. е. физи­ческий смысл имеет лишь их целое неотрицательное количество («штуки»). Предположим, что требуется составить производствен­ную программу, обеспечивающую максимум суммарной прибы­ли и не выводящую за пределы данных ресурсов. Обозначая через Xj искомые объемы выпуска продукции, мы сводим эту задачу к мо­дели (1)-(4).

Задача с булевыми переменными. Логическая взаимосвязь:

1) Взаимоисключение. Пусть Xj = 1, если реализуется проект АJ, И ХJ = 0 в противном случае. Запись AjÚAk означает, что в план может быть включен либо проект АJ, либо проект АK. Вместе они включены быть не могут. С помощью этой записи выражается от­ношение взаимоисключения между проектами.

В этих обозначениях взаимоисключение Aj Ú АK выражается неравенством ХJ + ХK £ 1;

2) Взаимообусловленность. Запись АK ® Aj («проект АK влечет за собой проект АJ») означает, что проект АK может быть включен в план только в том случае, если в план включен и проект Aj. С по­мощью этой записи выражается отношение между обусловлива­ющими друг друга проектами, например когда проект Ak — резуль­тат тиражирования проекта Aj на другом объекте или когда АK ба­зируется на результатах реализации проекта Aj.

В принятых обозначениях взаимообусловленность АK ® АJ вы­ражается неравенством ХK £ ХJ.

Экстремальные комбинаторные задачи. Задачи данного класса, называемые также задачами выбора, состоят в отыскании среди конечного множества альтернатив одной, которой отвечает экст­ремальное значение принятой целевой функции.

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

Пусть ХIj = 1, если коммивояжер переезжает из города I непо­средственно в город J, и Xij = 0 в противном случае. Обозначим через СIj расстояние между городами I и J (чтобы избежать бессмыс­ленных значений ХIj = 1, предполагается, что СIi равны достаточно большому числу).

Тогда формальная модель имеет вид

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

Где на переменные Zi и Zj не требуется накладывать никаких огра­ничений.

Общая Задача календарного планирования формулируется следу­ющим образом. Имеется П станков (машин), на которых требует­ся обработать M деталей. Заданы маршруты (в общем случае раз­личные) обработки каждой детали на каждом из станков или груп­пе станков. Задана также продолжительность операций обработки деталей. Предполагается, что одновременно на станке можно об­рабатывать не более одной детали. Требуется определить опти­мальную последовательность обработки. Критерием оптимально­сти могут выступать продолжительность обработки всех деталей, суммарные затраты на обработку, общее время простоя станков и др. Существует огромное число постановок данной задачи, учи­тывающих конкретные условия производства.

Один из представителей задач данного типа — так называемая Задача о ранце. Имеется П предметов. Предмет J (J = 1, . П) об­ладает весом Wj и полезностью СJ. Пусть B — общий максимально допустимый вес предметов, которые можно положить в ранец. Требуется выбрать предметы таким образом, чтобы их общий вес не превышал максимально допустимый и при этом суммарная по­лезность (ценность) содержимого ранца была максимальной. Пусть ХJ = 1, если предмет положен в ранец, и ХJ = 0 в противном случае. Математическая формулировка задачи имеет вид

К классу экстремальных комбинаторных задач принадлежит также линейный и нелинейный варианты Задача о назначениях (ли­нейный вариант такой задачи рассмотрен в главе 6).

Большинство целочисленных и комбинаторных типов задач, таких, как задача с неделимостями, задача коммивояжера, задача календарного планирования, принадлежит к разряду так называ­емых Трудно решаемых. Это означает, что вычислительная слож­ность алгоритма их точного решения — зависимость числа элемен­тарных операций (операций сложения или сравнения), необходи­мых для получения точного решения, от размерности задачи я — является Экспоненциальной (порядка 2N), т. е. сравнимой по тру­доемкости с полным перебором вариантов. В качестве П, например, для задачи с неделимостями служит число целочисленных перемен­ных и число ограничений, для задачи коммивояжера — число горо­дов (или узлов графа маршрутов), для задачи календарного плани­рования — число деталей и число станков. Такие задачи называют еще NP-трудными или NP-Полными. Получение их точного ре­шения не может быть гарантировано, хотя для некоторых задач данного типа существуют эффективные методы, позволяющие находить точное решение даже при больших размерностях. Примером таких задач служит задача о ранце с булевыми пере­менными.

Задачи с вычислительной сложностью, определяемой Полино­миальной зависимостью от П, называются Эффективно решаемы­ми. К такого типа задачам принадлежат задачи транспортного типа и линейные задачи о назначениях.

Для решения целочисленных задач используются следующие методы:

1) симплекс-метод (для транспортных задач, задач о назначениях);

2) метод отсечения (метод Гомори);

3) метод ветвей и границ (в общем случае не обеспечивает получения точного решения);

4) эвристические методы (не обеспечивают получения точно­го решения).

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