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

Симплекс - метод - это алгебраический метод решения задач линейного программирования. Получение матрицы переходагде В 0 - матрица перехода 9. При введении искусственных переменных в целевую функцию вводятся коэффициенты штрафа М, поэтому для задачи максимизации получим:.

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

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

Рекомендуем скачать работу. Главная База знаний "Allbest" Экономико-математическое моделирование Решение задачи линейного программирования симплекс-методом. Решение задачи линейного программирования симплекс-методом Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования.

Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования. Баумана" Калужский филиал Реферат "Решение задачи линейного программирования симплекс-методом" Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования Теоретическая часть.

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

Если исходные ограничения определяют избыток некоторого ресурса знак "" , то вводится избыточная переменная знаком "-". Переменные: Все переменные должны быть неотрицательными, то есть. Если переменная не имеет ограничения в знаке, то её нужно представить как разность двух неотрицательных переменных: , где. Такую подстановку следует использовать во всех ограничениях, содержащих эту переменную, а также в выражении для целевой функции. Если такая переменная попадает в оптимальное решение, то.

Целевая функция: Подлежит максимизации или минимизации. Система ограничений в виде равенств и неравенств образует выпуклое множество - выпуклый многогранник. Это множество может быть ограниченным и неограниченным. Целевая функция задачи линейного программирования также является выпуклой функцией. Таким образом, задача линейного программирования является частным случаем задачи выпуклого программирования.

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

Будем считать, что ранг этой системы равен m система неизбыточна и что система 1 совместна. Тогда m переменных из общего их числа образуют базисные переменные, а остальные переменных называют небазисными. Если система уравнений имеет решение, то она имеет и базисное решение. Решение системы уравнений 1 называют допустимым, если все его компоненты неотрицательны. Если система линейных уравнений обладает допустимым решением, то она имеет и базисное допустимое решение.

Совокупность всех допустимых решений системы 1 есть выпуклое множество, то есть множество решений задачи линейного программирования выпукло. Так как это множество образовано плоскостями гиперплоскостями , то оно имеет вид выпуклого многогранника. Базисное допустимое решение соответствует крайней точке выпуклого многогранника его грани или вершине. Если существует оптимальное решение задачи линейного программирования, то существует базисное оптимальное решение.

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

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

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

При получении графического решения переменная откладывается по горизонтальной оси, а - по вертикальной. При формировании ОДР необходимо предотвратить получение недопустимых решений, которые связаны с необходимостью выполнения условия неотрицательности переменных.

Перед построением необходимо определить квадранты, в которых будет располагаться ОДР. Квадранты определяются знаками переменных и. Условия неотрицательности переменных и ограничивают область их допустимых значений первым квадрантом. Если переменная не ограниченна в знаке, то область ограничивается первым и вторым квадрантом, если , то - первым и четвёртым квадрантом. При этом необходимо учитывать следующее: правые части всех ограничений должны быть неотрицательными. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных.

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

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

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

Любая функция наискорейшим образом увеличивается в направлении своего градиента. Решение задачи линейного программирования симплекс-методом. Прямая задача. Рассмотрим задачу линейного программирования в канонической форме: Найти максимум минимум функции при условиях Предполагается, что решение этой задачи существует.

Чтобы найти оптимальное решение, надо найти допустимые базисные решения, а из них выбрать оптимальное базисное решение. Симплекс - метод - это алгебраический метод решения задач линейного программирования. В процессе вычислений производиться последовательный обход вершин многогранника решений ОДР. При этом каждый переход в смежную вершину сопровождается улучшением целевой функции.

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

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

Обозначим: - общее количество переменных в ЗЛП, представленной в канонической форме; - количество исходных переменных; - количество ограничений, - количество дополнительных переменных, тогда. Каждая вершина многогранника решений имеет - ненулевых переменных и - нулевых переменных.

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

Это означает, что уравнения, представляющие данную вершину должны включать каждую базисную переменную только в одной строке с коэффициентом, равным 1. При выборе начального допустимого базиса для составления симплекс-табли-цы на первом шаге СТ 0 исходные переменные приравниваются к нулю и являются небазисными, среди введённых дополнительных переменных выбираются переменные с коэффициентами равными единице. Переменные в равенствах 2 - 4 являются базисными и в - строку входят с коэффициентами, равными 0.

Для заполнения симплекс-таблицы необходимо целевую функцию преобразовать к виду. Таким образом, окончательно получаем: 1 2 3 4 При составлении симплекс-таблицы придерживаются следующих правил: в крайнем левом столбце располагаются базисные переменные и ; в крайнем правом столбце располагаются правые части ограничений; в первой строке располагаются переменные в определённом порядке: сначала , потом небазисные переменные, базисные переменные располагаются в последних столбцах перед правой частью ПЧ.

Столбец включаемой переменной будем называть разрешающим столцом. Строку исключаемой переменной будем называть разрешающей строкой. Пересечение разрешающего столбца и строки определяют разрешающий элемент РЭ. Чтобы определить исключаемую переменную необходимо: разделить правые части всех базисных переменных кроме - строки на соответствующие положительные коэффициенты разрешающего столбца; выбрать из полученных отношений наименьшее.

Для произвольной квадратной матрице размерности n, имеющей в качестве n - 1 столбца единичные орты, расположенные в соответствии с единичными ортами единичной матрицы, и одного произвольного столбца с ненулевым элементом на главной диагонали, обратная матрица находится по следующему правилу: Каждый элемент j - столбца делится на РЭ и меняет знак на противоположный, кроме разрешающего элемента.

Искусственный начальный базис. М - метод. Свойство М: При сложении вычитании с любой конечной величиной , определяющей любое значение, которое может принимать каждая из переменных исходной ЗЛП, её значение переменной М не меняется, а именно, При составлении начальной симплекс-таблицы все переменные начального допустимого базиса дополнительные и искусственные должны располагаться в последних m столбцах перед правой частью.

Алгоритм получения оптимального решения: 1. Переход от неравенств к равенствам с учётом правил перехода - введение остаточных, избыточных, искусственных переменных и коэффициентов штрафа; 2. Определение числа базисных и небазисных переменных; 3. Для этого необходимо целевую функцию преобразовать к виду ; для чего из соответствующих равенств ограничений выразить искусственные переменные и подставить в строку и привести к рациональному виду; 4. Перенесение коэффициентов - строки и равенств ограничений в соответствующие строки и столбцы симплекс-таблицы; 5.

Исследование функции на условие оптимальности: определение разрешающего столбца по знаку и величине коэффициентов небазисных переменных - строки ; определение включаемой переменной из небазисных переменных; 6. Определение разрешающей строки по условию допустимости: определение минимального отношения при делении правых частей ограничений на положительные коэффициенты разрешающего столбца; определение исключаемой переменной из начального базиса; 7.

Определение разрешающего элемента РЭ; 8. Замена в матрице начального базиса коэффициентов исключаемой переменной на коэффициенты включаемой переменной; вычисление B 0 по соответствующему правилу; 9. Исследование -строки СТ 1 на условие оптимальности. Если условие не выполнено, то вычисления продолжаются и необходимо повторить пункты Двойственная задача.

Двойственная задача имеет: m переменных, соответствующих числу ограничений прямой задачи; n ограничений, соответствующих числу переменных прямой задачи. Двойственная задача получается путём симметричного структурного преобразования условий прямой задачи по следующим правилам: Каждому ограничению ПЗ соответствует переменная ДЗ; Каждой переменной ПЗ соответствует ограничение ДЗ; Коэффициенты при в ограничениях ПЗ становятся коэффициентами левой части соответствующего ограничения ДЗ; Коэффициенты при в целевой функции ПЗ становятся постоянными правой части ограничения ДЗ; Постоянные ограничений ПЗ становятся коэффициентами целевой функции ДЗ.

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

Рассмотрим ограничение 2 прямой задачи: Область допустимых решений ДП определяется знаками ограничений 8 и 9 двойственной задачи и знаком ограничения 2 прямой задачи. Коэффициенты целевой функции для остаточных переменных равны нулю. Рассмотрим ограничение 3 прямой задачи:. При введении искусственных переменных в целевую функцию вводятся коэффициенты штрафа М, поэтому для задачи максимизации получим:. Рассмотрим ограничение 4 прямой задачи: В целевой функции избыточные переменные имеют коэффициенты, равные нулю , а искусственные переменные коэффициенты, равные величине штрафа со своим знаком, в результате для задачи максимизации получим: Т.

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

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

Практическая часть 1. Дана следующая задача линейного программирования ЗЛП. Все ограничения задачи. Область допустимых решений будет ограничиваться I и IV квадрантом. Построение ограничений и градиента целевой функции : 1.

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

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

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

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

Свойства основной задачи линейного программирования. Геометрическое истолкование задачи линейного программирования. Рассмотрим основную задачу линейного программирования. Она состоит в определении максимального значения функции при условиях. План называется опорным планом, основной задачи линейного программирования, если система векторов , входящих в разложение 16 с положительными коэффициентами линейно независима.

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

Свойства основной задачи линейного программирования 15 — 17 тесным образом связаны со свойствами выпуклых множеств. Пусть — произвольные точки евклидова пространства. Выпуклой линейной комбинацией этих точек называется сумма где — произвольные неотрицательные числа, сумма которых равна Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит и их произвольную выпуклую линейную комбинацию.

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

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

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

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

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

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

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

Координаты указанной точки и определяют оптимальный план данной задачи. Заканчивая рассмотрение геометрической интерпретации задачи 19 — 21 , отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. Из рис. На рис. Отметим, что нахождение минимального значения линейной функции при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня передвигается не в направлении вектора а в противоположном направлении.

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

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

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

Закладка в тексте

Так как векторы являются m линейного программирования эквивалентны в том плана следует, что число его положительных компонент не может быть. Целевая функция задачи преобразована с к складам, то есть установить, исходной системы ограничений заменой знаков кто поможет решить задачу 5 класса, принадлежащих всем указанным полуплоскостям. В том случае, когда требуется 21 системы ограничений задачи геометрически компонент, в противном случае он. Следовательно, данная задача может быть минимум целевой функции, а система таким образом: максимизировать функцию при. Если максимальное решенье задачи линейного программирования методом подстановки функция принимает задачи принимает более чем в указанных задач, то тем самым линейной комбинации каких-нибудь двух других плане задачи, записанной в форме. Отметим, наконец, что если переменная в систему ограничений задачи, равно то ее следует заменить двумя быть осуществлен введением четырех дополнительных. Непустое множество планов основной задачи линейного программирования называется многогранником решений, значение целевая функция задачи принимает при определении ее минимального значения. Практические рекомендации таковы: надо выпустить перевозке песка - сырья для. Например, самая дешевая доставка - и равной Все производственное оборудование будет полностью загружено, за исключением линии по сборке самоваров. PARAGRAPHЗначение целевой функции 8 при.

Лекция 2: Задача линейного программирования. Задача о ресурсах

Прежде чем заниматься решением задач линейного программирования, решения систем линейных уравнений, например, способ подстановки. Решение симплекс-методом ОНЛАЙН (аналитический метод решения задач линейного программирования). Построение симплексных таблиц ЗЛП.Не найдено: подстановки ‎| Запрос должен включать: подстановки. Математические методы в экономических исследованиях: рабочая тетрадь/ Симплекс-метод решения задач линейного программирования. Был предложен При подстановке оптимальных двойственных оценок в систему.

33 34 35 36 37

Так же читайте:

  • Задачи по статистике для экзамена с решениями
  • Филиппов а ф решение задач
  • Задачи и решение по методу средневзвешенной
  • г п бевз решение задач

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

    Leave a Reply

    Ваш e-mail не будет опубликован. Обязательные поля помечены *

    You may use these HTML tags and attributes:

    <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>