Симплекс метод

ОГЛАВЛЕНИЕ

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

1. Теоретический раздел…………………………………………………………….4

1.1. Понятие симплекс-метода……………………………………………….4

1.2. Реализация симплекс-метода с помощью симплекс-таблиц…………..7

1.3. Смысл двойственной задачи  линейного программирования………...10

2. Практический раздел…………………………………………………………….14

2.1. Описание производственной  ситуации………………………………..14

2.2. Математическое описание ситуации…………………………………..15

2.3. Решение задачи………………………………………………………….16

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

Библиографический список………………………………………………………..24

 

 

 

ВВЕДЕНИЕ

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

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

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

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

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

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

 

1. ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ

1.1. Понятие симплекс-метода

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

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

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

 

(1)

 

Переменные  x₁, x₂,…, x_r называются базисными, а весь набор {x₁, x₂,…, x_r} - базисом, остальные переменные называются свободными, система ограничений (1) называется системой, приведенной к единичному базису. [2]

Придавая определенные значения свободным переменным и  вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения и являются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные х₁, х₂, ..., х_r, то решение {b₁, b₂,..., b_r, 0, ..., 0} будет опорным при условии, что b₁, b₂,..., b_r ≥ 0.

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

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

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

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

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

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

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

Если ограничительные  условия заданы неравенствами, то их можно преобразовать в равенства путем введения новых неотрицательных переменных - так называемых балансовых (выравнивающих). Так, например, в неравенстве 
a₁x₁+ a₂x₂+…+ a_nx_n ≤ b достаточно добавить в левую часть некоторую величину x_n+1 ≥ 0 и получится равенство a₁x₁+ a₂x₂+…+ a_nx_n+ x_n+1=b.

Если переменная x_l не подчинена условию неотрицательности, то её заменяют разностью двух неотрицательных переменных: x_l = u_l- v_l, где u_l, v_l ≥ 0.

Задача минимизации  функции  f может быть сведена к задаче максимизации функции -f. [1]

1.2. Реализация симплекс-метода с помощью симплекс-таблиц

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

f = γ₀+ γ_r+1 x_r+1+…+ γ_n x_n → max, min

     

 

x_i ≥ 0, i = 1,2, …, n.

Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные x₁, x₂, ..., x_r и что при этом b'₁, b'₂,..., b'_r ≥ 0 (соответствующее базисное решение является опорным).

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

 

 

 

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

Базисные  переменные	Свободные члены	x1	х2	…	…	xr	xr+1	xr+2	…	…	xn
x1	b'1	1	0	…	…	0	-a1,r+1	-a1,r+1	…	…	-a1n
х2	b'2	0	1	…	…	0	-а2,r+1	-а2,r+1	…	…	-а2n
…	…	…	…	…	…	…	…	…	…	…	…
…	…	…	…	…	…	…	…	…	…	…	…
xr	b'r	0	0	…	…	1	-ar,r+1	-ar,r+2	…	…	-arn
f	γ0	0	0	…	…	0	-γr+1	-γr+2	…	…	-γn

Таблица 1.

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

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

 

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

• Просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов y₀) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при решении задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;
• Просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту в последней строке - разрешающий столбец, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет;
• Среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, так же, как и строка, в которой он находится. [5] Если на каком-либо этапе расчета возникает неопределенность в выборе разрешающей строки, т.е. оказывается несколько равных минимальных отношений, то следует выбирать ту строку, для которой отношение элементов следующего столбца к разрешающему является наименьшим. Если при этом снова оказываются равные минимальные отношения, то составляют отношения элементов следующего столбца, и так до тех пор, пока разрешающая строка не определится однозначно; [1]
• В дальнейшем базисная переменная, отвечающая строке разрешающего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу разрешающего элемента, вводится в число базисных. Строится новая таблица, содержащая новые названия базисных переменных;
• Разделим каждый элемент разрешающей строки  на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы.
• Строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.
• В новой таблице все элементы разрешающего столбца = 0, кроме самого разрезающего элемента, он всегда равен 1.
• Столбец, у которого в разрешающей строке имеется 0,в новой таблице будет таким же.
• Строка, у которой в разрешающем столбце имеется 0,в новой таблице будет такой же.
• В остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы: