- •Лекции по математическому моделированию
- •Математическое моделирование. Математическая модель в задачах оптимизации. Элементарные математические модели
- •Элементарные математические модели
- •Примеры моделей, получаемых из фундаментальных законов природы
- •4. Движение шара, присоединенного к пружине
- •Вариационные принципы и математические модели
- •Общая схема принципа Гамильтона.
- •Третий способ получения модели системы «шарик – пружина».
- •3. Колебания маятника в поле сил тяжести
- •4. Заключение
- •Универсальность математических моделей
- •1. Жидкость в u – образном сосуде.
- •2. Колебательный электрический контур.
- •3. Малые колебания при взаимодействии двух биологических популяций.
- •4. Заключение.
- •Сохранение массы вещества
- •1. Поток частиц в трубе.
- •2. Основные предположения о гравитационном режиме течения грунтовых вод.
- •3. Баланс массы в элементе грунта.
- •4. Замыкание закона сохранения массы.
- •5. О некоторых свойствах уравнения Буссинеска.
- •6. Основные выводы.
- •Сохранение энергии
- •1. Предварительные сведения о процессах теплопередачи.
- •2. Вывод закона Фурье из молекулярно-кинетических представлений.
- •3. Уравнение баланса тепла.
- •4. Постановка типичных краевых условий для уравнения теплопроводности.
- •5. Об особенностях моделей теплопередачи.
- •Совместное применение нескольких фундаментальных законов
- •1. Предварительные понятия газовой динамики.
- •2. Уравнение неразрывности для сжимаемого газа.
- •3. Уравнения движения газа.
- •4. Уравнение энергии.
- •Фильтрация смеси нефти и воды в пористой среде
- •Математическая модель фильтрации
- •Модель переноса примеси при однокомпонентной фильтрации
- •Модель переноса примеси при многокомпонентной фильтрации
- •Математическое моделирование физических процессов
- •1. Изменение атмосферного давления с изменением расстояния от поверхности Земли.
- •2. Задача об остывании тела.
- •3. Падение тел у земной поверхности.
- •4. Режимы течения. Вязкость. Число Рейнольдса.
- •5. Формула Стокса.
- •6. Сила гидравлического сопротивления.
- •Математическое программирование. Понятие линейного программирования. Виды задач линейного программирования. Геометрическая интерпретация задач линейного программирования
- •1. Понятие математического программирования
- •2. Понятие линейного программирования. Виды задач линейного программирования
- •3. Геометрическая интерпретация задач линейного программирования
- •1. Понятие нелинейного программирования
- •2. Классификация методов нелинейного программирования
- •2.1. Задача нелинейного программирования при ограничениях – неравенствах
- •4. Геометрическая интерпретация задач нелинейного программирования
2. Понятие линейного программирования. Виды задач линейного программирования
Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина "математическое программирование". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина "линейное программирование" возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.
Термин "линейное программирование" возник в результате неточного перевода английского "linear programming". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом английского "linear programming" было бы не "линейное программирование", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термины линейное программирование, нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.
Итак, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности.
Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного представления реального мира.
Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.
Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.
Общая форма задачи имеет вид: найти при условиях
, ,
, ,
, ,
где
, , , ,
, , .
Здесь и далее нам удобнее считать и вектор - строками, а и - вектор - столбцами.
Наряду с общей формой широко используются также каноническая и стандартная формы. Как в канонической, так и в стандартной форме
т.е. все переменные в любом допустимом решении задачи должны принимать неотрицательные значения (такие переменные принято называть неотрицательные в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не накладывается). Отличие же между этими формами состоит в том, что в одном случае , а в другом .
Задача ЛП в канонической форме:
, (2.1)
, (2.2)
. (2.3)
Задача ЛП в стандартной форме:
,
,
.
В обоих случаях есть матрица размерности , строка которой совпадает с вектором .
Задача ЛП в общей форме сводится (в определенном смысле) к задаче ЛП в канонической (стандартной) форме. Под этим понимается существование общего способа построения по исходной задаче (в общей форме) новой задачи ЛП (в нужной нам форме), любое оптимальное решение которой "легко" преобразуется в оптимальное решение исходной задачи и наоборот. (Фактически, связь между этими задачами оказывается еще более тесной). Тем самым, имеется возможность, не теряя общности, заниматься изучением задач ЛП, представленных либо в канонической, либо в стандартной форме.