Конспект лекций по предмету "Модели и методы"

Узнать цену работы по вашей теме


Симплексный метод

Симплексный метод или метод последовательного улучшения плана является одним из основных методов решения задач ЛП. название симплексный метод берет от слова «симплекс», которым создатель метода Р. Данциг обозначил наложенное на переменные x1, x2 ... xn ограничение x1+x2+ ... +xn=1.

þ В математике симплексом в k-мерном пространстве называется совокупность k+1 вершин.

Так для плоскости при k=2 симплексом будет треугольник; в пространстве при k=3 симплексом будет тетраэдр, имеющий 4 вершины.
С учетом этого понятия аналитический метод решения задачи ЛП называют симплекс-методом. Он основан на алгоритме направленного перебора вершин. Этот алгоритм обеспечивает переход от одной вершины к другой в таком направлении, при котором значение целевой функции от вершины к вершине улучшается.

þ Определение значения целевой функции и переменных в одной вершине считается итерацией.

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

ì4x1+9x2 £ 56
(5.14) í5x1+3x2 £ 37
î-x1+2x2 £ 2

обращающее в максимум линейную форму:

¦=3x1+4x2 (5.15)

Вначале перейдем от системы неравенств (5.14) к системе уравнений, добавив к левым частям неравенств неотрицательные переменные x3, x4, x5. Мы получим:

ì4x1+9x2+x3+0 . x4+0 . x5=56
(5.16) í5x1+3x2+0 . x3+x4+0 . x5=37
î-x1+2x2+0 . x3+0 . x4+ x5=2

¦= 3x1+4x2+0 . x3+0 . x4+0 . x5 (5.17)

перепишем теперь систему (5.16) в виде системы 0-уравнений:

ì0=56 - (4x1+9x2+1 . x3+0 . x4+0 . x5)
(5.18) í0=37 - (5x1+3x2+0 . x3+1 . x4+0 . x5)
î0=2 - (-x1+2x2+0 . x3+0 . x4+1 . x5)

¦=0 - (-3x1-4x2-0 . x3-0 . x4-0 . x5) (5.19)

заметим, что система (5.18) может быть записана в виде одного векторного равенства:

0=B-(A1x1+A2x2+A3x3+A4x4+A5x5),

где вектор-столбец В имеет своими компонентами свободные члены, а векторы A1, A2, ... , A5 - коэффициенты при соответствующих переменных x1, x2, x3, x4, x5. Иными словами:


















В=


A1=


A2=


A3=


A4=


A5=





-1













Линейная форма имеет вид: ¦=3x1+4x2+0 . x3+0 . x4+0 . x5.

Векторы A3, A4, A5 образуют базис. Это означает, что, присвоив х1=0, х2=0, получаем из (5.16) первое базисное решение: x1=0; x2=0; x3=56; x4=37; x5=2.
При этом значение линейной формы ¦=0. На основании (5.18) строим первую симплексную таблицу.

Симплексная таблица строится следующим образом:

В заглавной строке пишем последовательно векторы B, A1, A2, A3, A4 , A5. Слева добавляем колонку «Базисные векторы», рядом с ней колонку «С», в которой поставлены коэффициенты при базисных переменных в линейной форме, в данном случае величины С3, С4, С5. В последней строке, называемой индексной, и обозначаемой через ¦ j-Сj, проставляются числа, равные значению линейной формы, в соответствием с уравнением (j=1, 2, 3, 4, 5). В итоге мы имеем таблицу 5.3.


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

Доработать Узнать цену работы по вашей теме
Поделись с друзьями, за репост + 100 мильонов к студенческой карме:

Пишем конспект самостоятельно:
! Как написать конспект Как правильно подойти к написанию чтобы быстро и информативно все зафиксировать.

Другие популярные конспекты:

Конспект Основные проблемы и этапы развития средневековой философии
Конспект Проблема познаваемости мира. Гносеологический оптимизм, скептицизм, агностицизм. Взаимосвязь субъекта и объекта познания
Конспект Понятие финансовой устойчивости организации
Конспект Внутренняя политика первых Романовых.
Конспект ПРОБЛЕМЫ КВАЛИФИКАЦИИ ПРЕСТУПЛЕНИЙ
Конспект Понятие мировоззрения, его уровни и структура. Исторические типы мировоззрения
Конспект Синтагматические, парадигматические и иерархические отношения в языке
Конспект Тема 1.2. Плоская система сходящихся сил. Определение равнодействующей геометрическим способом 13
Конспект Происхождение человека. Основные концепции антропосоциогенеза. Антропогенез и культурогенез.
Конспект Общая характеристика процессов сбора, передачи, обработки и накопления информации