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

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

Источник

Переход к канонической форме ЗЛП

Каноническая форма ЗЛП — задача линейного программирования вида ax = b , где a — матрица коэффициентов, b — вектор ограничений.

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .

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

Математическая модель называется канонической, если ее система ограничений представлена в виде системы m линейно независимых уравнений (ранг системы r=m), в системе выделен единичный базис, определены свободные переменные и целевая функция выражена через свободные переменные. При этом правые части уравнений неотрицательны (b_i ≥ 0).

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

Решение системы называется базисным, если в нем свободные переменные равны 0, и оно имеет вид:
X_баз = (0, 0; b₁, …, b_m), f(X_баз) = c₀

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

Базисное решение называется опорным, если оно допустимо, т.е. все правые части уравнений системы (или неравенств) положительны b_i ≥ 0.

Компактная форма канонической модели имеет вид:
AX = b
X ≥ 0
Z = CX(max)

Понятие допустимого решения, области допустимых решений, оптимального решения задачи линейного программирования.
Определение 1 . Вектор X, удовлетворяющий системе ограничений ЗЛП, в том числе и условиям неотрицательности, если они имеются, называется допустимым решением ЗЛП.
Определение 2 . Совокупность всех допустимых решений образует область допустимых решений (ОДР) ЗЛП.
Определение 3 . Допустимое решение, для которого целевая функция достигает максимума (или минимума), называется оптимальным решением.

• эти значения удовлетворяли некоторой системе линейных уравнений или неравенств;
• при этих значениях целевая функция обращалась бы в минимум или максимум.

• неравенства, входящие в систему ограничений задачи, преобразовать в уравнения с помощью введения дополнительных переменных;
• если целевая функция F→max (максимизируется), она заменяется на функцию –F→ min (которая минимизируется).

Пример №1 . Следующую задачу ЛП привести к каноническому виду: F(X) = 5x₁ + 3x₂ → max при ограничениях:
2x₁ + 3x₂≤20
3x₁ + x₂≤15
4x₁≤16
3x₂≤12
Модель записана в стандартной форме. Введем балансовые неотрицательные переменные x₃, x₄, x₅, x₆, которые прибавим к левым частям ограничений-неравенств. В целевую функцию все дополнительные переменные введем с коэффициентами, равными нулю:
В первом неравенстве смысла (≤) вводим базисную переменную x₃. Во 2-ом неравенстве смысла (≤) вводим базисную переменную x₄. В третьем неравенстве вводим базисную переменную x₅. В 4-м неравенстве — базисную переменную x₆. Получим каноническую форму модели:
2x₁ + 3x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ = 20
3x₁ + 1x₂ + 0x₃ + 1x₄ + 0x₅ + 0x₆ = 15
4x₁ + 0x₂ + 0x₃ + 0x₄ + 1x₅ + 0x₆ = 16
0x₁ + 3x₂ + 0x₃ + 0x₄ + 0x₅ + 1x₆ = 12
F(X) = 5x₁ + 3x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ → max Пример №2 . Найти два опорных решения системы
x₁ + 2x₄ – 2x₅ = 4
x₃ + 3x₄ + x₅ = 5
x₂ + 3x₅ = 2 Ответ: X = (4;2;5;0;0) Пример №3 . Привести к канонической форме следующую ЗЛП.
F = 2x₁ — x₂ + 4x₃ -2x₄ → min
при ограничениях:
7x₁ –x₂ +5x₃ + x₄ = -10
3x₁ +5x₂ -9x₃ + 2x₄ = 6
x₁ –x₂ -2x₃ + 6x₄ ≥ 7
x₁ +x₂ -5x₃ ≤ 11
7x₁ –x₂ -3x₃ — x₄ ≤ 9
x₁ ≥0 , x₂ ≥0 (обратите внимание, что переменные x₃ и x₄ имеют произвольный знак) Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции
— F = -2x₁ + x₂ — 4x₃ +2x₄ → max 2. В левые части трех последних неравенств внести дополнительные переменные x₅, x₆, x₇ со знаком плюс или минус в зависимости от знака неравенства.
7x₁ –x₂ +5x₃ + x₄ = -10
3x₁ +5x₂ -9x₃ + 2x₄ = 6
x₁ –x₂ -2x₃ + 6x₄ –x₅ = 7
x₁ +x₂ -5x₃ +x₆ = 11
7x₁ –x₂ -3x₃ — x₄ +x₇ = 9
x₁ ≥0 , x₂ ≥0, x₅ ≥0 , x₆ ≥0, x₇ ≥0 3. Так как переменные x₃ и x₄ произвольного знака, то они заменяются разностями неотрицательных переменных.
7x₁ –x₂ +5(x₈ – x₉) + (x₁₀ – x₁₁) = -10
3x₁ +5x₂ -9(x₈ – x₉) + 2(x₁₀ – x₁₁) = 6
x₁ –x₂ -2(x₈ – x₉) + 6(x₁₀ – x₁₁) –x₅ = 7
x₁ +x₂ -5(x₈ – x₉) +x₆ = 11
7x₁ –x₂ -3(x₈ – x₉) — (x₁₀ – x₁₁) +x₇ = 9
x₁ ≥0 , x₂ ≥0, x₅ ≥0 , x₆ ≥0, x₇ ≥0 , x₈ ≥0, x₉ ≥0 , x₁₀ ≥0, x₁₁ ≥0 4. Соответствующая целевая функция примет вид:
— F = -2x₁ + x₂ — 4(x₈ – x₉) +2(x₁₀ – x₁₁) → max см. также Как привести каноническую задачу линейного программирования к стандартной форме Пример №2 . Преобразовать следующие задачи ЛП к канонической форме и решить их симплекс-методом.

Источник

11.Общая, каноническая, стандартная задача линейного программирования.

В общем виде задачи об использовании ресурсов и о диете можно записать в общем виде. Пусть дана система m линейных неравенств с n- неизвестными.

(7)

И линейная функция (8)

Необходимо найти такое решение Х=(х1,х2,…,хn) удовлетворяющее неотрицательности

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

Система(7) система ограниченная ЗЛП, функция (8) – целевая функция.

Допустимым решением ЗЛП называется решение Х=(х1,х2,…,хn) системы ограничении удовлетворения условиям неотрицательности.

Оптимальным решением решения ЗЛП наз-ся план х1,х2,…,хn при которой целевая функция принимает оптимальное значение. Мы рассмотрели ЗЛП в которых система ограничений состоят только из неравенств, такие ЗЛП называются СТАНДАРТНЫМИ. Но система ограничений может состоять и из линейных неравенств и из линейных уравнений – ОБЩАЯ ЗЛП. Если же система ограничений ЗЛП состоит только из уравнений то ЗЛП называют КАНОНИЧЕСКОЙ.

12. Симплексная форма злп.

Допустимое решение ЗЛП называется Базисным, если все его свободные неизвестные равны нулю, а соответствующие ему значения целевой функции f(b1,b2,…,br,0)=b0 называется базисным.

Симплексная форма ЗЛП удовлетворяет следующим требованиям: система ограничений должна быть такой что:

1. Все ограничения записаны в виде уравнений.
2. Правые части уравнений неотрицательны bi≥0, i=
3. Система состоящая из r уравнении имеет r базисных уравнений

Целевая ф-ия удовлетворяет условиям:

1. Она содержит только свободные переменные
2. Обязательная минимизация ( случай нахождения мах сводится на задаче нахождения мин по формуле махf=-minf
3. Все слагаемые целевой ф-ии перенесены влево кроме b0

13. Матричная форма симплексного метода. Критерии оптимальности плана и его отсутствия. Симплексные преобразования.

В симплексной форме ЗЛП соответствует симплексная матрица состоящая из коэффициентов при неизвестных, правых частей уравнений и функций.

Базисное решение =(в1,в2,….,в0,0…,0) и базисное значение целевой функции. При этом мы каждый раз будем получать новую симплексную матрицу. По ней можно определить является ли базисное решение оптимальным с помощью следующего критерия.

Критерий оптимальности плана.

Если в последней сторке (целевой строке) симплексной матрицы, все элементы положительны без учеты последнего в0, то соот-ии этой матрице на опорный план оптимален.

Критерий отсутствия оптимальности. Если в симплексной матрице имеется столбец в котором последний элемент Cs>0 а все остальные элементы не положительны то ЗЛП не имеет оптимального плана minf=-∞.

Если в симплексной матрице не выполняется оба критерия то в необходимо перейти к следующей матрице с помощью разрешающего элемента. ais >0. A)определяется разрешающий столбец по наибольшему из положительных элементов целевой строки. Cs=max(Cj). Целевая строка выбирается по наилучшему значению отношения элемента последнего столбца к соответствующему элементу S-го столбца. Bi/ais=min (bk/aks), aks>0.

Б) На пересечении разрешающего столбца и разрешающей строки и находится разрешающий элемент. Ais>0

Когда разрешающий элемент ais производят симплексные преобразование матрицы:

1. Все элементы разрешающей строки делятся на разрешающий элемент.
2. Все элементы разрешающего столбца кроме разрешающего элемента заменяют 0.
3. Все остальные элементы матрицы заменяют по правилу прямоугольника.

Источник