рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

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

 

Симплексный метод или метод последовательного улучшения плана является одним из основных методов решения задач ЛП. название симплексный метод берет от слова «симплекс», которым создатель метода Р. Данциг обозначил наложенное на переменные 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.

 

Развернуть
Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Методы и модели

ЛЕКЦИИ... По дисциплине...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Симплексный метод

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

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

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

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

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

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

W=W (x, a, x)
  В соответствии с введенными терминами, математическая модель задачи имеет следующий вид:   W=W (x, a, x) ® max (min) (2.1) x &

Выпуклые множества
  Предварительно дадим некоторые понятия, весьма важные для линейного программирования.   þ множество точек называется выпуклыми,

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

Значения линейной формы на выпуклом множестве
  Предположим, что задана некоторая система из m-линейных неравенств (или уравнений) с n переменными х1, х2, ..., хn. Система нер

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

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

Решения задач линейного программирования
  Задачу линейного программирования (ЛП) можно решать аналитическими и графическими методами. Аналитические методы являются основой для решения задачи на ЭВМ. Их единственный н

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

Задач линейного программирования
  Перепишем основную задачу линейного программирования в векторной форме: найти максимум функции   F=CX (5.5)   при у

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

Постановка задачи нелинейного программирования
  В общем виде задача нелинейного программирования (ЗНП) формируется следующим образом:   f (x1, x2, ..., xn) ® max (mi

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

Многокритериальная оптимизация
  þ задачи, в которых оптимизацию проводят по нескольким параметрам, называют задачами многокритериальной или векторной оптимизации

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги