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

Размещено на http://www.allbest.ru/

Министерство образование и науки Украины

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

Механико-энергетический факультет

Контрольная работа

По дисциплине: «основы системного анализа»

Выполнила: Абросимова Л.П.

Киев 2014



Содержание

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

1.1 Решение задачи ЛП графическим методом

2. Симплексный метод решения задачи ЛП. Теоретические сведения

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

Список использованной литературы



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

Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

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

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

можно представить в виде системы двух неравенств (см. рис.1)

ЦФ при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня .

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

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

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

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



Рисунок 1 Геометрическая интерпретация ограничений и ЦФ задачи.

1.1 Методика решения задач ЛП графическим методом

I. В ограничениях задачи заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

II. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.

Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

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

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

IV. Если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня

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

V. Построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны .

VI. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ - против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).

VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .

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

Необходимо найти максимальное значение целевой функции

S = 5x₁+4x₂ > max,



при системе ограничений:

x1-x2?5
x1?10
3x1+4x2?60
-5x1+2x2?10
2x1+x2?10
x1?0
x2?0

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

Построим уравнение x₁-x₂ = 5 по двум точкам.

Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = -5. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 5. Соединяем точку (0;-5) с (5;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 * 0 - 1 * 0 - 5 ? 0, т.е. x₁-x₂ - 5? 0 в полуплоскости ниже прямой. Построим уравнение x₁ = 10.

Эта прямая проходит через точку x₁ = 10 параллельно оси OX₂. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 * 0 - 10 ? 0, т.е. x₁ - 10? 0 в полуплоскости левее прямой.

Построим уравнение 3x₁+4x₂ = 60 по двум точкам.

Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 15. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 20. Соединяем точку (0;15) с (20;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 3 * 0 + 4 * 0 - 60 ? 0, т.е. 3x₁+4x₂ - 60? 0 в полуплоскости ниже прямой.

Построим уравнение -5x₁+2x₂ = 10 по двум точкам.

Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 5. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = -2. Соединяем точку (0;5) с (-2;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: -5 * 0 + 2 * 0 - 10 ?0, т.е. -5x₁+2x₂ - 10? 0 в полуплоскости ниже прямой.

Построим уравнение 2x₁+x₂ = 10 по двум точкам.

Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 10. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 5. Соединяем точку (0;10) с (5;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 2 * 0 + 1 * 0 - 10 ? 0, т.е. 2x₁+x₂ - 10? 0 в полуплоскости ниже прямой.



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

Обозначим границы области многоугольника решений.

симплексный линейный программирование геометрический



Рассмотрим целевую функцию задачи

S = 5x₁+4x₂ > max.

Построим прямую, отвечающую значению функции S = 0: S = 5x₁+4x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации S(X). Начало вектора - точка (0; 0), конец - точка (5; 4). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

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

Прямая S(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых(4) и (5), то ее координаты удовлетворяют уравнениям этих прямых:

-5x₁+2x₂=10

2x₁+x₂=10

Решив систему уравнений, получим: x₁ = 1.1111, x₂ = 7.7778

Откуда найдем максимальное значение целевой функции:

S(X) = 5*1.1111 + 4*7.7778 = 36.6667 ? 36.7



2. Симплексный метод решения задачи ЛП. Теоретические сведения

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

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

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

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как

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

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X1, X2, ..., Xr, то решение {b1, b2,..., br, 0, ..., 0} будет опорным при условии, что b1, b2,..., br ? 0.

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

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

Реализация решения задачи симплекс-методом наглядно показана на блок-схеме (рис.1).

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

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

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

Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные X1, X2, ..., Xr и что при этом b1, b2,..., br ? 0 (соответствующее базисное решение является опорным).

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



Далее эта система оформляется в виде симплекс-таблиц:

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

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

Алгоритм перехода к следующей таблице такой:

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

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

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

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

строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место;

в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1;

столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же;

строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же;

в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:



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

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

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

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

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

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

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

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

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

Найти значения переменных x1...x2, при которых функция:

S =		5	x1	+	4	x2



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

x1-x2?5	(1)
x1?10	(2)
3x1+4x2?60	(3)
-5x1+2x2?10	(4)
2x1+x2?10	(5)
x1?0
x2?0

Избавимся от неравенств в ограничениях, введя в ограничения 1, 2, 3, 4, 5 неотрицательные балансовые переменные y1, y2, y3, y4, y5.

x1-x2+y1=5	(1)
x1+y2=10	(2)
3x1+4x2+y3=60	(3)
-5x1+2x2+y4=10	(4)
2x1+x2+y5=10	(5)
x1, x2, s1, s2, s3, s4, s5 ? 0

Ищем в системе ограничений базисные переменные.

Из последней системы ограничений можно выделить базисные переменные y1,y2,y3,y4,y5.

Теперь мы можем сформировать начальную симплекс-таблицу.

Начальная симплекс-таблица

БП	x1	x2	y1	y2	y3	y4	y5	Решение	Отношение
y1	1	-1	1	0	0	0	0	5	5/1=5
y2	1	0	0	1	0	0	0	10	10/1=10
y3	3	4	0	0	1	0	0	60	60/3=20
y4	-5	2	0	0	0	1	0	10	--
y5	2	1	0	0	0	0	1	10	10/2=5
S	5	4	0	0	0	0	0	0	--



Итерация 1

БП	x1	x2	y1	y2	y3	y4	y5	Решение	Отношение
y1	0	-1.5	1	0	0	0	-0.5	0	--
y2	0	-0.5	0	1	0	0	-0.5	5	--
y3	0	2.5	0	0	1	0	-1.5	45	45/2.5=18
y4	0	4.5	0	0	0	1	2.5	35	35/4.5=7.7777777777778
x1	1	0.5	0	0	0	0	0.5	5	5/0.5=10
S	0	1.5	0	0	0	0	-2.5	-25	--

Итерация 2

БП	x1	x2	y1	y2	y3	y4	y5	Решение	Отношение
y1	0	0	1	0	0	0.33333333333333	0.33333333333333	11.666666666667	--
y2	0	0	0	1	0	0.11111111111111	-0.22222222222222	8.8888888888889	--
y3	0	0	0	0	1	-0.55555555555556	-2.8888888888889	25.555555555556	--
x2	0	1	0	0	0	0.22222222222222	0.55555555555556	7.7777777777778	--
x1	1	0	0	0	0	-0.11111111111111	0.22222222222222	1.1111111111111	--
S	0	0	0	0	0	-0.33333333333333	-3.3333333333333	-36.666666666667	--

Достигнуто оптимальное решение, т.к. в строке целевой функции нет положительных коэффициентов.

Оптимальное значение функции S(x)= 36.666666666667 ? 36.7

Достигнуто оптимальное решение, т.к. в строке целевой функции нет положительных коэффициентов.

Оптимальное значение функции S(x)= 36.666666666667 ? 36.7

достигается в точке с координатами:

x1=	1.1111111111111
x2=	7.7777777777778
y1=	11.666666666667
y2=	8.8888888888889
y3=	25.555555555556
y4=	0
y5=	0



Список использованной литературы

1. Материал лекционных занятий;

2. Алесинская Т.В. - Задачи по исследованию операций с решениями.

3. Вентцель, Е.С. Исследование операций: Задачи, принципы, методология / Е.С.Вентцель. - М.: Высшая школа, 2001. - 208 с.

4. Кофман, А. Методы и модели исследования операций / А.Кофман. - М.: Мир, 1966. - 523 с.

Размещено на Allbest.ru

...