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

Содержание

1. Симплекс-метод
2. Авторы симплекс-методаСимплекс-метод был разработан и впервые применен
3. Авторы симплекс-методаДжордж Данциг будучи студентом университета, однажды
4. Общие положенияГеометрический смысл симплексного метода состоит в
5. Процесс применения симплексного метода предполагает реализацию
6. Алгоритм симплекс-метода. ШАГ 1Формулировка ЗЛП (формирование целевой
7. В ограничения задачи вводятся дополнительные переменныеАлгоритм симплекс-метода.
8. Алгоритм симплекс-метода. ШАГ 3Первое допустимое решение: (0,
9. Разрешающий столбец выбирается в соответствии со следующим
10. Необходимо проверить элементы разрешающего столбца. Если среди
11. где s - номер разрешающей строки,r -
12. Алгоритм симплекс-метода. ШАГ 8Пересчет элементов разрешающего столбца. Все они (кроме разрешающего элемента) должны стать равными нулю:
13. Элементы, не принадлежащие разрешающим столбцу и строке,
14. Алгоритм повторяем с шага 4 до тех
15. Слайд 15
16. Скачать презентанцию

Авторы симплекс-методаСимплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. ДанцигомДжорд Бернард Данциг (George Bernard Dantzig; 1914 —2005) — выдающийся математик США. Разработал симплексный алгоритм,

Слайды и текст этой презентации

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

Слайд 2Авторы симплекс-метода
Симплекс-метод был разработан и впервые применен для решения задач

в 1947 г. американским математиком Дж. Данцигом

Джорд Бернард Данциг (George

Bernard Dantzig; 1914 —2005) — выдающийся математик США. Разработал симплексный алгоритм, применяемый при решении задач линейного программирования. Считается «отцом линейного программирования», наряду с советским математиком Л. В. Канторовичем.

Леонид Витальевич Канторович (1912-1986) — советский математик, создатель математической экономики и линейного программирования. Работал в области функционального анализа, вычислительной математики, теории программирования, математической физики и в экономике.

Авторы симплекс-методаСимплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. ДанцигомДжорд

Слайд 3Авторы симплекс-метода
Джордж Данциг будучи студентом университета, однажды опоздал на занятие

и принял написанные на доске уравнения за домашнее задание. Оно

показалось ему сложнее обычного, но через несколько дней Бернард всё-таки смог его выполнить. Оказалось, что это были «нерешаемые в то время» задачи по статистике, над решением которых работали многие учёные.

Вспоминают, что когда Канторович пришёл на свою первую лекцию, студенты дружелюбно закричали ему: «Парень, садись на место! Сейчас профессор придет» Что неудивительно, поскольку «профессору» в это время было 18 лет. Пишут, что он был не очень блестящим лектором, но пытался добросовестно донести до студентов глубинный смысл математических определений и теорем. Экзаменатором он был строгим и требовательным, что, наверное, свойственно для многих вундеркиндов, которые очень многое схватывают на лету и не прощают студентам тупости.

Король Швеции Карл XVI Густав вручает Л.В.Канторовичу Нобелевскую премию

Присуждение премии Дж. Данцигу

Авторы симплекс-методаДжордж Данциг будучи студентом университета, однажды опоздал на занятие и принял написанные на доске уравнения за

Слайд 4Общие положения
Геометрический смысл симплексного метода состоит в последовательном переходе от

одной вершины многогранника ограничений к соседней, в которой целевая функция

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

Общие положенияГеометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений к соседней, в

Слайд 5Процесс применения симплексного метода предполагает реализацию трех основных элементов:
1) способ

определения какого-либо первоначального допустимого базисного решения задачи;
2) правило перехода к

лучшему (точнее, не худшему) решению;
3) критерий проверки оптимальности найденного решения.

Процесс применения симплексного метода предполагает реализацию трех основных элементов:1) способ определения какого-либо первоначального допустимого базисного решения

Слайд 6Алгоритм симплекс-метода. ШАГ 1
Формулировка ЗЛП (формирование целевой функции и системы

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

L(x) = c1x1 + c2x2 + ... + cnxn ?max;
a11x1 + a12x2 + ... + a1nxn ≤ b1,
a21x1 + a22x2 + ... + a2nxn ≤ b2,
...
am1x1 + am2x2 + ... + amnxn ≤ bm;
xj ≥ 0, j = 1,n

Алгоритм симплекс-метода. ШАГ 1Формулировка ЗЛП (формирование целевой функции и системы ограничений).Для определенности будем считать, что решается задача

Слайд 7В ограничения задачи вводятся дополнительные переменные
Алгоритм симплекс-метода. ШАГ 2
Приведение задачи

к канонической форме (перевод функциональных ограничений в систему уравнений).
Все дополнительные

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

В ограничения задачи вводятся дополнительные переменныеАлгоритм симплекс-метода. ШАГ 2Приведение задачи к канонической форме (перевод функциональных ограничений в

Слайд 8Алгоритм симплекс-метода. ШАГ 3
Первое допустимое решение: (0, 0,…,0, b1, b2,

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

Алгоритм симплекс-метода. ШАГ 3Первое допустимое решение: (0, 0,…,0, b1, b2, …, bm) Построение исходной симплекс-таблицы (получение первоначального

Слайд 9Разрешающий столбец выбирается в соответствии со следующим условием:

Алгоритм симплекс-метода. ШАГ

4
Выбор разрешающего столбца
(переменной, вводимой в базис).
Алгоритм симплекс-метода. ШАГ

Проверка условия: все cj ≤ 0. Если НЕТ - осуществляется переход к шагу 5, если ДА - задача решена.

Разрешающий столбец выбирается в соответствии со следующим условием:Алгоритм симплекс-метода. ШАГ 4Выбор разрешающего столбца (переменной, вводимой в базис).

Слайд 10Необходимо проверить элементы разрешающего столбца. Если среди них нет положительных,

то задача неразрешима.

Алгоритм симплекс-метода. ШАГ 6
Проверка условия: все air ≤ 0.

Если ДА - целевая функция неограничена и решения нет, если НЕТ - переход к шагу 7.

Алгоритм симплекс-метода. ШАГ 7

Выбор разрешающей строки (переменной, выводимой из базиса) по условию:

для air > 0, где s - номер разрешающей строки.

Необходимо проверить элементы разрешающего столбца. Если среди них нет положительных, то задача неразрешима.Алгоритм симплекс-метода. ШАГ 6Проверка условия:

Слайд 11где s - номер разрешающей строки,
r - номер разрешающего столбца,
a’sj ,

b’s - новые значения пересчитываемых элементов,
asj , bs - старые значения пересчитываемых элементов,
asr -

старое значение разрешающего элемента.
Таким образом, при пересчете элементов разрешающей строки каждый ее элемент делится на разрешающий элемент.

Алгоритм симплекс-метода. ШАГ 8

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

Для элементов разрешающей строки используются следующие формулы:

где s - номер разрешающей строки,r - номер разрешающего столбца,a’sj , b’s - новые значения пересчитываемых элементов,asj , bs - старые

Слайд 12Алгоритм симплекс-метода. ШАГ 8
Пересчет элементов разрешающего столбца. Все они (кроме

разрешающего элемента) должны стать равными нулю:

Слайд 13Элементы, не принадлежащие разрешающим столбцу и строке, пересчитываются по так

называемому правилу прямоугольника: мысленно выделяется прямоугольник, в котором элемент, подлежащий пересчету

и разрешающий элемент образуют одну из диагоналей. Формулы будут иметь следующий вид:

Алгоритм симплекс-метода. ШАГ 8

Пересчет остальных элементов

Элементы, не принадлежащие разрешающим столбцу и строке, пересчитываются по так называемому правилу прямоугольника: мысленно выделяется прямоугольник, в котором

Слайд 14Алгоритм повторяем с шага 4 до тех пор, пока в

строке коэффициентов целевой функции есть неотрицательные элементы.
Решение находится в первом

и последнем столбцах, значение целевой функции – в правой нижней ячейке (со знаком минус)

Алгоритм повторяем с шага 4 до тех пор, пока в строке коэффициентов целевой функции есть неотрицательные элементы.Решение

Слайд 15

Скачать презентацию

Разделы презентаций

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

Содержание

Слайды и текст этой презентации

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

Слайд 2Авторы симплекс-метода
Симплекс-метод был разработан и впервые применен для решения задач

в 1947 г. американским математиком Дж. Данцигом

Джорд Бернард Данциг (George

Слайд 3Авторы симплекс-метода
Джордж Данциг будучи студентом университета, однажды опоздал на занятие

и принял написанные на доске уравнения за домашнее задание. Оно

Слайд 4Общие положения
Геометрический смысл симплексного метода состоит в последовательном переходе от

одной вершины многогранника ограничений к соседней, в которой целевая функция

Слайд 5Процесс применения симплексного метода предполагает реализацию трех основных элементов:
1) способ

определения какого-либо первоначального допустимого базисного решения задачи;
2) правило перехода к

Слайд 6Алгоритм симплекс-метода. ШАГ 1
Формулировка ЗЛП (формирование целевой функции и системы

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

Слайд 7В ограничения задачи вводятся дополнительные переменные
Алгоритм симплекс-метода. ШАГ 2
Приведение задачи

к канонической форме (перевод функциональных ограничений в систему уравнений).
Все дополнительные

Слайд 8Алгоритм симплекс-метода. ШАГ 3
Первое допустимое решение: (0, 0,…,0, b1, b2,

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

Слайд 9Разрешающий столбец выбирается в соответствии со следующим условием:

Алгоритм симплекс-метода. ШАГ

4
Выбор разрешающего столбца
(переменной, вводимой в базис).
Алгоритм симплекс-метода. ШАГ

Слайд 10Необходимо проверить элементы разрешающего столбца. Если среди них нет положительных,

то задача неразрешима.

Алгоритм симплекс-метода. ШАГ 6
Проверка условия: все air ≤ 0.

Слайд 11где s - номер разрешающей строки,
r - номер разрешающего столбца,
a’sj ,

b’s - новые значения пересчитываемых элементов,
asj , bs - старые значения пересчитываемых элементов,
asr -

Слайд 12Алгоритм симплекс-метода. ШАГ 8
Пересчет элементов разрешающего столбца. Все они (кроме

разрешающего элемента) должны стать равными нулю:

Слайд 13Элементы, не принадлежащие разрешающим столбцу и строке, пересчитываются по так

называемому правилу прямоугольника: мысленно выделяется прямоугольник, в котором элемент, подлежащий пересчету

Слайд 14Алгоритм повторяем с шага 4 до тех пор, пока в

строке коэффициентов целевой функции есть неотрицательные элементы.
Решение находится в первом

Слайд 15

Обратная связь

Что такое TheSlide.ru?

Разделы презентаций

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

Содержание

Слайды и текст этой презентации

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

Слайд 2Авторы симплекс-методаСимплекс-метод был разработан и впервые применен для решения задач

в 1947 г. американским математиком Дж. ДанцигомДжорд Бернард Данциг (George

Слайд 3Авторы симплекс-методаДжордж Данциг будучи студентом университета, однажды опоздал на занятие

и принял написанные на доске уравнения за домашнее задание. Оно

Слайд 4Общие положенияГеометрический смысл симплексного метода состоит в последовательном переходе от

одной вершины многогранника ограничений к соседней, в которой целевая функция

Слайд 5Процесс применения симплексного метода предполагает реализацию трех основных элементов:1) способ

определения какого-либо первоначального допустимого базисного решения задачи;2) правило перехода к

Слайд 6Алгоритм симплекс-метода. ШАГ 1Формулировка ЗЛП (формирование целевой функции и системы

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

Слайд 7В ограничения задачи вводятся дополнительные переменныеАлгоритм симплекс-метода. ШАГ 2Приведение задачи

к канонической форме (перевод функциональных ограничений в систему уравнений).Все дополнительные

Слайд 8Алгоритм симплекс-метода. ШАГ 3Первое допустимое решение: (0, 0,…,0, b1, b2,

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

Слайд 9Разрешающий столбец выбирается в соответствии со следующим условием:Алгоритм симплекс-метода. ШАГ

4Выбор разрешающего столбца (переменной, вводимой в базис). Алгоритм симплекс-метода. ШАГ

Слайд 10Необходимо проверить элементы разрешающего столбца. Если среди них нет положительных,

то задача неразрешима.Алгоритм симплекс-метода. ШАГ 6Проверка условия: все air ≤ 0.

Слайд 11где s - номер разрешающей строки,r - номер разрешающего столбца,a’sj ,

b’s - новые значения пересчитываемых элементов,asj , bs - старые значения пересчитываемых элементов,asr -

Слайд 12Алгоритм симплекс-метода. ШАГ 8Пересчет элементов разрешающего столбца. Все они (кроме

разрешающего элемента) должны стать равными нулю:

Слайд 13Элементы, не принадлежащие разрешающим столбцу и строке, пересчитываются по так

называемому правилу прямоугольника: мысленно выделяется прямоугольник, в котором элемент, подлежащий пересчету

Слайд 14Алгоритм повторяем с шага 4 до тех пор, пока в

строке коэффициентов целевой функции есть неотрицательные элементы.Решение находится в первом

Слайд 15

Похожие презентации

Обратная связь

Что такое TheSlide.ru?

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

Слайд 2Авторы симплекс-метода
Симплекс-метод был разработан и впервые применен для решения задач

в 1947 г. американским математиком Дж. Данцигом

Джорд Бернард Данциг (George

Слайд 3Авторы симплекс-метода
Джордж Данциг будучи студентом университета, однажды опоздал на занятие

Слайд 4Общие положения
Геометрический смысл симплексного метода состоит в последовательном переходе от

Слайд 5Процесс применения симплексного метода предполагает реализацию трех основных элементов:
1) способ

определения какого-либо первоначального допустимого базисного решения задачи;
2) правило перехода к

Слайд 6Алгоритм симплекс-метода. ШАГ 1
Формулировка ЗЛП (формирование целевой функции и системы

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

Слайд 7В ограничения задачи вводятся дополнительные переменные
Алгоритм симплекс-метода. ШАГ 2
Приведение задачи

к канонической форме (перевод функциональных ограничений в систему уравнений).
Все дополнительные

Слайд 8Алгоритм симплекс-метода. ШАГ 3
Первое допустимое решение: (0, 0,…,0, b1, b2,

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

Слайд 9Разрешающий столбец выбирается в соответствии со следующим условием:

Алгоритм симплекс-метода. ШАГ

4
Выбор разрешающего столбца
(переменной, вводимой в базис).
Алгоритм симплекс-метода. ШАГ

то задача неразрешима.

Алгоритм симплекс-метода. ШАГ 6
Проверка условия: все air ≤ 0.

Слайд 11где s - номер разрешающей строки,
r - номер разрешающего столбца,
a’sj ,

b’s - новые значения пересчитываемых элементов,
asj , bs - старые значения пересчитываемых элементов,
asr -

Слайд 12Алгоритм симплекс-метода. ШАГ 8
Пересчет элементов разрешающего столбца. Все они (кроме

строке коэффициентов целевой функции есть неотрицательные элементы.
Решение находится в первом