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

Лекция 12. Основная задача линейного программирования

Во многих областях деятельности возникают задачи оптимизации решений, для которых характерны следующие черты: • показатель эффективности W представляет линейную функцию от элементов решения x 1 , x 2 , …; • ограничения, налагаемые на возможные решения, имеют вид линейных равенств или неравенств. Такие задачи принято называть задачами линейного программирования .

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

Основной задачей линейного программирования (ОЗЛП) называется задача линейного программирования с ограничениями – равенствами. От задачи с ограничениями – неравенствами можно перейти к ОЗЛП и обратно. Основная задача линейного программирования формулируется следующим образом [5, 21,28]. Имеется ряд переменных x 1 , x 2 ,…, x n . Требуется найти такие неотрицательные значения этих переменных, которые удовлетворяли бы системе линейных уравнений:

a 11 x 1 + a 12 x 2 + . + a 1 n x n = b 1 ; a 21 x 1 + a 22 x 2 + . + a 2 n x n = b 2 ; . a m 1 x 1 + a m 2 x 2 + . + a mn x n = b m ,

и обращали бы в минимум линейную целевую функцию
L = c 1 x 1 + c 2 x 2 +…+ c п x n .	(12.2)

Если линейную функцию L нужно обратить в максимум, то вместо нее надо рассмотреть функцию L ´ = – L . Допустимым решением ОЗЛП называется любая совокупность переменных x 1 ≥ 0, x 2 ≥ 0,…, x n ≥ 0, удовлетворяющую уравнениям (12.1). Оптимальным решением будем называть то из допустимых решений, при котором линейная функция (12.2) обращается в минимум. ОЗЛП необязательно должна иметь решение. Может оказаться, что: 1) уравнения (12.1) противоречат друг другу; 2) уравнения (12.1) имеют решение, но не в области неотрицательных значений x 1 , x 2 ,…, x n (ОЗЛП не имеет допустимых решений); 3) допустимые решения ОЗЛП существуют, но среди них нет оптимального (функция L в области допустимых решений не ограничена снизу). Существование допустимых решений ОЗЛП. Прежде чем перейти к формулировке условий существования, приведем некоторые необходимые определения из линейной алгебры. Матрицей системы линейных уравнений (12.1) называется таблица, составленная из коэффициентов при x 1 , x 2 ,…, x n . Расширенной матрицей линейных уравнений называется та же таблица, дополненная столбцом свободных членов b i . Рангом матрицы называется наибольший порядок отличного от нуля определителя, который можно получить, вычеркивая из матрицы какие-то строки и какие-то столбцы. Для совместности системы линейных уравнений (12.1) необходимо и достаточно, чтобы ранг матрицы системы был равен рангу ее расширенной матрицы . Этот общий ранг r называется рангом системы ; он представляет число линейно независимых уравнений среди 63

наложенных ограничений. Ранг системы r не может быть больше числа уравнений т : r ≤ т и не может быть больше общего числа переменных п : r ≤ п . Случай, когда r = п . Система уравнений – ограничений ОЗЛП имеет единственное решение x 1 , x 2 ,…, x n . Если в этом решении хотя бы одна из величин x 1 , x 2 ,…, x n отрицательна, это значит, что полученное решение недопустимо и, следовательно, ОЗЛП не имеет решения. Если все решения x 1 , x 2 ,…, x n неотрицательны, то найденное решение является допустимым . Оно же является и оптимальным . Случай, когда r < п . Тогда, если система совместна, у нее существует бесчисленное множество решений. При этом п – r переменным мы можем придавать произвольные значения (так называемые свободные переменные ), а остальные r выразятся через них (эти r переменных называются базисными ). Если среди решений нет ни одного, для которого все x 1 , x 2 ,…, x n неотрицательны, то это значит, что ОЗЛП не имеет допустимого решения . Если же существуют решения системы (12.1), для которых все x 1 , x 2 ,…, x n неотрицательны, то каждое из них допустимо. Теперь необходимо найти среди допустимых решений оптимальное , т.е. такое решение x 1 , x 2 ,…, x n , для которого линейная функция L (12.2) обращается в минимум. Геометрически область допустимых решений (если она существует) представляет собой выпуклый k -мерный многогранник ( k = п – т ), т.е. часть пространства, для которой выполнены все условия: x 1 ≥ 0, x 2 ≥ 0,…, x n ≥ 0. Решение, лежащее в одной из вершин области допустимых решений, называется опорным решением , а сама вершина – опорной точкой . Решение основной задачи линейного программирования обладает следующими свойствами при любых значениях числа переменных п и числа уравнений т < п : 1. Оптимальное решение, если оно существует, лежит не внутри, а на границе области допустимых решений, в одной из опорных точек , в каждой из которых по крайней мере k из переменных обращаются в нуль. 2. Для того, чтобы найти оптимальное решение, нужно, переходя от одной опорной точки к другой, двигаться в направлении уменьшения линейной функции L , которую требуется минимизировать.

12.2. Задача линейного программирования с ограничениями-неравенствами

Довольно часто ограничения в задаче линейного программирования задаются не уравнениями, а неравенствами. Пусть имеется задача линейного программирования с п переменными x 1 , x 2 ,…, x n , в которой ограничения имеют вид линейных неравенств:

a 11 x 1 + a 12 x 2 + . + a 1 n x n + b 1 ≥ 0; a 21 x 1 + a 22 x 2 + . + a 2 n x n + b 2 ≥ 0; . a m 1 x 1 + a m 2 x 2 + . + a mn x n + b m ≥ 0.

Требуется найти такую совокупность неотрицательных значений x 1 , x 2 ,…, x n , которая удовлетворяла бы неравенствам (12.3), и обращала бы в минимум линейную функцию (12.2). От поставленной таким образом задачи можно перейти к основной задаче линейного программирования. Введем обозначения:

y 1	= a 11 x 1 + a 12 x 2 + . + a 1 n x n + b 1 ,
y 2	= a 21 x 1 + a 22 x 2 + . + a 2 n x n + b 2 ,

. y m = a m 1 x 1 + a m 2 x 2 + . + a mn x n + b m ,

где у 1 , у 2 ,…, у т – некоторые новые, добавочные переменные. Согласно условиям (12.3), эти добавочные переменные так же, как x 1 , x 2 ,…, x n , должны быть неотрицательными.

Источник

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. Решим прямую задачу графически:

Источник