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

сОДЕРЖАНИЕ

Введение…………………………………………………………………………3

1.Общая задача линейного  программирования (ЛП)…………………………5

1.1. Постановка  задачи…………………………………………………………5

1.2. Графический метод решения задач ЛП…………………………………...8

1.3. Симплекс-метод решения задач ЛП…………………………………...…11

2. Примеры решения задач различными методами ЛП…………….……......17

Заключение ……………………………………………………………………..29

Список литературы……………………………………………………………..30

 

 

Введение

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

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

Графический метод  основан на геометрической интерпретации  задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трех изобразить  графически вообще невозможно. Поэтому для решения, в том числе этой проблемы, в конце 40-х годов американским математиком Дж. Данцигом был разработан эффективный метод решения данного класса задач – симплекс-метод. К задачам, решаемых этим методом в рамках математического программирования относятся такие типичные экономические задачи как «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», « Задача о выборе производственной программы», «Транспортная задача», «Задача размещения», «Модель Неймана расширяющейся экономики» и другие. Решение таких задач дает большие выгоды как народному хозяйству в целом, так и отдельным его отраслям.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

1.1. Постановка задачи

Задача линейного программирования (ЛП) ассоциируется с задачей распределительного типа, в которой требуется распределить ограниченные ресурсы по нескольким видам деятельности. Интерпретация задачи ЛП в этом случае состоит в следующем. Моделируемая ЭИС характеризуется наличием нескольких видов деятельности j (j = 1, …, n), для осуществления которых требуются имеющиеся в ограниченном количестве различные ресурсы b_i, (i = 1, …, m). Интенсивность расходования каждого из ресурсов на каждый из видов деятельности ЭИС известна и равна a_ij. Результативность или ценность каждого j-го вида деятельности ЭИС характеризуется величиной c_j. Цель построения модели заключается в определении уровней каждого вида деятельности ЭИС x_j, при которых оптимизируется общий результат деятельности ЭИС в целом при выполнении ограничений, накладываемых на использование ресурсов, т. е. c_j x_j ≤ b_i, i = 1, …, m. Структура целевой функции y(u)  отражает вклад каждого вида деятельности ЭИС в общий результат. При максимизации с_j представляет собой “полезность” j-го вида деятельности (ущерб, наносимый конкуренту по бизнесу, предотвращенный ущерб), а в случае минимизации характеризует затраты (потери собственные, расход материальных средств). Линейность модели выявляется или принимается в качестве допущения на этапе формализации задачи. Линейность предполагает наличие двух свойств — пропорциональности и аддитивности, присущих как целевой функции, так и ограничениям. Пропорциональность целевой функции означает, что вклад каждой управляемой переменной в целевую функцию пропорционален величине этой переменной. Аддитивность же целевой функции заключается в том, что целевая функция представляет собой сумму вкладов от различных управляемых переменных. Пропорциональность ограничений проявляется в том, что общий объем потребляемых ресурсов прямо пропорционален величинам управляемых переменных. Аддитивность ограничений состоит в том, что величина ресурса должна представлять собой сумму расходов по видам деятельности, каждое слагаемое которой пропорционально величине соответствующей управляемой переменной. В формализованном виде задачу ЛП можно представить следующим образом:

Определить

где              , (1.1)

Условие неотрицательности, накладываемое на переменные x_j, означает, что ни одному виду деятельности ЭИС не может быть приписан отрицательный уровень. Ограничение типа ≥ нельзя рассматривать как ограничение в буквальном смысле этого слова. Наличие такого неравенства предполагает необходимость обязательного выполнения каких-либо планов, заданий, нормативов.

Математическая формулировка задачи ЛП выглядит следующим образом: необходимо определить значения управляемых переменных x_j, доставляющих экстремум целевой функции y(u) на всем множестве стратегий U = {u} и удовлетворяющих всем имеющимся в задаче ограничениям. Этой формулировкой задача ЛП считается поставленной математически, что позволяет осуществлять поиск ее оптимального решения известными математическими методами.

Формальную постановку задачи ЛП (1.1) для удобства можно представить в упрощенном виде:

определить max (или min) W(x) = при ограничениях:

c_j x_j (≤, = или ≥) b_i, i = 1, …, m; xj ≥ 0,

где W(x) — новое обозначение ЦФ, т. е. W(x) = y(u) = f(x).

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

 

1.2. Графический метод решения задач ЛП

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

(c, x) → max

Ax ≤ b,

где x = (x₁, x₂), c = (c₁, c₂), b = (b₁, b₂, ..., b_m), A - матрица размера (m × 2).

Очевидно, что  при данной постановке задачи допустимое множество X в плоскости (x₁, x₂) представляет собой многоугольник (не обязательно замкнутый), образованный пересечением полуплоскостей H+a_ib_i (где a_i - i-я строка матрицы A, i = 1, ..., m), соответствующих ограничениям вида a_i1x₁ + a_i2x₂ ≤ b_i в исходной задаче. Линии уровня функции f(x) = (c, x) (линией уровня называется множество {x R: f(x)= α, α R}) образуют семейство параллельных прямых H_cα. При этом grad f(x) = c, т.е. градиент целевой функции всюду одинаков и является нормалью каждой из данных полуплоскостей. В соответствии с предыдущим, поиск решения задачи сводится к нахождению максимального числа α* среди всех таких α, что полуплоскость H_cα имеет непустое пересечение с X. При этом X - множество решений задачи. При неограниченном решений может и не быть, т.е. H_cα X Ø при всех α→ .

Из графического представления  ясна характерная особенность задачи ЛП (при c ≠ 0): если ее решение существует, то оно достигается обязательно  на границе. Отметим, что в рассмотренной  задаче ЛП на максимум при поиске α* происходит как бы перемещение прямой H_cα в направлении вектора c. Если же решается задача ЛП на минимум, и, следовательно, ищется минимальное α*, удовлетворяющее указанным требованиям, то H_cα перемещается в направлении, противоположном вектору c.

Пример 1.2.1 Пусть дана задача ЛП

2x + y → max

-x + y ≤ 2,

x + 2y ≤ 7,

4x - 3y ≤ 6,

x ≥ 0, y ≥ 0.

Геометрическая интерпретация  задачи приведена на рис. 1. Ясно, что  решением является точка пересечения  прямых

x + 2y = 7 и 4x - 3y = 6, т.е. (x*, y*) = (3, 2).

Очевидно, что графический метод решения задач ЛП применим лишь в случае малой размерности пространства. В общем случае для решения задач линейного программирования в пространстве произвольной размерности широко используется симплекс-метод.  
1.3. Симплекс-метод решения задач ЛП

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

Применение  симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (x₁, ..., x_n), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (x₁, ..., x_m), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1.

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

 

Симплекс-таблица

	1	x1	x2	...	xm	xm+1	...	xn
x0	A0,0	0	0	...	0	A0,m+1	...	A0,n
x1	A1,0	1	0	...	0	A1,m+1	...	A1,n
x2	A2,0	0	1	...	0	A2,m+1	...	A2,n
...	...	...	...	...	...	...	...	...
xm	Am,0	0	0	...	1	Am,m+1	...	Am,n

 

Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует определенному ограничению-равенству задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (x₁, ..., x_m). Сверху от таблицы приведен набор всех переменных задачи, где x_m+1, ..., x_n - свободные переменные задачи.

На начальном шаге алгоритма симплекс-метода должно быть выбрано базисное допустимое решение (x₁, ..., x_m) ≥0 при x_j = 0 (j = m+1, ..., n), следовательно, все свободные члены ограничений A_i,0 ≥0 (i = 1, ..., m). Когда это условие выполнено, симплекс-таблица называется прямо-допустимой, так как в этом случае базисные переменные, равные A_i,0, определяют допустимое решение прямой задачи линейного программирования. Если все коэффициенты целевой функции A_0,j≥  0 (j = 1, ..., m), то симплекс-таблица называется двойственно-допустимой, поскольку соответствующее решение является допустимым для двойственной задачи линейного программирования.

Если симплекс-таблица является одновременно прямо и двойственно  допустимой, т.е. одновременно все A_i,0 ≥ 0 и A_0,j ≥ 0, то решение оптимально.

Действительно, поскольку допустимыми являются лишь неотрицательные значения управляемых  параметров, то изменение целевой  функции за счет вариации свободных переменных, через которые она выражена, возможно только в сторону увеличения, т.e. будет ухудшаться. Если среди ее коэффициентов имеются A_0,j < 0, то значение целевой функции еще можно уменьшить (т.e. улучшить), увеличивая значение любой свободной переменной x_j с отрицательным коэффициентом A_0,j при побочном уменьшении базисных переменных, чтобы оставались справедливы ограничения задачи. Теоретически можно использовать любую свободную переменную x_j с A_0,j < 0, но на практике обычно действуют в соответствии со стратегией наискорейшего спуска, выбирая минимальный элемент A_0,p < 0 из всех отрицательных A_0,j <0:

A_0,p = min A_0,j < 0.

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

Её индекс легко определить, если среди положительных элементов  ведущего столбца p найти элемент, минимизирующий отношение (A_i,0 / A_i,p):