Содержание.
1. Общая характеристика симплекс метода.4
2. Решение различных задач симплекс методом.11
3. Табличный симплекс метод.21
Список использованной литературы.31
Симлекс-метод - это характерный пример итерационных вычислений. используемых при решении большинства оптимизационных задач.
В вычислительной схеме симплекс-метода реализуется упорядоченный процесс, при котором, начиная с некоторой исходной допустимой угловой точки ( обычно начало координат ), осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех пор, пока не будет найдена точка, соответствующая оптимальному решению.
.
1. Общая характеристика симплекс метода.
Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.
Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП (задачи линейного программирования) состоит
- умение находить начальный опорный план;
- наличие признака оптимальности опорного плана;
- умение переходить к нехудшему опорному плану.
Пусть ЗЛП представлена системой ограничений в каноническом виде:
Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части
Пусть система ограничений имеет вид
Сведем задачу к каноническому виду. Для этого прибавим к левым частям неравенств дополнительные переменные
которая имеет предпочтительный вид
В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю
Пусть далее система ограничений имеет вид
Сведём её к эквивалентной вычитанием дополнительных переменных
Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные
Пусть исходная ЗЛП имеет вид
причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:
Задача (4)-(6) имеет предпочтительный план. Её начальный опорный план имеет вид
Если некоторые из уравнений (2) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.
Теорема. Если в оптимальном плане
М-задачи (4)-(6) все искусственные переменные
Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный базис и решают расширенную М-задачу, которая имеет начальный опорный план
Решение исходной задачи симплексным методом путем введения искусственных переменных
Если в результате применения симплексного метода к расширенной задаче получен оптимальный план, в котором все искусственные переменные
Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.
Признаки оптимальности.
Теорема. Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки
Теорема. Если исходная задача решается на минимум и для некоторого опорного плана все оценки
Для привидения системы ограничений неравенств к каноническому виду, необходимо в системе ограничений выделить единичный базис.
I. Ограничения вида «0»- ресурсные ограничения. Справа находится то что мы используем на производстве, слева - то что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0».
II. Ограничения вида «=». Часто бывает, что несмотря на то что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса - Yi. В систему ограничений они входят с коэффициентом «1». а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin - «+M», при Fmax - «-M»).
III. Ограничения вида «0» - Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл - перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0». А искусственные переменные (Y) как в предыдущем случае.
Алгоритм симплекс метода.
(первая симплекс таблица)
X1+ q1,m+1 Xm+1 + …. + q1,m+nXm+n = h1
X2+ q1,m+1 Xm+1 + …. + q1,m+nXm+n = h1
X3+ q1,m+1 Xm+1 + …. + q1,m+nXm+n = h1
……………………………………………………………….
Xm+qm,m+1 Xm+1 + …. + qm,m+nXm+n =hm
В ней m базисных переменных, k свободных переменных. m+k=n - всего переменных.
Fmin= C1X1+ C2X2+ C3X3+....+ CnXn
Все hi должны быть больше либо равны нулю, где i=1,2...m. На первом шаге в качестве допустимого решения принимаем все Xj=0 (j=m+1,m+2,...,m+k). При этом все базисные переменные Xi=Hi.
Для дальнейших рассуждений вычислений будем пользоваться первой симплекс таблицей (таблица1).
Таблица 1.
Симплекс таблица.
C | Б | H | C1 | C2 | … | Cm | Cm+1 | … | Cm+k |
X1 | X2 | … | Xm | Xm+1 | … | Xm+k | |||
C1C2C3::Cm | X1X2X3::Xm | h1h2h3::hm | 100::0 | 010::0 | :::::: | 000::0 | q1,m+1q2,m+1q3,m+1::qm,m+1 | :::::: | q1,m+kq2,m+kq3,m+k::qm,m+k |
F= | F0 | | | … | m | m+1 | … | m+k |
Первый столбец- коэффициенты в целевой функции при базисных переменных.