Составить математическую модель задачи линейного программирования. Решение задачи линейного программирования симплекс-методом Основные понятия моделирования

Государственное образовательное учреждение высшего

профессионального образования

"Московский государственный технический университет им. Н.Э. Баумана"

Калужский филиал

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

Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования

Теоретическая часть.

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

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

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

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

,

Ограничения:

1. Правые части всех ограничений должны быть неотрицательными . Если какой-нибудь из коэффициентов < 0, то необходимо коэффициенты ограничения слева и справа домножить на "-1" и изменить знак данного ограничения на противоположный;

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

Если исходные ограничения определяют расход некоторого ресурса (знак ""), то переменные следует интерпретировать как остаток, или неиспользованную часть ресурса. В этом случае – остаточная переменная и вводится в уравнение со знаком "+".

Если исходные ограничения определяют избыток некоторого ресурса (знак ""), то вводится избыточная переменная знаком "-".

Переменные:

Все переменные должны быть неотрицательными, т.е. .

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

Если такая переменная попадает в оптимальное решение, то

Целевая функция:

Подлежит максимизации или минимизации.

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

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

(1)

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

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

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

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

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

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

В результате построений получается многоугольник, который определяет пространство решений. Если одно из ограничений имеет знак "=", то ОДР вырождается в отрезок.

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

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

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

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

Прямая задача.

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

Найти максимум (минимум) функции при условиях

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

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

Вычислительные процедуры симплекс - метода.

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

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

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

Каждая вершина многогранника решений имеет - ненулевых переменных и () - нулевых переменных.

Ненулевые переменные называются базисными, нулевые переменные – небазисными.

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

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

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

При составлении симплекс-таблицы придерживаются следующих правил:

в крайнем левом столбце располагаются базисные переменные и ;

в крайнем правом столбце располагаются правые части ограничений;

в первой строке располагаются переменные в определённом порядке:

сначала , потом небазисные переменные, базисные переменные располагаются в последних столбцах перед правой частью (ПЧ). Запишем коэффициенты в СТ(0):

Оптимальность любой из вершин определяется коэффициентами при небазисных переменных в – строке текущей симплекс-таблицы:

Для задачи максимизации данная вершина является оптимальной, если все коэффициенты при небазисных переменных в – строке являются неотрицательными (>0);

Для задачи минимизации данная вершина является оптимальной, если все коэффициенты при небазисных переменных в – строке являются неположительными (< 0).

Если в задаче максимизации (минимизации) у одной небазисной переменной в – строке коэффициент <0(>0), то текущая точка не является оптимальной и необходимо изменить базис. Для этого выбирают небазисную переменную, имеющую максимально отрицательный (положительный) коэффициент в – строке. Выбранная небазисная переменная будет включаться в новый базис, поэтому называется включаемой переменной. Базисная переменная, которая будет выведена из базиса, называется исключаемой переменной.

Исключаемой переменой будет та базисная переменная, которая первой обратится в "0" при переходе в смежную вершину после ввода включаемой переменной.

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

Строку исключаемой переменной будем называть разрешающей строкой.

Пересечение разрешающего столбца и строки определяют разрешающий элемент (РЭ).

Чтобы определить исключаемую переменную необходимо:

разделить правые части всех базисных переменных (кроме - строки) на соответствующие положительные коэффициенты разрешающего столбца;

выбрать из полученных отношений наименьшее.

Делить на "0" и отрицательную величину нельзя, т. к. это приводит к отсутствию пересекающейся вершины или к вершине вне ОДР.

Для перехода в смежную вершину необходимо сформировать матрицу перехода B(0), которая определит связь между СТ(0) и СТ(1): СТ(1) = В(0) СТ(0).

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

Каждый элемент j – столбца делится на РЭ и меняет знак на противоположный, кроме разрешающего элемента.

Искусственный начальный базис. М – метод.

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

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

Переменные R определяют начальный допустимый базис с точки зрения возможного дальнейшего перехода в одну из вершин ОДР. За использование искусственных переменных в целевой функции вводится штраф М. В задаче максимизации М отрицательное (М<<0), в задаче минимизации М положительное (М>>0).

Свойство М: При сложении (вычитании) с любой конечной величиной , определяющей любое значение, которое может принимать каждая из переменных исходной ЗЛП, её значение (переменной М) не меняется, а именно,

Формула (1.2), ограничений не отрицательности переменных (есть, нет) - формула (1.3) (1.1) i = 1,… m (1.2) (1.3) Алгоритм решения задач линейного программирования требует приведения их постановки в канонический вид, когда целевая функция...

Основные понятия моделирования

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

Моделирование – это универсальный способ изучения процессов и явлений реального мира. Особое значение моделирование приобретает при изучении объектов, недоступных прямому наблюдению и исследованию. К ним, в частности, относятся социально-экономические явления и процессы.

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

Экономика – это система общественного производства, осуществляющая собственно производство, распределение, обмен и потребление необходимых обществу материальных благ.

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

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

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

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

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

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

найти экстремум функции

при ограничениях

при условиях неотрицательности

Введем обозначения:

Запасы i –го вида ресурса;

затраты i –го вида ресурса на производство j –го вида продукции;

прибыль от реализации единицы j –го вида продукции.

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

Компактная запись показывает, что модель общей задачи линейного программирования включает пять основных элементов:

Переменные величины, значение которых отыскивается в процессе решения задачи;

Технико-экономические коэффициенты при переменных в ограничениях;

Объем правой части неравенств, которые называют константами задачи;

Коэффициенты при переменных в целевой функции, которые называют оценками переменных;

Индекс переменной;

Индекс ограничения.

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

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

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

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

Переменные могут выражаться в самых различных единицах измерения: га, ц, кг, шт., головах и т.д. По характеру переменные подразделяют на основные, дополнительные и вспомогательные. К основным переменным относят искомые виды деятельности: отрасли хозяйства, виды кормов, марки машин. Дополнительными называют переменные, которые образуют в процессе превращения неравенств в уравнения. Они могут означать недоиспользованную часть ресурсов, излишек над правой частью неравенства (если это неравенство типа «не более»). Вспомогательные переменные включают в задачу для того, чтобы определить расчетные величины приобретаемых производственных ресурсов, расчетные величины показателей экономической эффективности производства.

Дополнительные и вспомогательные переменные всегда имеют единичные коэффициенты (+1 или –1).

Технико-экономические коэффициенты (a ij) при переменных в системе ограничений выражают нормы затрат производственных ресурсов или норму выхода продукции в расчете на единицу измерения переменной величины.

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

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

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

Правой части ограничений (b i) называют константами, т.е. постоянными величинами. К ним относят объемы производственных ресурсов – земли, труда, техники, удобрений, капиталовложений и т.д. Производственные ресурсы должны быть определены с учетом их фактического состояния и обязательно учитывать период планирования. Кроме того, те производственные ресурсы, использование которых в течение года неравномерно, рассчитывают не только за год в целом, но и по отдельным напряженным периодам или месяцам (трудовые ресурсы).

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

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

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

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

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

v отражать в задаче только те условия, которые действительно ограничивают возможности производства;

v слишком большое количество ограничений увеличивает размеры задачи и делает ее трудноразрешимой

Ограничения бывают трех типов: равенства (=), неравенства типа меньше либо равно (≤), неравенства типа больше либо равно (≥). Например,

где i = 1, 2, … , m . Коэффициенты при переменных обозначаются a ij , где индекс i – номер ограничения, индекс j – номер переменной, свободные члены (правая часть ограничений) обозначаются b i , индекс i – номер ограничения.

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

По смыслу все ограничения можно подразделить на основные, дополнительные и вспомогательные.

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

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

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

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

Условие неотрицательности переменных записывается в виде

x j ≥ 0, j = 1, 2, …, n .

В реальной жизни производства, исходя из условий задания, по данной записи структурной экономико-математической модели (ЭММ) составляется перечень переменных величин и ограничений, подготавливается исходная информация, строится развернутая ЭММ задачи, которая затем записывается в виде матрицы (таблицы), вводится в компьютер и по соответствующей программе производится расчет и анализ результатов.i = 1, …, m , (1.5)

j = 1, …, n . (1.6)

Вектор x = (x 1 , x 2 , …, x n), компоненты x j которого удовлетворяют ограничениям (1.2) и (1.3) [или (1.5) и (1.6) в задаче на минимум], называется допустимым решением или допустимым планом задачи ЛП. Совокупность всех допустимых планов называется множеством допустимых планов.

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

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

Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на – 1;

3) если среди ограничений имеются неравенства, то путем введения дополнительных переменных неотрицательных переменных они преобразуются в равенства. Например, дополнительные переменные S j в ограничения типа меньше либо равно (£) вводятся со знаком плюс:

Дополнительные переменные S j в ограничения типа больше либо равно (≥) вводятся со знаком минус:

Для устранения отрицательности дополнительных переменных – S j вводят искусственные переменные со знаком плюс + М j c очень большими значениями.

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

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

Определение. Математическое выражение целевой функ­ции и ее ограничений называется математической моделью экономической задачи.

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

при ограничениях:

где x j - неизвестные; a ij , b i , c j - заданные постоянные вели­чины.

Все или некоторые уравнения системы ограничений могут быть записаны в виде неравенств.

Математическая модель в более краткой записи имеет вид

при ограничениях:

Определение. Допустимым решением (планом) зада­чи линейного программирования называется вектор = (x 1 , x 2 ,..., x п), удовлетворяющий системе ограничений.

Множество допустимых решений образует область допус­тимых решений (ОДР).

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

Базисное допустимое решение (х 1 , х 2 ,..., x r , 0, …, 0) яв­ляется опорным решением, где r - ранг системы ограничений.

Математическая модель задачи ЛП может быть каноничес­кой и неканонической.

7.Решение задач линейного программирования графическим методом . Графики функций-ограничений. Линии уровня.

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

Наиболее простым и наглядным методом линейного про­граммирования является графический метод. Он применяется для решения задач ЛП с двумя переменными, заданными в не­канонической форме, и многими переменными в канонической форме при условии, что они содержат не более двух свободных переменных.

С геометрической точки зрения в задаче линейного про­граммирования ищется такая угловая точка или набор точек из допустимого множества решений, на котором достигается самая верхняя (нижняя) линия уровня, расположенная дальше (ближе) остальных в направлении наискорейшего роста.

Для нахождения экстремального значения целевой функ­ции при графическом решении задач ЛП используют вектор L () на плоскости Х 1 ОХ 2 , который обозначим . Этот вектор показывает направление наискорейшего изменения це­левой функции. Другими словами вектор - нормаль линии уровня L ()

где е 1 и е 2 - единичные векторы по осям OX 1 и ОX 2 соответ­ственно; таким образом, = (∂L/∂х 1 , ∂L/∂х 2 ). Координатами вектора являются коэффициенты целевой функции L(). Построениелинии уровня будет рассмотрено подробно при решении практических задач.

Алгоритм решения задач

1. Находим область допустимых решений системы ограни­чений задачи.

2. Строим вектор .

3. Проводим линию уровня L 0 , которая перпендикулярна .

4. Линию уровня перемещаем по направлению вектора для задач на максимум и в направлении, противоположном , для задач на минимум.

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

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

Где 0 ≤ t ≤ 1, 1 и 2 - оптимальные решения в угловых точках ОДР.

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

5. Находим координаты точки экстремума и значение це­левой функции в ней.

Пример 3. Выбор оптимального варианта выпуска изделий

Фирма выпускает 2 вида мороженого: сливочное и шоко­ладное. Для изготовления мороженого используются два ис­ходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы даны в таблице.

Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное мороженное, но не бо­лее чем на 100 кг.

Кроме того, установлено, что спрос на шо­коладное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого 16 р., шоколадного - 14 р.

Какое количество мороженого каждого вида должна про­изводить фирма, чтобы доход от реализации продукции был максимальным?

Решение. Обозначим: x 1 - суточный объем выпуска сли­вочного мороженого, кг; x 2 - суточный объем выпуска шоко­ладного мороженого, кг.

Составим математическую модель задачи.

Цены на мороженное известна: соответственно 16руб и 14руб., поэтому целевая функция будет иметь вид:

Установим ограничения по молоку для мороженного. Расход его на сливочное мороженное - 0,8кг, на шоколадное - 0,5кг. Запас молок 400кг. Поэтому первое неравенство будет иметь вид:

0,8х 1 + 0,5х 2 ≤400 – первое неравенство – ограничение. Аналогично составляются остальные неравенства.

В результате получится система неравенств. что область решения каждого неравенства. Это можно сделать, подставив в каждое из неравенств координаты точки О(0:0). В результате получим:

Фигура OABDEF - область допустимых решений. Строим вектор (16; 14). Линия уровня L 0 задается уравнением 16x 1 +14x 2 =Const. Выбираем любое число, например число 0, тогда 16x 1 +14x 2 =0. На рисунке для линии L 0 выбрано некоторое положительное число, не равное нулю. Все линии уровня параллельны между собой. Вектор нормаль линии уровня.

Перемещаем линию уровня по направлению вектора. Точ­кой выхода L 0 из области допустимых решений является точка D , ее координаты определяются как пересечение прямых, за­данных уравнениями:

Решая систему, получим координаты точки D (312,5; 300), в которой и будет оптимальное решение, т.е.

Таким образом, фирма должна выпускать в сутки 312,5 кг сли­вочного мороженого и 300 кг шоколадного мороженого, при этом доход от реализации составит 9 200 р.

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

9.Симплекс-метод . Характеристика и алгоритм метода, применимость его.

Для решения задачи симплекс методом необходимо :

1. Указать способ нахождения оптимального опорного решения

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

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

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

1. Привести задачу к каноническому виду

2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение, в виду несовместимости системы ограничений)

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

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается

5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

10.Транспортная задача. Определение, виды, методы нахождения начального решения транспортной задачи.

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

1. Нахождение исходного опорного решения;

2. Проверка этого решения на оптимальность;

3. Переход от одного опорного решения к другому.

Наиболее простыми являются так называемые линейные детерминированные модели. Они задаются в виде линейной формы управляющих переменных (х ):

W = a 0 + a 1 x 1 + … + a k x k

при линейных ограничениях вида

b 1 j x 1 + b 2 j x 2 + … + b kj x k ³ b j , j = 1,…, q 1 ;

c 1 j x 1 + c 2 j x 2 + … + c kj x k = c j , j = 1,…, q 2 ;

d 1 j x 1 + d 2 j x 2 + … + d kj x k £ d j , j = 1,…, q 3 .

Общее число ограничений m = q 1 + q 2 + q 3 может превосходить число переменных (m > k ). Кроме того, обычно вводится условие положительности переменных (x i ³ 0).

Поверхность отклика для линейной модели представляет собой гиперплоскость . Например, рассмотрим линейную модель двух переменных следующего вида:

W = –2x 1 –3x 2 (2.2)

при следующих ограничениях

x 1 – 4x 2 £ 4;

–2x 1 + x 2 £ 2;

х 1 ³ 0; x 2 ³ 0.

Область допустимых значений (область определения) OABCD для модели (2.2) образована ограничениями (2.3) (Рис. 2.2). Поверхность отклика представляет собой плоский многоугольник OA"B"C"D" (рис. 2.2, б ).

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

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

При исследовании ДЛА линейные модели используются редко и почти исключительно при приближенном описании задач.

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

Исследование линейных моделей не представляет труда. В частности влияние каждой из переменных на характеристики модели вида

W = a 0 + a 1 x 1 + a 2 x 2 + …+ a k x k

задается ее коэффициентами:

, i = 1,…, k.

Для нахождения оптимума линейной модели W опт разработан эффективный симплекс-метод.

К линейным иногда сводятся простейшие модели стоимости, рассматриваемые как совокупность производимых затрат.

Примером такой модели является классическая модель стоимости перевозок (транспортная задача) (Рис. 2.4).

Имеется k пунктов производства
(i = 1,…, k ) и m пунктов потребления
(j = 1,…, m ) некоторого продукта. Количество продукта, произведенного в каждом из k пунктов производства, равно a i ; количество продукта, необходимого в каждом из m пунктов потребления, равно b j .

Предполагается равенство общего производства и потребления:

Количество продукта, перевозимого из i -го пункта производства в j -й пункт потребления, равно x ij ; стоимость перевозки единицы этого продукта – с ij .

Суммарная стоимость перевозок С S задается линейной моделью :

при следующих ограничениях

К линейным также относятся модели в виде линейных дифференциальных уравнений (обыкновенных или в частных производных).

Линейное обыкновенное дифференциальное уравнение n -го порядка имеет вид

Начальные условия записываются как

Линейное дифференциальное уравнение в частных производных имеет вид

Модель, заданная в виде дифференциального уравнения в частных производных, включает начальные и граничные условия (условия на границе области определения функции F(t )).

2.3. Исследование простейшей математической модели
работы газотурбинного двигателя

Газотурбинный двигатель (ГТД) является основной силовой установкой современных самолетов.

Схема ГТД имеет вид, показанный на рис. 2.5.

Здесь 1 – входной диффузор; 2 – компрессор; 3 – камера сгорания; 4 – турбина;
5 – выходное сопло.

Цикл работы ГТД включает следующие этапы:

1) Набегающий со скоростью V поток воздуха через диффузор поступает в компрессор.

2) Компрессор, вращаясь на одном валу с турбиной, сжимает воздух, который поступает в камеру сгорания.

3) В камеру сгорания постоянно впрыскивается топливо (керосин), которое смешивается со сжатым воздухом.

4) Газ, образующийся от сгорания, поступает на турбину, которая разгоняет его до скорости W .

5) С этой скоростью газ через сопло выбрасывается в атмосферу.

За счет того, что W > V , образуется сила тяги Р , которая позволяет самолету осуществлять полет в атмосфере.

Изменение силы тяги осуществляется путем изменения скорости впрыска топлива в камеру сгорания с помощью перемещения ручки управления двигателем (РУД). Перемещение РУД на определенный угол d РУД осуществляется либо вручную летчиком, либо с помощью исполнительного устройства по сигналам от САУ полетом. Увеличение значения d РУД вызывает возрастание силы Р , а уменьшение – убывание этой силы.

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

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

, (2.11)

где t > 0 – постоянная времени двигателя, зависящая кроме конструктивных характеристик также от температуры окружающего воздуха, его влажности и других внешних факторов; k [кг/град] – коэффициент пропорциональности.

Начальное условие для уравнения (2.11) записывается как

Р (0) = Р 0 . (2.12)

Таким образом,уравнение (2.11) совместно с начальным условием (2.12) представляет собой простейшую математическую модель работы ГТД, записанную в виде обыкновенного дифференциального уравнения 1-го порядка.

Для определения коэффициента пропорциональности k используются градуировочные графики зависимости тяги от угла поворота РУД, построенные на основе экспериментальных данных. Тангенс угла наклона графика равен искомому коэффициенту.

При отклонении РУД тяга Р нарастает и затем стабилизируется на определенном предельном значении, т.е. ГТД является инерционным объектом.

Предельное значение силы тяги получаем из (2.11), когда скорость ее изменения равна нулю:

. (2.13)

Длительность нарастания зависит от значения постоянной времени двигателя t. Процесс считается установившимся при t = t уст, когда тяга входит в так называемый пятипроцентный коридор от предельного значения силы тяги (рис. 2.6). Чем больше t, тем инерционнее двигатель и, следовательно, больше t уст.

На рис. 2.7 показано поведение силы тяги в зависимости от угла отклонения РУД при t = 0,5.

Сила тяги при взлете, когда РУД отклонена на 10°, выходит на установившийся режим на третьей секунде и достигает величины 3390 кг. Через десять секунд после взлета, когда РУД отклонена на 20°, сила тяги устанавливается на величине 6780 кг, и еще через десять секунд, когда РУД отклонена на 30°, сила тяги устанавливается на величине 10170 кг. Предельное значение силы тяги равно
14270 кг.

Похожая информация.

МОДЕЛЬ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

2 Методы реализации моделей линейного программирования

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

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

Модели ЛП используются для решения двух основных типов прикладных задач:

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

2) транспортной задачи (нахождение оптимального плана различного рода перевозок, оптимального плана распределения разных средств по объектам различного назначения и т. п.)

МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Требуется найти неотрицательные значения переменных

удовлетворяющих линейным ограничениям в виде равенств и неравенств

,

где – заданные числа,

и обеспечивающих экстремум линейной целевой функции

,

где – заданные числа, что записывается в виде

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

Область допустимых решений – множество всех допустимых решений.

Оптимальное решение
, для которого .

Замечания

1. Приведенная модель ЛП является общей . Различают также стандартные и канонические формы моделей ЛП.

2. Условия существования реализации модели ЛП:

– множество допустимых решений – не пустое;

– целевая функция ограничена на (хотя бы сверху при поиске максимума и снизу при поиске минимума).

3.ЛП основывается на двух теоремах

Теорема 1. Множество G , определяемое системой ограничений вида, есть выпуклое замкнутое множество (выпуклый многогранник в с угловыми точками - вершинами .)

Теорема 2. Линейная форма , определенная на выпуклом многограннике

j =1,2,…,s

i=s +1,s+2,…,m ,

достигает экстремума в одной из вершин этого многогранника.

Данная теорема получила название теоремы об экстремуме линейной формы.

В соответствии с теоремой Вейерштрасса оптимальное решение единственно и является глобальным экстремумом.

Существует общий аналитический подход к реализации модели ЛП – симплекс-метод. При решении задач линейного программирования достаточно часто решения нет. Это происходит по следующим причинам.

Первую причину проиллюстрируем примером

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

Вторая причина комментируется следующим примером:

В данном случае, область допустимых решений не ограничена сверху. Область допустимых решений не ограничена.

Следуя традициям линейного программирования, дадим задаче ЛП экономическую интерпретацию. Пусть в нашем распоряжении имеется m типов ресурсов. Количество ресурса типа j равно . Эти ресурсы необходимы для производства n типов товаров. Обозначим количество этих товаров символами соответственно. Единица товара типа i стоит . Производство товаров типа i должно быть ограничено величинами соответственно. На производство единицы товара типа i расходуется ресурса типа j . Необходимо определить такой план производства товаров (), чтобы их суммарная стоимость была минимальной.

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

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

Алгебраические методы решения задачи ЛП начинаются с приведения ее к стандартной (канонической) форме :

,

,

i =1,..,n ; j =1,..,m .

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

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

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

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

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

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

,

.

Необходимо привести ее к стандартной форме. Заметим, что первое неравенство исходной задачи имеет знак , следовательно, в него необходимо ввести остаточную переменную . В результате получим .

Второе неравенство имеет знак и для преобразования к стандартной форме требует введения избыточной переменной , выполнив эту операцию, получим .

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

.

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

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .