Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных x1, x2, …, xn, удовлетворяющие m условиям - равенствам
и обращающие в максимум линейную функцию этих переменных
Для простоты предположим, что все условия (1) линейно независимы (r=m), и будем вести рассуждения в этом предположении.
Назовём допустимым решением ОЗЛП всякую совокупность неотрицательных значений x1, x2, …, xn, удовлетворяющую условиям (1).Оптимальным назовём то из допустимых решений, которое обращает в максимум функцию (2). Требуется найти оптимальное решение.
Всегда ли эта задача имеет решение? Нет, не всегда.
ЗЛП неразрешима (не имеет оптимального решения):
Из-за несовместности системы ограничений. Т.е. система не имеет ни одного решения, как показано на рисунке 1.
Рисунок 1 - Несовместность системы ограничений
Из-за неограниченности целевой функции на множестве решений. Другими словами при решении ЗЛП на max значение целевой функции стремится к бесконечности, а в случае ЗЛП на min - к минус бесконечности, как показано на рисунке 2.
Рисунок 2 - Неограниченность целевой функции на множестве решений
ЗЛП разрешима:
Множество решений состоит из одной точки. Она же и является оптимальной, как показано на рисунке 3.
Рисунок 3 - Множество решений состоит из одной точки
Единственное оптимальное решение ЗЛП. Прямая, соответствующая целевой функции в предельном положений пересекается с множеством решений в одной точке, как показано на рисунке 4.
Рисунок 4 - Единственное оптимальное решение
Оптимальное решение ЗЛП не единственно. Вектор N перпендикулярен к одной из сторон множества решений. В этом случае оптимальной является любая точка на отрезке АВ, как показано на рисунке 5.
Рисунок 5 - Оптимальное решение не единственно
Решение задач линейного программирования симплекс-методом
Симплекс-метод - алгоритм решения задачи ЛП, реализующий перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции С. Симплекс-метод является основным в линейном программировании.
Использование этого метода в дипломном проекте для решения задачи ЛП обусловлено следующими факторами:
Метод является универсальным, применимым к любой задаче линейного программирования в канонической форме;
Алгоритмический характер метода позволяет успешно программировать и реализовать его с помощью технических средств.
Экстремум целевой функции всегда достигается в угловых точках области допустимых решений. Прежде всего, находится какое-либо допустимое начальное (опорное) решение, т.е. какая-либо угловая точка области допустимых решений. Процедура метода позволяет ответить на вопрос, является ли это решение оптимальным. Если «да», то задача решена. Если «нет», то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается. Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции .
Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.
Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен, то возможно выбрать неизвестных, которые выражают через остальные неизвестные. Для определенности обычно полагают, что выбраны первые, идущие подряд, неизвестные. Эти неизвестные (переменные) называются базисными, остальные свободными. Количество базисных переменных всегда равно количеству ограничений.
Присваивая определенные значения свободным переменным, и вычисляя значения базисных (выраженных через свободные), получают различные решения системы ограничений. Особый интерес представляют решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Оно соответствует всем ограничениям.
Имея систему ограничений, находят любое базисное решение этой системы. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому допустимому базисному решению.
Симплексный метод гарантирует, что при этом новом решении линейная форма если и не достигнет оптимума, то приблизится к нему. С новым допустимым базисным решением поступают так же, пока не находят решение, которое является оптимальным.
Если первое найденное базисное решение окажется недопустимым, то с помощью симплексного метода осуществляется переход к другим базисным решениям, пока на каком-то шаге решения базисное решение окажется допустимым, либо можно сделать вывод о противоречивости системы ограничений.
Таким образом, применение симплексного метода распадается на два этапа:
Нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности;
Нахождение оптимального решения в случае совместности системы ограничений.
Алгоритм перехода к следующему допустимому решению следующий:
В строке коэффициентов целевой функции выбирается наименьшее отрицательное число при отыскании максимума. Порядковый номер коэффициента - . Если такового нет, то исходное базисное решение является оптимальным;
Среди элементов матрицы с номером столбца (этот столбец называется ведущим, или разрешающим) выбираются положительные элементы. Если таковых нет, то целевая функция неограничена на области допустимых значений переменных и задача решений не имеет;
Среди выбранных элементов ведущего столбца матрицы выбирается тот, для которого величина отношения соответствующего свободного члена к этому элементу минимальна. Этот элемент называется ведущим, а строка, в которой он находится - ведущей;
Базисная переменная, отвечающая строке ведущего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу ведущего элемента, вводится в число базисных. Строится новое решение, содержащее новые номера базисных переменных.
Условие оптимальности плана при решении задачи на максимум: среди коэффициентов целевой функции нет отрицательных элементов .
Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП
Линейное программирование - направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием оптимальности. Несколько слов о самом термине линейное программирование. Он требует правильного понимания. В данном случае программирование - это, конечно, не составление программ для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий. К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов. Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:
- - задача об оптимальном использовании ресурсов при производственном планировании;
- - задача о смесях (планирование состава продукции);
- - задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");
- - транспортные задачи (анализ размещения предприятия, перемещение грузов). Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:
- - математические модели большого числа экономических задач линейны относительно искомых переменных;
- - данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;
- - многие задачи линейного программирования, будучи решенными, нашли широкое применение;
- - некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования. Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных. В общем виде модель записывается следующим образом:
- - целевая функция:
C1x1 + c2x2 + ... + cnxn > max(min);- ограничения:
a11x1 + a12x2 + ... + a1nxn {? = ?} b1,
a21x1 + a22x2 + ... + a2nxn {? = ?} b2
am1x1 + am2x2 + ... + amnxn {? = ?} bm;
Требование неотрицательности:
При этом aij, bi, cj () - заданные постоянные величины. Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3). Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми. Вектор, удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программирования. План, при котором функция (2.1) достигает своего максимального (минимального) значения, называется оптимальным.
Далее приведем примеры некоторых типовых задач, решаемых при помощи методов линейного программирования. Такие задачи имеют реальное экономическое содержание. Сейчас лишь сформулируем их в терминах ЗЛП, а методы решения подобных задач рассмотрим ниже.
1. Задача об оптимальном использовании ресурсов при производственном планировании. Общий смысл задач этого класса сводится к следующему. Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц. Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида (). Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj. В планируемом периоде значения величин aij, bi и cj остаются постоянными. Требуется составить такой план выпуска продукции, при реализации которого прибыль преприятия была бы наибольшей. Далее приведем простой пример задачи такого класса.
Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В - 72 н-часа и участка С - 10 н-часов. Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?
Условия задач указанного класса часто представляют в табличной форме (см. таблицу 2.1).
По данному условию сформулируем задачу линейного программирования. Обозначим: x1 - количество выпускаемых ежедневно хоккейных клюшек, x2 - количество выпускаемых ежедневно шахматных наборов. Формулировка ЗЛП:
4x1 + 6x2 ? 120,
Подчеркнем, что каждое неравенство в системе функциональных ограничений соответствует в данном случае тому или иному производственному участку, а именно: первое - участку А, второе - участку В, третье - участку С.
Система переменных величин в задаче по оптимизации структуры посевных площадей с учётом севооборотов
Общая задача линейного программирования (ОЗЛП) формулируется следующим образом – найти переменные задачи x 1 , x 2 , ..., x n , которые обеспечивают экстремум целевой функции
Допустимым решением (планом) задачи линейного программирования (ЗЛП) называется любой n -мерный вектор X =(x 1 , x 2 , ..., x n), удовлетворяющий системе ограничений равенств и неравенств. Множество допустимых решений задачи образует область допустимых решений D .
Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение, при котором целевая функция Z (X ) достигает экстремума.
Каноническая задача линейного программирования (КЗЛП) имеет вид
(1.2)
Она отличается от ОЗЛП тем, что её система ограничений является системой только уравнений и все переменные неотрицательные.
Приведение ОЗЛП к каноническому виду ЗЛП:
Чтобы заменить исходную задачу минимизации на задачу максимизации (или наоборот задачу максимизации на задачу минимизации) достаточно целевую функцию умножить на «-1» и искать максимум (минимум) полученной функции;
Если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных x n +1 ≥ 0 они преобразуются в равенства:
неравенство a i 1 x 1 +…+a in x n ≥ b i заменяется на равенство a i 1 x 1 +…+a in x n + x n +1 = b i ,
неравенство a i 1 x 1 +…+a in x n ≤ b i заменяется на равенство a i 1 x 1 +…+a in x n + x n +1 = b i ;
Если некоторая переменная x k не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательны-ми переменными: x k = x " k – x ” k , где x " k ≥ 0. x ” k ≥ 0.
Графический метод решения ЗЛП с двумя неизвестными
ЗЛП с двумя неизвестными имеет вид:
Метод основан на возможности графического изображения области допустимых решений и нахождении среди них оптимального решения.
Область допустимых решений (ОДР) задачи является выпуклым многоугольником и строится как пересечение (общая часть) областей решений каждого из неравенств ограничений задачи.
Областью решения неравенства a i 1 x 1 +a i 2 x 2 ≤ b i является одна из двух полуплоскостей, на которые прямая a i 1 x 1 +a i 2 x 2 = b i , соответствующая этому неравенству, делит координатную плоскость. Чтобы определить, какая из двух полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на разделяющей прямой подставить в неравенство:
Если неравенство справедливо, то областью решений является полуплоскость, содержащая эту точку;
Если неравенство не справедливо, то областью решений является полуплоскость, не содержащая эту точку.
Для нахождения среди допустимых решений оптимального используются линии уровня.
Линией уровня называется прямая с 1 x 1 +с 2 x 2 = l , где l = const, на которой целевая функция задачи принимает постоянное значение. Все линии уровня параллельны между собой.
Градиент целевой функции grad Z (X ) задает вектор нормали C = (c 1 , c 2) линий уровня. Целевая функция на линиях уровня возрастает, если линии уровня перемещать в направлении их нормали, и убывает – в противоположном направлении.
Опорной прямой называется линия уровня, которая имеет хотя бы одну общую точку с ОДР и по отношению к которой ОДР находится в одной из полуплоскостей. ОДР задачи имеет не более двух опорных прямых.
Оптимальное решение ЗЛП лежит на опорной прямой в угловой точке многоугольника ОДР. ЗЛП имеет единственное решение, если опорная прямая проходит через одну угловую точку ОДР, бесконечное множество решений, если опорная прямая проходит через ребро многоугольника ОДР. ЗЛП не имеет решения, если ОДР является пустым множеством (когда система ограничений несовместна) и если ОДР неограниченна в направлении экстремума (целевая функция неограниченна).
Алгоритм графического метода решения ЗЛП с двумя неизвестными:
Построить ОДР.
Построить вектор нормали C = (c 1 , c 2) и линию уровня с 1 x 1 +с 2 x 2 = 0, проходящую через начало координат и перпендикулярную вектору С .
Передвигать линию уровня до опорной прямой в направлении вектора С в задаче на max, или в противоположном направлении – в задаче на min.
Если при перемещении линии уровня в направлении экстремума ОДР уходит в бесконечность, то ЗЛП не имеет решения ввиду неограниченности целевой функции.
Если ЗЛП имеет оптимальное решение, то для его нахождения решить совместно уравнения прямых, ограничивающих ОДР и имеющих общие точки с опорной прямой. Если экстремум достигается в двух угловых точках, то ЗЛП имеет бесконечное множество решений, принадлежащих ребру ОДР, ограниченному этими угловыми точками. В данном случае вычисляются координаты обеих угловых точек.
Вычислить значение целевой функции в точке экстремума.
Симплекс-метод решения ЗЛП
Симплекс-метод основывается на следующих положениях:
ОДР задачи линейного программирования является выпуклым множеством с конечным числом угловых точек;
Оптимальным решением ЗЛП является одна из угловых точек ОДР. Угловые точки ОДР алгебраически представляют некоторые базисные (опорные) решения системы ограничений ЗЛП.
Базисным (опорным) решением ЗЛП называется такое допустимое решение X 0 =( x 10 , x 20 , ..., x m 0 , 0,…0), для которого векторы условий (столбцы коэффициентов при неизвестных в системе ограничений) линейно независимы.
Ненулевые координаты x 10 , x 20 , ..., x m 0 решения X 0 называются базисными переменными, оставшиеся координаты решения X 0 - свободными переменными. Число отличных от нуля координат опорного решения не может быть больше ранга r системы ограничений ЗЛП (числа линейно независимых уравнений в системе ограничений ЗЛП). Далее считаем, что система ограничений ЗЛП состоит из линейно независимых уравнений, т.е. r = m .
Смысл симплекс-метода заключается в целенаправленном переходе от одного опорного решения ЗЛП к другому (т.е. от одной угловой точки ОДР к другой) в направлении экстремума и состоит в последовательности этапов:
Найти начальное опорное решение;
Осуществить переход от одного опорного решения к другому;
Определить критерий достижения оптимального решения или сделать заключение об отсутствии решения.
Алгоритм выполнения Симплекс-метода ЗЛП
Алгоритм симплекс-метода осуществляет переход от одного опорного решения ЗЛП к другому в направлении экстремума целевой функции.
Пусть ЗЛП задана в каноническом виде (1.2) и выполнено условие
b i ≥ 0, i =1,2,…,m , (1.3)
соотношение (1.3) всегда можно выполнить, домножив соответствующее уравнение на «-1» в случае отрицательности b i . Также считаем, что система уравнений в ограничениях задачи (1.2) линейно независима и имеет ранг r = m . При этом вектор опорного решения имеет m ненулевых координат.
Пусть исходная задача (1.2), (1.3) приведена к виду, где базисные переменные x 1 , x 2 , ..., x m выражены через свободные переменные x m + 1 , x m + 2 , ..., x n
(1.4)
На основе этих соотношений построим таблицу 1
Таблица 1.
Таблица 1 называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменениями содержания этой таблицы.
Алгоритм с имплекс-метода :
1. В последней строке Z симплекс-таблицы в задаче на min находят наименьший положительный элемент (в задаче на max - наименьший отрицательный элемент), не считая свободного члена. Столбец, ответствующий этому элементу, называется разрешающим.
2. Вычисляют отношение свободных членов к положительным элементам разрешающего столбца (симплекс-отношение). Находят наименьшее из этих симплекс - отношений, оно соответствует разрешающей строке.
3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.
4. Если имеется несколько одинаковых по величине симплекс - отношений, то выбирают любое из них. То же самое относится к положительным элементам последней строки симлекс - таблицы.
5. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Симплекс - таблица преобразуется следующим образом (таблица 2):
Таблица 2
6. Элемент таблицы 2, соответствующий разрешающему элементу таблицы 1, равен обратной величине разрешающего элемента.
7. Элементы строки таблицы 2, соответствующие элементам разрешающей строки таблицы 1, получаются путем деления соответствующих элементов таблицы 1 на разрешающий элемент.
8. Элементы столбца таблицы 2, соответствующие элементам разрешающего столбца таблицы 1, получаются путем деления соответствующих элементов таблицы 1 на разрешающий элемент и берутся с противоположным знаком.
9. Остальные элементы вычисляются по правилу прямоугольника : мысленно вычерчиваем прямоугольник в таблице 1, одна вершина которого совпадает с разрешающим элементом (Рэ), а другая – с элементом, который мы ищем; обозначим элемент в новой таблице 2 через (Нэ), а элемент, стоящий на этом же месте в старой таблице 1 – через (Сэ). Остальные две вершины А и В дополняют фигуру до прямоугольника. Тогда искомый элемент Нэ из таблицы 2 равен Нэ = Сэ – А*В/Рэ.
10. Критерий оптимальности. Как только получится таблица, у которой в последней строке в задаче на min все элементы отрицательны (в задаче на max все элементы положительны), считается, что экстремум найден. Оптимальное значение целевой функции равно свободному члену в строке Z, а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные полагаются равными нулю.
11.Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается).
Метод искусственного базиса решения ЗЛП
Алгоритм симплекс-метода применим, если выделено какое-либо опорное решение ЗЛП, т. е, исходная ЗЛП (1.2) приведена к виду (1.4). Метод искусственного базиса предлагает процедуру построения такого опорного решения.
Метод искусственного базисаоснован на введении искусственных базисных переменных y 1 , y 2 ,…, y m , с помощью которых система ограничений ЗЛП (2.2)
(1.5)
может быть преобразована к виду
(1.6)
Системы (1.5) и (1.6) будут эквивалентны в том случае, если все y i будут равны нулю. Как и раньше мы считаем, что все b i ≥ 0. Для того чтобы у i были равны 0, мы должны преобразовать задачу таким образом, чтобы все искусственные базисные переменные y i перешли в свободные переменные. Такой переход можно сделать алгоритмом симплекс метода относительно дополнительной целевой функции
F (y ) = y 1 + y 2 + ... + y m = d 0 – (d 1 x 1 + d 2 x 2 +…+d n x n). (2.7)
Исходная симплекс таблица для данного метода имеет вид
Сначала симплекс таблица преобразуется относительно целевой функции F (y ) до получения опорного решения. Опорное решение найдено, когда выполнен следующий критерий: F (y ) = 0 и все искусственные переменные у i переведены в свободные переменные. Затем из симплекс таблицы вычеркивается строка для F (y ) и столбцы для у i и решают задачу для исходной целевой функции Z (x ) до получения оптимального решения.
Задача линейного программирования (ЗЛП) − это задача нахождения наибольшего (или наименьшего) значения линейной функции на выпуклом многогранном множестве.
Симплекс метод − это метод решения задачи линейного программирования. Суть метода заключается в нахождении начального допустимого плана, и в последующем улучшении плана до достижения максимального (или минимального) значения целевой функции в данном выпуклом многогранном множестве или выяснения неразрешимости задачи.
Рассмотрим следующую задачу линейного программирования в канонической форме:
| (1) |
| (2) |
| (3) |
Метод искусственного базиса
Как было паказано выше, для задачи, записанной в канонической форме, если среди векторов столбцов матрицы A есть m единичных и линейно независимых , можно непосредственно указать опорный план. Однако для многих задач линейного программирования, записанных в канонической форме и имеющих опорные планы, среди векторов столбцов матрицы A не всегда есть m единичных и линейно независимых. Рассмотрим такую задачу:
Пусть требуется найти максимум функции
при условиях
где первы n
элементы нули. Переменные 
называются искусственными
. Векторы столбцы
  | (28) |
образуют так называемый искусственный базис m -мерного векторного пространства.
Так как расширенная задача имеет опорный план, то ее решение можно найти симплекс методом.
Теорема 4.
Если в оптимальном плане 
расширенной задачи (24)−(26) значения искусственных переменных 
, то 
является оптимальным планом задачи (21)−(23).
Таким образом, если в найденном оптимальном плане расширенной задачи, значения искусственных переменных равны нулю, то получен оптимальный план исходной задачи. Остановимся более подробно на нахождении решения расширенной задачи.
Значение целевой функции при опорном плане (27):
Замечаем, что F(X) и состоят из двух независимых частей, одна из которых зависим от M , а другая − нет.
После вычисления F(X) и их значения, а также исходные данные расширенной задачи заносят в симплекс таблицу, как было показано выше. Разность заключается лишь в том, что данная таблица содержит на одну строку больше, чем обычная симплекс таблица. При этом в (m +1)-ю строку помещают коэффициенты, не содержащие M , а в (m +2)-ю строку − коэффициенты при M .
При переходе от одного опорного плана к другому, в базис вводят вектор, соответствующий наибольшему по абсолютной величине отрицательному числу (m +2) строки. Искусственный вектор, исключенный из базиса не имеет смысла вновь ввести в базис. При переходе к другому опорному плану, может случится так, что ни один из искусственных векторов из базиса не будет исключен. Пересчет симплекс таблицы при переходе от одного опорного плана к другому производят по обычным правилам симплекс метода (смотри выше).
Итерационный процесс ведут по m
+2 строке до тех пор, пока элементы m
+2 строки, соответствующие переменным 
не станут неотрицательными. При этом, если искусственные переменные исключены из базиса, то найденный план расширенной задачи отвечает некоторому опорному плану исходной задачи.
m +2 строки, столбца x 0 отрицателен, то исходная задача не имеет решения.
Если же не все искусственные переменные исключены из базиса и элемент m +2 строки, столбца x 0 равен нулю, то опорный план исходной задачи является вырожденным и базис содержит минимум один из векторов искусственного базиса.
Если исходная задача содержит несколько единичных векторов, то их следует включить в искусственный базис.
Если в ходе итераций m +2 строка больше не содержит отрицательных элементов, то итерационный процесс продолжают с m +1 строкой, до тех пор, пока не найден оптимальный план расширенной задачи или не выявлен неразрешимость задачи.
Таким образом, процесс нахождения решения задачи линейного программирования (21)−(23) методом искусственного базиса включает следующие основные этапы:
- Составляют расширенную задачу (24)−(26).
- Находят опорный план расширенной задачи.
- Используя симплекс метод исключают искусственные векторы из базиса. В результате находят опорный план исходной задачи или фиксируют ее неразрешимость.
- Используя найденный опорный план ЗЛП (21)−(23), или находят оптимальный план исходной задачи, или устанавливают ее неразрешимость.
Для решения задач линейного программирования онлайн, пользуйтесь калькулятором
Составляющие математической модели
Основой для решения экономических задач являются математические модели.
Составление математической модели включает:Математической моделью задачи называется совокупность математических соотношений, описывающих суть задачи.
- выбор переменных задачи
- составление системы ограничений
- выбор целевой функции
Переменными задачи называются величины Х1, Х2, Хn, которые полностью характеризуют экономический процесс. Обычно их записывают в виде вектора: X=(X1, X2,...,Xn).
Системой ограничений задачи называют совокупность уравнений и неравенств, описывающих ограниченность ресурсов в рассматриваемой задаче.
Целевой функцией задачи называют функцию переменных задачи, которая характеризует качество выполнения задачи и экстремум которой требуется найти.
В общем случае задача линейного программирования может быть записана в таком виде:
Данная запись означает следующее: найти экстремум целевой функции (1) и соответствующие ему переменные X=(X1, X2,...,Xn) при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3).
Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X1, X2,...,Xn), удовлетворяющий системе ограничений и условиям неотрицательности.
Множество допустимых решений (планов) задачи образует область допустимых решений (ОДР).
Пример составления математической моделиЗадача использования ресурсов (сырья)Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение (план) задачи, при котором целевая функция достигает экстремума.
Условие: Для изготовления n видов продукции используется m видов ресурсов. Составить математическую модель.
Известны:
- bi (i = 1,2,3,...,m) - запасы каждого i-го вида ресурса;
- aij (i = 1,2,3,...,m; j=1,2,3,...,n) - затраты каждого i-го вида ресурса на производство единицы объема j-го вида продукции;
- cj (j = 1,2,3,...,n) - прибыль от реализации единицы объема j-го вида продукции.
Требуется составить план производства продукции, который обеспечивает максимум прибыли при заданных ограничениях на ресурсы (сырье).
Решение:
Введем вектор переменных X=(X1, X2,...,Xn), где xj (j = 1,2,...,n) - объем производства j-го вида продукции.
Затраты i-го вида ресурса на изготовление данного объема xj продукции равны aijxj, поэтому ограничение на использование ресурсов на производство всех видов продукции имеет вид:
Прибыль от реализации j-го вида продукции равна cjxj, поэтому целевая функция равна:
Ответ - Математическая модель имеет вид:
Каноническая форма задачи линейного программирования
В общем случае задача линейного программирования записывается так, что ограничениями являются как уравнения, так и неравенства, а переменные могут быть как неотрицательными, так и произвольно изменяющимися.
В том случае, когда все ограничения являются уравнениями и все переменные удовлетворяют условию неотрицательности, задачу линейного программирования называют канонической.
Она может быть представлена в координатной, векторной и матричной записи.
Каноническая задача линейного программирования в координатной записи имеет вид:
Каноническая задача линейного программирования в матричной записи имеет вид:
- А - матрица коэффициентов системы уравнений
- Х - матрица-столбец переменных задачи
- Ао - матрица-столбец правых частей системы ограничений
Нередко используются задачи линейного программирования, называемые симметричными, которые в матричной записи имеют вид:
Приведение общей задачи линейного программирования к канонической форме
В большинстве методов решения задач линейного программирования предполагается, что система ограничений состоит из уравнений и естественных условий неотрицательности переменных. Однако при составлении моделей экономических задач ограничения в основном формируются в виде системы неравенств, поэтому необходимо уметь переходить от системы неравенств к системе уравнений.
Это может быть сделано следующим образом:Возьмем линейное неравенство a1x1+a2x2+...+anxn≤b и прибавим к его левой части некоторую величину xn+1, такую, что неравенство превратилось в равенство a1x1+a2x2+...+anxn+xn+1=b. При этом данная величина xn+1 является неотрицательной.
Рассмотрим все на примере.
Пример 26.1Привести к каноническому виду задачу линейного программирования:
Решение:
Перейдем к задаче на отыскивание максимума целевой функции.
Для этого изменим знаки коэффициентов целевой функции.
Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x4 x5 (на математической модели эта операция отмечена буквой Д).
Переменная х4 вводится в левую часть второго неравенства со знаком "+", так как неравенство имеет вид "≤".
Переменная x5 вводится в левую часть третьего неравенства со знаком "-", так как неравенство имеет вид "≥".
В целевую функцию переменные x4 x5 вводятся с коэффициентом. равным нулю.
Записываем задачу в каноническом виде:
