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

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

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

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

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

а) строится начальное решение;

б) проводится оценка найденного решения по соответствующему критерию оптимальности;

в) если условие оптимальности не выполняется, переходят к новому решению.

Этапы б) и в) выполняются до тех пор, пока будет получено оптимальное решение.

Все правила проиллюстрируем на примере [6]:

Пример 2. Найти при ограничениях:

I этап.Построение начального решения.

а) Приводим задачу к каноническому виду.

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

.

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

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

Получили канонический вид уравнений.

б) В ограничения, где дополнительные переменные вычитаются, добавляют искусственные переменные с последующими номерами. Эти искусственные неизвестные вносят и в целевую функцию с коэффициентом . В результате таких преобразований задача приобретает вид:

где - основные переменные;

- дополнительные переменные;

- искусственные переменные.

Все переменные неотрицательны.

в) Выписывают векторы коэффициентов при неизвестных и вектор свободных членов.

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

Таблица 2.

Базис С -1 М М С.О.
 
M -1
M -1
-1 -
Z- строка   -2  
M- строка   -1 -1  

 

Заполняют таблицу по правилам:

  1. Вносят все векторы .
  2. В самую верхнюю строку записывают коэффициенты целевой функции при соответствующих неизвестных.
  3. В качестве первоначального базиса берут векторы, образующие единичную матрицу, - в данном случае это векторы , , .
  4. В столбец С переносят из верхней строки числа, соответствующие базисным векторам.
  5. Чтобы получить элементы двух последних строк, вектор С умножают последовательно на векторы , ,…,и от результата вычитают соответствующие число из верхней строки.

, и т.д.

В М – строку записывают коэффициент при М, в Z – строку –коэффициент без М.

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

,

II этап.Проверка оптимальности решения.

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

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

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

в) Определяют симплексные отношения, для этого элементы делят на положительные элементы ключевого столбца (на отрицательные и нули не делят). Ключевую строку выбирают по наименьшему симплексному отношению (С.О.), она показывает, какой вектор выйдет из базиса. В примере симплексные отношения равны 4 и 1, в третьей строке ставят прочерк, так как на (-1) не делят. Наименьшее значение равно 1, ключевой будет вторая строка, из базиса уйдет .

г) Элемент, стоящий на пересечении ключевой строки и ключевого столбца, называется генеральным. В построенной таблице генеральный элемент равен 5, он выделен.

III этап.Построение нового решения (табл.3)

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

б) Столбец С заполняют по правилу, изложенному выше –из верхней строки.

 

Таблица 3

Базис С -1 М М С.О.
 
M 9/5 -1 1/5 5/3
1/5 -1/5
6/5 -1/5 10/3
Z- строка   7/5 -2/5  
M- строка   9/5 -1 1/5  

в) вычисления ведут по таким правилам.

1. Элементы ключевой строки делят на генеральный элемент и записывают в новую таблицу.

2. Ключевой столбец дополняют нулями.

3. Если в ключевой строке есть нули, то соответствующие им столбцы переносят без изменения.

4. Остальные элементы определяют по правилу прямоугольника. Для его построения в предыдущей таблице старый элемент соединяют с ключевой строкой и ключевым столбцом, а затем по строке и столбцу ведут к генеральному элементу (см. табл.1)

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

Решение, соответствующее II –й таблице, такое:

,,

Для анализа второго решения повторяют все действия, начиная со II этапа. Проверка показала, что во II таблице условие оптимальности не выполняется. Вновь выбирают ключевой столбец (), находят симплексные отношения и находят ключевую строку (первая), генеральный элемент равен 9/5. Все вычисления приводят к таблице 4. Из базиса уходит последний искусственный вектор , поэтому таблица 4 не будет содержать М-строку.

Таблица 4

Базис С -1 С.О.
 
-1 5/3 -5/9 1/9 -
2/3 1/9 -2/9
2/3 -1/3
Z- строка   -1/3 7/9 -5/9  

Решение в соответствии с таблицей 3 имеет вид:

,

Данное решение оптимальным не является – проверку проведем по Z- строке. Строим еще одну таблицу:

Таблица 5

Базис С -1
 
-1 10/3 -1/6 -5/6
1/3 -1/6 -1/6
-1/2 3/2
Z- строка   -8/3 -1/6 -7/6

Условие оптимальности выполнилось. Оптимальное решение имеет вид:

 

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

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

Методические указания и задания Математическое программирование

К изучению раздела курса прикладной математики.. Математическое программирование.. для студентов экономических специальностей заочной и дневной форм обучения..

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

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

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

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

ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.
Задача линейного программирования (ЛП) возникает из необходимости оптимально использовать имеющиеся ресурсы. Это задачи, связанные с целеобразованием и анализом целей и функций; задачи разработки и

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГРАФИЧЕСКИМ МЕТОДОМ.
Нахождение решения задачи ЛП (1) – (2) на основе ее геометрической интерпретации [5] включает следующие этапы: 1. Строят прямые, уравнения которых получаются в результате замены в ограниче

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

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

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