🗊Презентация Симплексный метод

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

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

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

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

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

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

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

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

Если для найденного опорного решения найдется хотя бы одна отрицательная оценка ∆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, ..., п), то опорное решение оптимально.

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

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

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

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

Таблица 2. Таблица 2.

Таблица 4. Таблица 4.