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

Министерство  сельского хозяйства РФ

Федеральное государственное бюджетное образовательное учреждение

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

Пермская государственная  сельскохозяйственная академия

имени Ак. Д. Н. Прянишникова

 

 

 

 

 

Курсовая работа

по дисциплине «Методы оптимизации»

на тему: «Алгоритм решения задач симплексным методом»

 

 

 

 

 

Руководитель:

Старший преподаватель 

кафедры ИТАП                              ______________                               Гревцев А. М.

Исполнитель:                                     подпись, дата

Студент группы ПИ-31Б               ______________                           

                                                           подпись, дата

                                                                         

 

 

 

 

г. Пермь, 2011. 
Содержание

 

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

1 Описание симплексного  метода..…………...……………………………...……….4

2 Алгоритм решения задач симплексным методом……………………...…………..9

2.1 Графический метод……………………………………………………………….16

2.2 Табличный симплекс  – метод……………………………………………….…...21

2.3 Модифицированный симплекс  – метод.………………………………………...25

2.4 Алгоритм метода  искусственного базиса………………...…………….……….29

2.5 Двойственный симплекс-метод………………..………………………………...30

3 Решение реальной производственной задачи…………………………………….32

3.1 Постановка задачи………………………………………………………………..32

3.2 Решение задачи…………………………………………………………………...32

Заключение……………………………………………………………………………42

Список используемой литературы…………………………………………………..44

 

Введение

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

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

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

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

 

1 Описание симплексного метода

 

Симплекс - выпуклый многоугольник в n-мерном пространстве с n + 1 вершинами, не лежащими в одной гиперплоскости. Симплексы выделены в отдельный класс потому, что в n-мерном пространстве n точек всегда лежат в одной гиперплоскости(гиперплоскость делит пространство на два полупространства). Так что симплекс - это простейший многоугольник, содержащий некоторый объем n-мерного пространства.

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

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

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

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

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

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

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

1) Добавления неотрицательной остаточной переменной в левую часть неравенства вида « ≤ ».

2) Вычитания неотрицательной избыточной переменной из левой части неравенств вида « ≤ ».

Избыточные и достаточные переменные называют свободными.

Кроме того, все элементы правой части b_i делают неотрицательными, либо умножая для этого i-ое уравнение на -1, если b_i < 0, либо используя эквивалентность следующих отношений:

                                           (1.1)

Запишем целевую функцию:

F(X) =c₁x₁+c₂x₂+...+c_nx_n => max,                                                                       (1.2)

Где F(X) – целевая функция.

        c_i – коэффициенты при переменных.

        x_n – базисные переменные.

Система ограничений и условие неотрицательности будут выглядеть следующим образом:

 

a₁₁x₁ + a₁₂x₂ + . . . + a_1nx_n ≤ b₁

a₂₁x₁ + a₂₂x₂ + . . . + a_2nx_n ≤ b₂

. . . . . . . . . . . . . . . . . . . . . . . . .                                                                            (1.3)

a_m1x₁ + a_m2x₂ + . . . + a_mnx_n ≤ b_m                                                                           

 

x_j ≥ 0, (j = 1, 2, . . . n)                                                                                         (1.4)                                                     

 

 

 

Запишем представленную систему ограничений  в канонической форме:

a₁₁ x ₁+a₁₂ x ₂+...+a_1n x _n = b₁

a₂₁ x ₁+a₂₂ x ₂+...+a_2n x _n = b₂                                                                         (1.5)

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

a_m1 x ₁+a_m2 x ₂+...+a_mn x _n = b_m

 

Пусть A = (a_ij) — матрица m*n, b = (b₁, … , b_m)^T — вектор-стоблец,                  c = (c₁, … , c_n) — вектор-строка. Если a = (a₁, … , a_m) и b = (b₁, … , b_m), то под неравенством a ≥ b будем понимать m неравенств a_i ≥ b_i (i = 1, … , m).

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

max cx:

 

 

 

max cx:

 

 

 

Матрица A = (a_ij) (i = 1, … , m; j = 1, 2, . . . n), составленная из коэффициентов системы (1.5), называется симплекс-таблицей.

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

Базисные Переменные	Свободные Переменные	X1	.......	Xi	.......	Xm
X1	B1	1	.......	0	.......	0
X2	B2	0	.......	0	.......	0
.....	.....	.....	.....	.....	.....	.....
Xi	Bi	0	.......	1	.......	0
.....	.....	.....	.....	.....	.....	.....
Xm	Bm	0	.......	0	.......	1
F(X)	C0	0	.......	0	.......	0

 

Решение Х системы уравнений, в котором все небазисные переменные равны нулю, называется базисным решением. Если все компоненты базисного решения неотрицательны, то оно называется допустимым базисным решением, или опорным планом. При этом сама база также называется допустимой.

Переход от текущей базы к соседней называется итерацией.

Алгоритм симплекс-метода:

1. Определить число и состав базисных и свободных переменных.
2. Выразить базисные переменные через свободные переменные.
3. Выразить целевую функцию через свободные переменные.
4. Построить начальную симплекс-таблицу.
5. Проверить решение на оптимальность: если в F-строке (кроме С₀) все С_j=0, то получено оптимальное решение: X=(B₁,...,B_m,0,...,0), F=C₀. Если же существует C_j<0, то решение можно улучшить, но предварительно надо проверить факт существования решения.
6. Проверить существование решения: рассмотрим все столбцы, у которых С_j<0, если существует хотя бы один столбец, у которого все коэффициенты A_ij<0, то задача решения не имеет, т.к. множество допустимых решений D не ограничено и целевая функция неограниченно возрастает. Если таких столбцов нет, то переходим к следующему этапу. Выбрать свободную переменную, которую надо ввести в базис (выбор разрешающего столбца): это столбец с минимальным значением С_j (пусть это k-й столбец). Выбрать базисную переменную, которую надо вывести из базиса (выбор разрешающей строки). Рассмотрим k-й столбец и все его элементы, которые больше нуля, т.е. A_ik>0. Для всех этих элементов находим отношение B_i/A_ik и выбираем строку, которая соответствует минимальному значению этого отношения (пусть это i-я строка). Соответствующая i-я переменная X_i выводится из базиса, при нескольких одинаковых отношениях берем любую строку. Элемент A_ik называется разрешающим элементом.
7. Пересчитать симплекс-таблицу.

• составляем новую симплекс-таблицу, заменив в составе базисных переменных X_i на X_k;

• заполняем сначала новую k-ю строку, записывая в нее элементы старой     i-ой строки, поделенные на разрешающий элемент;
• после заполнения k-ой строки заполняем оставшиеся строки. Для этого k-ю строку умножаем последовательно на такие числа, чтобы после сложения ее с каждой строкой старой таблицы в k-ом столбце получить везде ноль (кроме единицы в k-ой строке).