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

Основой для решения экономических задач являются математические модели.

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

• выбор переменных задачи
• составление системы ограничений
• выбор целевой функции

Переменными задачи называются величины Х1, Х2, Хn, которые полностью характеризуют экономический процесс. Обычно их записывают в виде вектора: X=(X 1 , X 2 ,...,X n).

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

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

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

Данная запись означает следующее: найти экстремум целевой функции (1) и соответствующие ему переменные X=(X 1 , X 2 ,...,X n) при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3).

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X 1 , X 2 ,...,X n), удовлетворяющий системе ограничений и условиям неотрицательности.

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

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

Пример составления математической модели

Задача использования ресурсов (сырья)

Условие: Для изготовления n видов продукции используется m видов ресурсов. Составить математическую модель.

Известны:

• b i (i = 1,2,3,...,m) — запасы каждого i-го вида ресурса;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) — затраты каждого i-го вида ресурса на производство единицы объема j-го вида продукции;
• c j (j = 1,2,3,...,n) — прибыль от реализации единицы объема j-го вида продукции.

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

Решение:

Введем вектор переменных X=(X 1 , X 2 ,...,X n), где x j (j = 1,2,...,n) — объем производства j-го вида продукции.

Затраты i-го вида ресурса на изготовление данного объема x j продукции равны a ij x j , поэтому ограничение на использование ресурсов на производство всех видов продукции имеет вид:
Прибыль от реализации j-го вида продукции равна c j x j , поэтому целевая функция равна:

Ответ - Математическая модель имеет вид:

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

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

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

Она может быть представлена в координатной, векторной и матричной записи.

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

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

• А — матрица коэффициентов системы уравнений
• Х — матрица-столбец переменных задачи
• Ао — матрица-столбец правых частей системы ограничений

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

Приведение общей задачи линейного программирования к канонической форме

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

Возьмем линейное неравенство a 1 x 1 +a 2 x 2 +...+a n x n ≤b и прибавим к его левой части некоторую величину x n+1 , такую, что неравенство превратилось в равенство a 1 x 1 +a 2 x 2 +...+a n x n +x n+1 =b. При этом данная величина x n+1 является неотрицательной.

Рассмотрим все на примере.

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

Решение:
Перейдем к задаче на отыскивание максимума целевой функции.
Для этого изменим знаки коэффициентов целевой функции.
Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x 4 x 5 (на математической модели эта операция отмечена буквой Д).
Переменная х 4 вводится в левую часть второго неравенства со знаком "+", так как неравенство имеет вид "≤".
Переменная x 5 вводится в левую часть третьего неравенства со знаком "-", так как неравенство имеет вид "≥".
В целевую функцию переменные x 4 x 5 вводятся с коэффициентом. равным нулю.
Записываем задачу в каноническом виде.

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

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

Для составления математической модели необходимо:

1. выбрать переменные задачи;

2. составить систему ограничений;

3. задать целевую функцию.

Переменными задачи называются величины х 1 , х 2 ,…, х n , которые полностью характеризуют экономический процесс. Их обычно записывают в виде вектора Х = (х 1 , х 2 ,…, х n).

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

Целевой функцией называется функция F(X) = f(х 1 , х 2 ,…, х n) переменных задачи, которая характеризует качество выполнения задачи и экстремум которой требуется найти.

Общая задача математического программирования формулируется следующим образом: найти переменные задачи х 1 , х 2 ,…, х n , которые обеспечивают экстремум целевой функции

F(X) = f(х 1 , х 2 ,…, х n) ® max (min) (2)

и удовлетворяют системе ограничений (1).

Если целевая функция (2) и система ограничений (1) линейны, то задача математического программирования называется задачей линейного программирования (ЗЛП) .

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

2. Примеры составления математических моделей экономических задач

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

1.Задача об оптимальном производственном плане

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

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

Решение.

Обозначим х 1 , х 2 – число единиц продукции соответственно Т 1 и Т 2 , запланированных к производству. Для их изготовления потребуется (х 1 + х 2) единиц ресурса S 1 , (х 1 + 4х 2) единиц ресурса S 2 , (х 1) единиц ресурса S 3 . Потребление ресурсов S 1 , S 2 , S 3 не должно превышать их запасов, соответственно 8, 20 и 5 единиц.

Тогда экономико-математическую модель задачи можно сформулировать так:

Найти план выпуска продукции Х = (х 1 , х 2), удовлетворяющий системе ограничений:

и условию ,

при котором функция принимает максимальное значение.

Задачу можно легко обобщить на случай выпуска n типов продукции с использованием m видов ресурсов.

2.Задача об оптимальном рационе

Имеется два вида корма К 1 и К 2 , содержащие питательные вещества S 1 , S 2 и S 3 . Содержание числа единиц питательных веществ в 1кг каждого вида корма, необходимый минимум питательных веществ, а также стоимость 1кг корма приведены в таблице:

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

Решение.

Обозначим х 1 , х 2 – количество кормов К 1 и К 2 , входящих в дневной рацион. Тогда этот рацион будет включать (3х 1 + х 2) единиц питательного вещества S 1 , (х 1 +2х 2) единиц вещества S 2 , (х 1 +6х 2) единиц питательно вещества S 3 . Так как содержание питательных веществ S 1 , S 2 и S 3 в рационе должно быть соответственно 9, 8 и 12 единиц, то экономико-математическую модель задачи можно сформулировать так:

Составить дневной рацион Х = (х 1 , х 2), удовлетворяющий системе ограничений:

и условию ,

при котором функция принимает минимальное значение.

Формы записи ЗЛП

В ЗЛП требуется найти экстремум линейной целевой функции:

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

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

где а ij , b i , c j ( , ) – заданные постоянные величины.

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

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

Чтобы перейти от одной формы записи ЗЛП к другой надо уметь переходить от ограничений-неравенств к ограничениям-равенствам и наоборот.

Ограничение – неравенство (£) можно преобразовать к ограничению-равенству добавлением к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство (³) – в ограничение равенство вычитанием из его левой части дополнительной неотрицательной переменной. Число вводимых дополнительных неотрицательных переменных равно числу преобразуемых ограничений-неравенств.

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

Пример 1 . Записать в канонической форме ЗЛП:

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

Решение.

Целевая функция остается без изменений:

Система неравенств преобразуется в систему равенств:

При решении ЗЛП графическим методом требуется переход от канонической формы к стандартной форме.

Для приведения ЗЛП к стандартной форме используется метод Жордана – Гаусса решения СЛАУ. В отличие от метода Гаусса, в котором расширенная матрица системы приводится к ступенчатому виду, в методе Жордана – Гаусса в составе расширенной матрицы формируется единичная матрица. Поэтому обратный ход здесь не требуется.

Для преобразования исходной канонической ЗЛП в эквивалентную стандартную ЗЛП:

а) в расширенной матрице системы ограничений выбирается отличный от нуля элемент a qp . Этот элемент называется разрешающим , а q - я строка и р-й столбец называются разрешающей строкой и разрешающим столбцом .

б) разрешающая строка переписывается без изменения, а все элементы разрешающего столбца, кроме разрешающего, заменяются нулями. Остальные элементы расширенной матрицы определяются с помощью «правила прямоугольника»:

Рассмотрим четыре элемента расширенной матрицы: элемент а ij , подлежащий преобразованию, разрешающий элемент a qp и элементы а i р и a qj . Для нахождения элемента а ij следует из элемента а ij вычесть произведение элементов а i р и a qj , расположенных в противоположных вершинах прямоугольника, деленное на разрешающий элемент a qp:

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

Пример 2 . Привести к стандартному виду:

Решение.

Методом Жордана – Гаусса приведем систему уравнений-ограничений ЗЛП к равносильной системе неравенств. Выберем в качестве разрешающего элемента третий элемент первой строки:

Число -9, полученное в последнем столбце последней строки, необходимо записать в целевую функцию с противоположным знаком. В результате преобразований ЗЛП принимает вид:

Т.к. переменные х 2 и х 3 неотрицательные, то отбросив их, можно записать ЗЛП в симметричном виде:

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

Свойства ЗЛП

1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

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

Согласно этому определению многоугольник на рис.1а является выпуклым множеством, а многоугольник на рис.1б таковым не является, т.к. отрезок MN между двумя его точками M и N не полностью принадлежит этому многоугольнику.

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

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

Точка Х называется выпуклой линейной комбинацией точек Х 1 , Х 2 ,…, Х n , если выполняются условия:

Х = α 1 Х 1 +α 2 Х 2 +…+ α n Х n ,

α j ≥ 0, Σα j = 1.

Очевидно, что в частном случае при n = 2 выпуклой линейной комбинацией двух точек является соединяющий их отрезок.

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 очень большими значениями.

Лекция 2

В канонической форме

допустимым решением ЗЛП (допустимым планом ).

оптимальным решением ЗЛП.

Необходимость

Пример .

Запишем задачу в канонической форме

Особые ситуации графического решения ЗЛП

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

1. задача имеет бесконечное множество оптимальных решений – экстремум функции достигается на отрезке (альтернативный оптимум) – рисунок 2;

2. задача не разрешима из-за неограниченности ОДР, или – рисунок 3;

3. ОДР - единственная точка А, тогда ;

4. задача не разрешима , если ОДР есть пустая область.

А

Рисунок 2 Рисунок 3

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

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

Пример . Решить графически задачу линейного программирования (альтернативный оптимум ):

Вопросы для самоконтроля

1. Запишите задачу линейного программирования в общей форме.

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

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

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

5. Какое из решений и является «лучшим» для задачи минимизации функции , если ?

6. Какое из решений и является «лучшим» для задачи максимизации функции , если ?

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

8. Как построить полуплоскость, заданную линейным неравенством с двумя переменными ?

9. Что называется решением системы линейных неравенств с двумя переменными? Постройте на плоскости область допустимых решений такой системы линейных неравенств, которая:

1) имеет единственное решение;

2) имеет бесконечное множество решений;

3) не имеет ни одного решения.

10. Запишите для линейной функции вектор градиент, назовите вид линий уровня. Как расположены относительно друг друга градиент и линии уровня?

11. Сформулируйте алгоритм графического метода решения стандартной ЗЛП с двумя переменными.

12. Как найти координаты решения и значения , ?

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

1) достигается в единственной точке, а - на отрезке ОДР;

2) достигается в единственной точке ОДР, а .

14. Дайте геометрическую иллюстрацию ЗЛП, если она:

1) имеет единственные оптимальные решения для и ;

2) имеет множество оптимальных решений для .

Лекция 2

графический метод нахождения оптимального решения

1. Формы линейных математических моделей и их преобразование

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

3. Особые ситуации графического решения ЗЛП

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

Формы линейных математических моделей и их преобразование

Математическая модель задачи линейного программирования (ЗЛП) может быть записана в одной из трех форм.

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

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

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

Решение системы ограничений, удовлетворяющее условиям неотрицательности переменных, называют допустимым решением ЗЛП (допустимым планом ).

Множество допустимых решений называют областью допустимых решений ЗЛП.

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

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

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

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

Пример .

Запишем задачу в канонической форме , вводя в левую часть первого неравенства системы ограничений дополнительную (балансовую) переменную со знаком «+», а в левую часть второго неравенства дополнительную переменную со знаком «минус».

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

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