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

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

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

Большинство задач оптимизации относится к нелинейным, но решение нелинейных задач – это сложная вычислительная проблема. Поэтому практически во всех реальных приложениях для решения нелинейных задач используются приближенные методы решения. Линейное программирование выделяется среди других методов программирования как основа для многих процедур решения. Математически задача линейного программирования ставится следующим образом: ищется максимум линейной формы (функции цели) L (2.1) = c₁x₁ + c₂x₂ + . + c_nx_n = при условиях a_i1x₁ + a_i2x₂ + . + a_inx_n ≤ b_i, i = 1, 2, . m; j = 1,2, …, n, или –a_i1x₁ – a_i2x₂ – . – a_inx_n + b_i  0. Словесно задачу линейного программирования можно сформулировать так: требуется найти максимум линейной формы от n переменных при m ограничениях в виде неравенств или равенств. Нетрудно убедиться, что всегда можно говорить только о равенствах, так как введением дополнительных переменных x_n+υ (υ = 1, . p ≤ m) неравенства всегда можно свести к равенствам. Так, ограничение a (2.2) _i1x₁ + a_i2x₂ + . + a_inx_n ≤ b_i м (2.3) ожно свести к равенству, добавив переменную x_n+1: a_i1x₁ + a_i2x₂ + . + a_inx_n + x_n+1 = b_i. Тогда условие (2.2) сведется к (2.3) и условию неотрицательности переменной x_n+1. Поэтому можно сказать, что при решении задачи линейного программирования определяются такие значения n переменных x_j, которые бы обращали в максимум линейную форму L = c₁x₁ + c₂x₂ + . + c_nx_n при условии выполнения m равенств a_i1x₁ + a_i2x₂ + . + a_inx_n = b_i, i = 1, 2, . m и n неравенств x_j, j = 1,2, …, n.

2.1.2. Примеры прикладных задач линейного программирования

Рассмотрим несколько практических задач, которые сводятся к линейному программированию. Транспортная задача В трех месторождениях добывается определенное количество угля. Имеются три пункта потребления угля. Известны расстояния между пунктами добычи и потребления и стоимость перевозок c_ij (i = 1, 2, 3; j = 1, 2, 3). Необходимо так определить девять чисел x_ij, означающих количество грузов, перевозимых из пункта добычи в пункт потребления, чтобы суммарная стоимость перевозок была минимальна: L = ∑c_ijx_ij → min при условиях x_1j + x_2j + x_3j = b_j, j = 1, 2, 3, требующих, чтобы спрос удовлетворялся во всех пунктах, и при условиях x_i1 + x_i2 + x_i3 = a_i, i = 1, 2, 3, требующих, чтобы из каждого пункта добычи вывозилось угля не больше количества а_i, которое на нем производится. Считается, что количество добытого угля равно сумме потребляемого, т.е. хотя это ограничение непринципиально. Задача о рациональном питании При правильном питании калорийность пищевых продуктов должна полностью возмещать расход энергии человека, причем потребление отдельных растительных и животных жиров, белков, углеводов и витаминов не должно превышать определенную норму. Предположим, имеется n различных продуктов калорийностью a_1j (j = 1, 2, . n), равной числу калорий в единице массы. В единице массы j-го продукта содержится a_2j жиров, a_3j белков, a_4j углеводов. Обозначим через b₁, b₂, b₃, b₄ потребность организма в энергии, жирах, белках и углеводах, соответственно. Тогда при правильном питании должны выполняться следующие соотношения: a₁₁x₁ + a₁₂x₂ + . + a_1nx_n  b₁; a₂₁x₁ + a₂₂x₂ + . + a_2nx_n ≤ b₂; a₃₁x₁ + a₃₂x₂ + . + a_3nx_n ≤ b₃; a₄₁x₁ + a₄₂x₂ + . + a_4nx_n ≤ b₄, где x_j  0 – количество потребления j-го продукта. Если ввести требование экономного расходования средств, то это эквивалентно критерию L = → min. Если поменять знаки b₁, a_1j (j = 1, 2, . n), то первое неравенство запишется в виде –a₁₁x₁ – a₁₂x₂ – . – a_1nx_n ≤ –b₁. После этого задача о рациональном питании приобретает стандартный вид задачи линейного программирования. Задача об использовании ресурсов Предприятие имеет определенное количество ресурсов: рабочую силу, сырье, оборудование и т.д. Для простоты будем считать, что число ресурсов равно трем, и каждого ресурса имеется b₁, b₂, b₃, условных единиц. Предприятие выпускает два вида товаров. Для производства единицы каждого товара затрачивается а_ij ресурсов. Известна стоимость с_i единицы каждого товара. Требуется при данных ресурсах выпустить такую комбинацию товаров x₁ и x₂, чтобы доход предприятия L был максимален. При линейной зависимости стоимости продукции от количества продукции задача записывается в виде L = c₁x₁ + c₂x₂ → max; a_i1x₁ + a_i2x₂ ≤ b_i; i = 1, 2, 3; x_j  0 и относится к классу задач линейного программирования. Если стоимость товаров не зависит линейно от их количества, то имеет место задача нелинейного программирования. Задача о загрузке транспорта Пусть имеется транспортная единица грузоподъемностью b, которую необходимо загрузить различными предметами x_j в разных количествах, причем c_j – стоимость; w_j – вес отдельного предмета j-го типа. Например, загружаются автомобили. Требуется определить оптимальную загрузку так, чтобы стоимость перевозимого груза была минимальной. Очевидно, что стоимость всего перевозимого груза задается формулой Необходимо найти такие целые числа x_j (j = 1, 2, . n), при которых эта линейная форма приняла бы максимальное значение при условиях В отличие от предыдущих в этой задаче число ограничений i = 1. Она существенно отличается от ранее рассмотренных тем, что в ней искомые значения величин x_j целочисленные. Поэтому ее можно отнести к задачам целочисленного линейного программирования, которые решаются различными способами, в том числе и с помощью динамического программирования.

Источник

6. Постановка задач линейного программирования. Примеры, различные формы задач и подходы решения. Постановка задач линейного программирования

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

В общей постановке задача линейного программирования (ЗЛП) формулируется следующим образом. Имеются какие-то переменные x = (x1, x2,…, xn) и линейная функция этих переменных, которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции при условии, что переменные x удовлетворяют системе линейных равенств и/или неравенств.

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

Или в сокращённом виде с сигмой:

Можно встретить обозначение целевой функции и через C, и через F.

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

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

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

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

Ограничения. Очень просто. Например, в каждом уравнении (неравенстве) заданы ограничения перечисленных выше или других запасов, используемых для производства определённого вида продукции.

Примеры, различные формы задач и подходы решения

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

Общей задачей ЛП называется задача, которая состоит в определении максимального (минимального) значения функции

Помимо общей формы, различают еще две частные задачи линейного программирования — стандартную и основную.

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

Ограничения основной задачи ЛП представляют собой линейные ограничения-равенства, а также условия неотрицательности на переменные:

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

Примеры решения задач линейного программирования:

Пример №1. Предприятие выпускает продукцию двух разновидностей. Каждый вид продукции проходит обработку на трёх станках. При обработке 1 т продукции I вида первый станок используется 0 ч, второй станок – 1 ч, третий станок – 1 ч. При обработке 1 т продукции II вида первый станок используется 1 ч, второй станок – 4 ч, третий станок – 1 ч. Время работы станков ограничено и не может превышать для первого станка 7 ч, для второго 29 ч, для третьего 11 ч. При реализации 1 т продукции I вида предприятие получает прибыль 2 руб., а при реализации 1 т продукции II вида – 5 руб. Найти оптимальный план выпуска продукции каждого вида, дающий максимальную прибыль от реализации всей продукции.

3. Решим прямую задачу графически:

Источник