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

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

Содержание ▲

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

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

Слайд 1

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

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ

Слайд 2

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

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

Слайд 3

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

Слайд 4

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

Множество всех планов задачи линейного программирования выпукло. Множество всех планов задачи линейного программирования выпукло. Не существует локального экстремума, отличного от глобального. Другими словами, если максимум (минимум) есть, то он единственный. Целевая функция ЗЛП достигает своего максимального (минимального) значения в угловой точке многогранника решений (в его вершине). Каждой угловой точке многогранника решений отвечает опорный план ЗЛП.

Слайд 5

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

называется метод последовательного улучшения плана. называется метод последовательного улучшения плана. Название метода возникло от слова «симплекс», что значит «простейший» (т.е. простейший многогранник в Rn, имеющий п+1 вершину).

Слайд 6

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

Слайд 7

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

найти вначале любую угловую точку многогранника решений, т.е. найти x0 опорное решение системы ограничений (1) и вычислить в ней значение целевой функции L(x0), а затем перейти в новую точку x1, но не в любую, а в такую, где L(x1)> L(x0). найти вначале любую угловую точку многогранника решений, т.е. найти x0 опорное решение системы ограничений (1) и вычислить в ней значение целевой функции L(x0), а затем перейти в новую точку x1, но не в любую, а в такую, где L(x1)> L(x0). 3aтем улучшать это решение, пока не попадем в точку xопт , т.е. в точку, где L(xопт)> L(x1). Хотя угловых точек может оказаться много, но симплексный метод освобождает от громоздкой работы их перебора и быстро приводит к цели.

Слайд 8

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

Пусть известно первое опорное решение системы ограничений, в ней выделены базисные неизвестные x1, x2, …, xm , а свободные члены неотрицательны, тогда система (1) имеет вид Пусть известно первое опорное решение системы ограничений, в ней выделены базисные неизвестные x1, x2, …, xm , а свободные члены неотрицательны, тогда система (1) имеет вид

Слайд 9

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

Слайд 10

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

Слайд 11

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

Слайд 12

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

Если все ∆j > 0, то L увеличить нельзя, найдено оптимальное решение xопт. Если все ∆j > 0, то L увеличить нельзя, найдено оптимальное решение xопт. Если существует ∆j < 0, то найденное решение можно улучшить, введя в базис xj . Заметим, что при переходе в новую угловую точку L изменяется на величину L0 - ∆jxj, а поэтому чем больше |∆j|, тем сильнее увеличится L, тем быстрее мы продвигаемся к max. Значит надо выбирать наибольшую по модулю отрицательную оценку.

Слайд 13

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

Слайд 14

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

Предположим, что все aij < 0, Тогда из (5) следует x1>0, x2>0, …, xm>0, т.е. ни одна из координат не обратится в 0 (из базисных не выйдет). Значит к базисным векторам a1, a2, …, am добавился ещё один вектор, но m+1 векторов линейно зависимы, если ранг системы =m, поэтому новое решение не является опорным.

Слайд 15

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

Слайд 16

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

Если для найденного опорного решения найдется хотя бы одна отрицательная оценка ∆j < 0, причем вектор aj имеет хотя бы одну положительную координату aij > 0, то решение можно улучшить. Для этого ввести в базис xj, и вывести вектор, определяемый условием Если для найденного опорного решения найдется хотя бы одна отрицательная оценка ∆j < 0, причем вектор aj имеет хотя бы одну положительную координату aij > 0, то решение можно улучшить. Для этого ввести в базис xj, и вывести вектор, определяемый условием Если существует ∆j < 0, но aij < 0, где (i = 1, 2, ..., n.), то максимум целевой функции недостижим в области допустимых решений. Если любая оценка ∆j ≥ 0 (j = 1, 2, ..., п), то опорное решение оптимально.

Слайд 17

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

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ

Слайд 18

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

Целевая функция направлена на максимум: Целевая функция направлена на максимум: (2)

Слайд 19

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

Слайд 20

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

Таблица 1. Таблица 1.

Слайд 21

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

В первом столбце таблицы (Cб) - коэффициенты целевой функции при базисных переменных. В первом столбце таблицы (Cб) - коэффициенты целевой функции при базисных переменных. Во втором столбце (Хб) - базисные переменные, соответствующие единичным векторам системы ограничений (7). В третьем столбце (bi) - свободные члены системы (7). В первой строке - коэффициенты целевой функции при соответствующих переменных. Далее т строк занимает матрица коэффициентов системы (7).