Симплекс-метод - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Симплекс-метод. Доклад-сообщение содержит 15 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

Алгоритм симплекс-метода. ШАГ 8 Элементы, не принадлежащие разрешающим столбцу и строке, пересчитываются по так называемому правилу прямоугольника: мысленно выделяется прямоугольник, в котором элемент, подлежащий пересчету и разрешающий элемент образуют одну из диагоналей. Формулы будут иметь следующий вид:

Слайд 14

Описание слайда:

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