- •Министерство образования и науки российской федерации
- •Дифференциальные уравнения первого порядка
- •Уравнения с разделёнными и разделяющимися переменными
- •Однородные уравнения первого порядка
- •Линейные уравнения первого порядка
- •Уравнение в полных дифференциалах
- •Интегрирующий множитель
- •Дифференциальные уравнения высших порядков
- •Уравнения вида
- •Уравнения второго порядка, приводящиеся к уравнениям первого порядка
- •Линейные однородные уравнения. Определения и общие свойства
- •Линейные однородные уравнения второго порядка с постоянными коэффициентами
- •Линейные однородные уравнения го порядка с постоянными коэффициентами
- •Неоднородные линейные уравнения второго порядка
- •Неоднородные линейные уравнения второго порядка с постоянными коэффициентами
- •Неоднородные линейные уравнения высших порядков
- •Системы обыкновенных дифференциальных уравнений
- •Системы линейных дифференциальных уравнений с постоянными коэффициентами
- •Р я д ы Числовые ряды Числовой ряд. Сумма ряда. Необходимый признак сходимости ряда
- •Достаточные признаки сходимости рядов с положительными членами
- •Знакопеременные ряды
- •Функциональные ряды
- •Ряды Тейлора и Маклорена
- •Ряды Фурье
- •Ряды Фурье для четных и нечетных функций
- •Ряд Фурье для функции с периодом
- •К о м б и н а т о р и к а
- •Общие правила комбинаторики
- •Соединения в комбинаторике
- •Размещения без повторений
- •Перестановки без повторений
- •Сочетания без повторений
- •Размещения с повторениями
- •11 12 13 14 15 16 17 19
- •Перестановки с повторениями
- •Т е о р и я в е р о я т н о с т е й Случайные события Основные понятия теории вероятностей
- •Основные теоремы теории вероятностей Теорема сложения вероятностей несовместных событий
- •Зависимые и независимые события. Условная вероятность
- •Теорема умножения вероятностей
- •Теорема сложения вероятностей совместных событий
- •Вероятность появления хотя бы одного события
- •. Формула полной вероятности
- •Формула Бейеса
- •Повторение испытаний
- •Формула Бернулли
- •Локальная теорема Лапласа
- •. Формула Пуассона
- •Интегральная теорема Лапласа
- •Случайные величины Случайная величина. Виды случайных величин
- •Закон распределения вероятностей дискретной случайной величины
- •Числовые характеристики дискретных случайных величин
- •Математическое ожидание дискретной случайной величины
- •Дисперсия дискретной случайной величины
- •Плотность распределения вероятностей непрерывной случайной величины
- •Числовые характеристики непрерывных случайных величин
- •Законы распределений
- •Равномерное распределение
- •Нормальное распределение
- •. Правило трёх сигм
- •Показательное распределение
- •Функция надёжности
- •Элементы математической статистики Основные сведения из математической статистики
- •Статистическое распределение выборки. Полигон и гистограмма
- •1 4 6
- •10 15 25
- •Статистические оценки параметров распределения
- •Оценка генеральной дисперсии по исправленной выборочной
- •Точность оценки, доверительная вероятность (надёжность). Доверительный интервал
- •Методы расчёта сводных характеристик выборки
- •Сведение первоначальных вариант к равноотстоящим
- •Оценка отклонения теоретического и эмпирического распределений от нормального. Асимметрия и эксцесс
- •Элементы теории корреляции
- •. (1)
- •(4) . (5) Корреляционная таблица
- •Отыскание параметров выборочного уравнения прямой линии регрессии по сгруппированным данным
- •Методика вычисления выборочного коэффициента корреляции
- •. Статистическая проверка статистических гипотез
- •Линейное программирование Задача линейного программирования
- •Построение математической модели
- •Графическое решение задачи линейного программирования
- •Симплексный метод решения задачи линейного программирования
- •Решение задачи 1 симплексным методом
- •Искусственное начальное решение. Метод больших штрафов.
- •Особые случаи применения симплекс-метода
- •1.7.2 Бесконечное множество решений
- •1.7.4 Неограниченные решения
- •1.7.5 Промежуточное вырожденное решение
- •Задача о назначениях
- •4 Изменение запаса ресурса продукта а 7
- •1 Изменение единицы стоимости продукта а 4
- •Заключение
Симплексный метод решения задачи линейного программирования
Пусть имеется ЗЛП, записанная в стандартной форме:
max , (1)
(2)
Обозначим через ивекторы-столбцы:
, и через- вектор-строку.
Тогда условия (1) и (2) можно записать в виде
max ,или max ,
Прежде чем приступить к обоснованию симплексного метода, множество всех векторов , удовлетворяющих условию , обозначим через и введем несколько определений:
Определение 1. Линейная функция, определенная на выпуклом многограннике К, достигает своего оптимального значения в крайней точке этого многогранника.
Определение 2. Допустимая точка называется базисной или опорной (опорным планом), если она соответствует крайней точке многогранника решений;
Определение 3. Допустимая точка называется вырожденной, если менее чем значенийотличны от нуля (- число ограничений в задаче);
Определение 4. Если X – крайняя точка многогранника К, то не более её координатотличны от нуля, и векторы, коэффициентыпри которых отличны от нуля, линейно независимы.
Пусть - крайняя точка многогранника решений, определяемого равенством, причем координатточкиотличны от нуля, т.е.
- невырожденный опорный план задачи.
Согласно определению 4, векторы линейно независимы и образуют базис-мерного пространства. Функция целив точкепринимает значение
и равенство объединяется в равенство (3)
Найдём опорный план , которому соответствует значениефункции цели. Поскольку векторыобразуют базис, то любой векторможет быть представлен в виде линейной комбинации этих векторов. Выберем вектори, умножив его на число, прибавим к левой части равенства (3), а затем вычтем из неё, в результате получим
(4)
Так как , то получим.
Таким образом, если выбрать точку с координатами
то она будет удовлетворять условию и, если при этом все координаты точкибудут неотрицательны, т.е.(5) , тобудет допустимой точкой задачи. Условие (5) выполняется, если выбрать, (6)
где берётся min только положительных отношенийи. В случае, когда все, величинуможно выбрать как угодно большой. Это свидетельствует о неограниченности многогранника решений. Пусть выбрано, удовлетворяющее условию (6); тогда имеем в предположении, что:. Координаты второй точки будут:
При выборе в соответствии с (6) обращается в нуль лишь одна координата, поэтому новое решение, как и старое, содержитположительных координат. Таким образом точкаявляется опорным планом задачи и переход от планак планусоответствует переходу от одной крайней точки многогранника решений к другой.
Выясним, как следует выбирать вектор , чтобы при переходе от одной крайней точки к другой линейная функцияпо крайней мере не убывала.
Точке соответствует значение функции цели, равное
Преобразовав это выражение для , получим, где. Очевидно, если.
Решение задачи 1 симплексным методом
max Стандартная формаmax
Ба- зис |
сz |
bi |
|
|
|
|
|
|
θ |
Замечания |
|
|
|
|
|
| |||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
| |
Результи- рующая строка |
zопт |
|
|
|
|
|
|
| ||
| ||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
| |
Результи- рующая строка |
zопт |
|
|
|
|
|
|
| ||
| ||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
| |
Результи- рующая строка |
zопт |
|
|
|
|
|
|
| ||
|
Презентация решения задачи 1 симплексным методом