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

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

Источник

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. Все остальные элементы матрицы заменяют по правилу прямоугольника.

Источник

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

Определение 1. Общей задачей ЛП называется задача нахождения максимального (минимального) значения линейной целевой функции (1) при условиях , (2) , (3) , ,(4), где ,,— заданные постоянные величины и. Определение.2. Функция Z называется целевой функцией задачи (1 — 4), —проектными параметрами задачи, а условия (2 — 4) ограничениями данной задачи. Определение 3. Стандартной задачей ЛП называется задача нахождения целевой функции (1) при выполнении условий (2), (4), где k=m,l=n, т.е. когда ограничения заданы только в виде неравенств (2), и все проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде равенств отсутствуют: , , . Определение 4. Канонической (или основной) задачей ЛП называется задача нахождения максимального (минимального) значения функции (1) при выполнении условий (3), (4), где k=0,l=n,mn, т.е. когда ограничения заданы только в виде равенств (3), и все проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде неравенств (2) отсутствуют: , , ,. Определение 5. Совокупность значений проектных параметров , удовлетворяющих ограничениям задачи (2-4), называетсядопустимым решением, или планом. Определение 6. План , при котором целевая функция (1) принимает свое максимальное (минимальное) значение, называетсяоптимальным, т.е. . Все три формы задачи ЛП эквивалентны, ибо каждая из них с помощью некоторых преобразований может быть переписана в форме другой задачи. При этом необходимо пользоваться следующими правилами:

1. Задачу минимизации функции можно свести к задаче максимизации, и, наоборот, путем замены знаков коэффициентов на противоположные, поскольку.
2. Ограничения-неравенства (2) можно заменить эквивалентными ограничениями-равенствами путем введения дополнительных неотрицательных переменных следующим образом:

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

1. Каждое ограничение-равенство вида (3) можно записать в виде двух неравенств .
2. Переменная , неограниченная условием неотрицательности вида (4), можно заменить разностью двух дополнительных неотрицательных переменных:,,.

1. Геометрическая интерпретация задачи линейного программирования

Рассмотрим задачу, состоящую в определении максимального значения функции: (5) при условиях , (6) , (7). Эта задача ЛП в стандартной форме с двумя переменными. Каждое неравенство вида (6), (7) геометрически определяет полуплоскость соответственно с граничными прямыми (8). При этом вектор , как градиента функции, указывает ту полуплоскость, которая определяется неравенством, а вектор— полуплоскость, определяемую неравенством. Если система неравенств (6), (7) совместна, то область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Пересечение этих полуплоскостей образует выпуклый многоугольник решений, или область допустимых решений (ОДР). Таким образом, исходная задача ЛП состоит в нахождении таких точек многоугольника решений, в которых целевая функция Z принимает максимальное (минимальное) значение. Эта точка существует тогда, когда многоугольник решений не пуст, и на нем целевая функция ограничена. Линейная целевая функция достигает точек экстремума только на границе выпуклого многоугольника. Рассмотрим градиент функции цели . Это будет вектор(см. рис.2.), указывающий направление возрастания функции цели. Очевидно, если взять обратное направление, то это будет направлением убывания функции цели. Если построить произвольную прямую— const, то её движение параллельно самой себе в направлении вектора приведет к возрастанию функции цели. При этом для допустимости решения эта прямая должна иметь хотя бы одну общую точку с многоугольником решений. Два крайних положения этой прямой в ОДР соответствуют наименьшему и наибольшему значениям целевой функции. При этом могут встретиться случаи, изображенные на рис.2-5, когда исходная задача имеет единственное решение (минимальное и максимальное значение) (рис.2), множество решений (координаты любой точки прямойна рис.3), и решение исходной задачи не существует в силу неограниченности целевой функции (рис.4) или несовместности системы неравенств (6), (7) (рис.5).

Источник

Читайте также:  Какую среду программирования выбрать