Основы математического программирования (стр. 1 )

Оглавление

Раздел 1. Основы математического программирования. 2

1.1. Введение в математическое программирование. 2

1.2. Классификация математических методов и моделей. 4

1.3. Элементы теории принятия решений. 4

Раздел 2. Линейное программирование. 4

2.1. Метод Жордана-Гаусса. 4

2.2. Практическое занятие. Метод Жордановых исключений. 4

2.4. Постановка основной задачи линейного программирования. 4

2.5. Понятие и назначение симплекс-метода. 4

2.8. Понятие графического метода. Особые случаи графического метода. 4

2.9. Двойственность в линейном программировании. 4

2.10. Понятие целочисленности в линейном программировании. 4

2.11. Постановка транспортной задачи. 4

Раздел 1. Основы математического программирования

1.1. Введение в математическое программирование

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

Математические знания и навыки нужны практически во всех профессиях, прежде всего, конечно, в тех, которые связаны с естественными науками и экономикой.

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

Математические методы и модели, которые мы будем рассматривать на занятиях, хорошо известны и используются в различных контекстах - математические методы в принятии решений, методы исследования операций, методы оптимального управления и пр.

____________________________________________________________

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

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

Математическое программирование (оптимальное программирование) – область прикладной математики, объединяющая различные математические методы - линейное программирование, нелинейное программирование, динамическое программирование, выпуклое программирование и др.

Математическое программирование – это раздел высшей математики, посвященный решению задач, связанных с нахождением экстремумов функций нескольких переменных при наличии ограничений на эти переменные.

Методами математического программирования решаются задачи распределения ресурсов, планирование выпуска продукции, ценообразования, транспортные задачи и т. п.

Математическое программирование возникло в 30-е годы ХХ века. Венгерский математик Б. Эгервари в 1931 году решил задачу, называемую проблемой выбора. Американский ученый обобщил этот метод, после чего он стал называться «венгерским методом».

В 1947 году американский ученый Дж. Данциг описал один из основных методов решения задач линейного программирования, получивший название «симплексный».

Построение математической модели процесса включает в себя следующие этапы:

1. выбор переменных задачи.

2. составление системы ограничений.

3. выбор целевой функции.

Переменными задачи называются величины х1, х2,…хn, которые полностью характеризуют процесс. Их обычно записывают в виде вектора Х=( х1, х2,…хn).

Система ограничений включает в себя систему уравнений и неравенств, которым удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других экономических или физических условий, например положительности переменных и т. п.

Целевой функцией называют функцию переменных задачи, которая характеризует качество выполнения задачи, и экстремум которой требуется найти.

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

В самом общем виде эта задача формулируется следующим образом: найти экстремум целевой функции

Z(Х) = f (х1, х2,…хn) →max (min) (1)

и соответствующие ему переменные при условии, что эти переменные удовлетворяют системе ограничений:

{

φi (х1, х2,…хn ) = 0, i =1, 2, …, l φi (х1, х2,…хn ) ≤(≥) 0, i =l+1, l+2, …, m

(2)

Если целевая функция (1) и система ограничений (2) линейны, то задача математического программирования называется задачей линейного программирования. Если нелинейны – нелинейного программирования. Если ставится дополнительное условие, чтобы переменные были целочисленны – задача целочисленного программирования и т. п.

Допустимым решением задачи математического программирования называется любой n-мерный вектор Х = (х1, х2,…хn ), удовлетворяющий системе ограничений.

Множество допустимых решений задачи образует область допустимых решений (ОДР).

Оптимальным решением задачи математического программирования называется такое допустимое решение задачи, при котором целевая функция достигает экстремума.

Рассмотрим типичную задачу математического программирования – задача и диете.

Имеется два продукта 1 – картофель и 2 – мясо; заданы два типа питательных веществ: 1 – белки и 2 – углеводы.

Необходимо составить диету, имеющую минимальную стоимость и обеспечивающую необходимую насыщенность питательными веществами.

Задача описывается следующими математическими объектами и связями между ними.

1. Матрица содержания питательных веществ в продуктах

A =

(

a11 a21 a21 a22

)

Здесь a11 - содержание белков в картофеле; a21 - содержание углеводов в картофеле;

a12 - содержание белков в мясе; a22 - содержание углеводов в мясе;

2. Вектор ограничений

В =

(

b1 b2

)

Здесь b1 - минимальное количество белков (например, в килограммах), которое должно содержаться в диете;

b2 - углеводов;

3. Вектор цен

С =

(

с1 с2

)

Здесь с1 - цена единицы (килограмма) картофеля; с2 - цена мяса.

4. Вектор плана (диета)

Х =

(

х1 х2

)

Здесь х1 - потребление картофеля; х2 - мяса.

Задача построения оптимальной диеты формулируется следующим образом:

Необходимо минимизировать стоимость диеты

Z = с1х1 +с2х2

При ограничениях:

{	a11x1 + a12x2 ≥ b1 a21x1 + a22x2 ≥ b2

Что означает потребление обоих питательных веществ выше необходимого минимума.

В данном примере на упрощенном уровне поставлена задача составления оптимального плана, который в силу исторических причин получило обобщенное название задачи математического программирования (что не имеет прямого отношения к программированию на ЭВМ, хотя такие задачи решаются только на ЭВМ), в связи с принятым в англоязычных странах термином «program», подразумевающим план.

Другие классические задачи математического программирования.

Задача о коммивояжере. Состоит в отыскании наилучшего маршрута для коммивояжера, который должен объехать все порученные ему города и вернуться назад в кратчайший срок или с наименьшими затратами на проезд. О сложности этой задачи говорит тот факт: если городов 4, то число возможных маршрутов - 6, а уже при 11 городах существует более 3,5 млн допустимых маршрутов. В общем случае, когда число городов n, количество маршрутов равно (n-1)!

Распределительные задачи. Класс экономико-математических задач, связанных с распределением ресурсов по работам, которые необходимо выполнить. Если ресурсов достаточно, чтобы каждую работу выполнить наиболее эффективно, задача не возникает. В обратом случае переброска ресурсов с одной работы на другую приводит к изменению общей эффективности. Поэтому распределительная задача заключается в отыскании наилучшего распределения ресурсов, при котором либо максимизируется общий доход, либо минимизируются затраты.

Задачи теории расписаний. Теорией расписаний называется совокупность моделей календарного планирования. Модели теории расписаний позволяют, например, решать такие задачи, как определение оптимальной последовательности обработки деталей на станках, планирование работы производственного участка, составление программы-диспетчера для управления работой ЭВМ в мультипрограммном режиме.

Управление запасами. Это комплекс методов, предназначенных для оптимизации запасов, т. е. ресурсов, находящихся на хранении. В качестве целевой функции выступают суммарные затраты на содержание запасов, на складские операции, потери от порчи при хранении, моральное старение и пр. Управляемыми переменными являются объем запасов, частота и сроки их пополнения и т. п.

Задачи массового обслуживания. Это класс задач, заключающихся в нахождении параметров систем массового обслуживания.

Важнейшими критериями качества систем массового обслуживания являются:

· вероятность обслуживания заявки или задержки в обслуживании;

· математическое ожидание числа удовлетворенных (задержанных) заявок за фиксированное время;

· математическое ожидание числа занятых каналов;

· математическое ожидание длины очереди.

Наиболее важным критерием оптимальности являются средние суммарные потери от ожидания требований, с одной стороны, и простоя каналов обслуживания – с другой.

Задача о размещении складов. Заключается в минимизации общей с3уммы транспортных и складских расходов при следующих ограничениях: с каждого завода должна быть отгружена вся продукция, емкость любого склада не должна быть переполнена, потребности всех покупателей должны быть удовлетворены.

Задачи о раскрое. Метод решения таких задач помогает с наименьшими отходами использовать листы металла, стекла, картона и др. материалов при раскрое их на заданное количество деталей различного размера. При правильной постановке задачи применение методов линейного программирования гарантирует сокращение отходов до минимально возможного. Часто на предприятиях отходы сокращаются в несколько раз.

Основные классы задач математического программирования.

Нелинейное программирование.

Раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты возрастают или убывают не пропорционально изменению масштабов использования ресурсов.

При этом возможны разные случаи: целевая функция нелинейна, а ограничения линейны; целевая функция линейна, а ограничения (хотя бы одно из них) – нелинейны, и целевая функция и ограничения нелинейны.

Нелинейные задачи сложны, часто их упрощают тем, что приводят к линейным. Для этого условно принимают, что на том или ином участке целевая функция возрастает или убывает линейно. Такой метод называется кусочно-линейных приближений.

Универсального метода для решения нелинейных задач нет, так как они чрезвычайно разнообразны.

Выпуклое программирование.

Выпуклым этот вид программирования называется потому, что имеет дело с выпуклыми функциями и выпуклыми системами ограничений.

Дискретное программирование.

Это раздел оптимального программирования, в котором на искомые переменные накладывается условие целочисленности, а область допустимых значений конечна

Значительное количество реальных задач носит дискретный характер. Прежде всего это связано с физической неделимостью многих факторов и объектов расчетов: например, нельзя построить 2/3 завода, или нанять ½ землекопа.

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

Квадратичное программирование.

Это раздел выпуклого программирования, в котором целевая функция представляет собой многочлен второй степени, а ограничения линейны.

Линейное программирование.

Линейное программирование – область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью

1.2. Классификация математических методов и моделей

Модель – это материальный или мысленно представленный объект, который в процессе исследования замещает объект-оригинал т. о., что его непосредственное изучение дает новые знания об объекте-оригинале.

Моделирование – это изучение объекта путем построения и исследования его модели.

Модель должна строиться так, чтобы она наиболее полно воспроизводила существенные качества объекта.

Модель должна быть удобной для изучения объекта и должна быть проще объекта.

Модели подразделяются на два типа:

1. Аналитические модели. Учитывают небольшое количество факторов, всегда требуют каких-либо упрощений и допущений. Результаты легко обозримы и хорошо отображают основные закономерности.

2. Статистические модели. Более подробные и точные модели, учитывают большое количество факторов. Недостатки – громоздкость, плохая обозримость, большой расход. На практике чаще сочетают аналитические и статистические методы

Понятие операции и оптимального решения.

Операция – мероприятия или система действий, объединенных единым замыслом и направленных на достижение какой-либо цели (строительство дома, создание предприятия).

Решение – это определенный набор параметров, зависящих от организаторов.

Оптимальное решение – решение, которое по тем или иным признакам предподчительнее других.

Параметры, совокупность которых образует решении, называются элементами решения.

Пример 1.

Имеется ряд магазинов, торгующих определенными товарами. Есть ряд товарных баз, которые могут поставить эти товары магазинам. Базы связаны с магазинами путями сообщения с определенными тарифами. Требуется обеспечить такой план маршрутов, чтобы потребности магазинов были обеспечены.

В качестве целевой функции выбираем стоимость перевозок.

В качестве допущений предполагаем, что все товары одинакового типа имеют одинаковую стоимость и одинаковое качество.

В данной задаче:

А1, А2,…, Am – пункты отправлении (базы).

В1, В2,…, Bn – магазины.

Количество продуктов, перевезенных из i-базы, в j – магазин – Хij.

Разновидности задач моделирования и подходов к их решении.

Задачи математического моделирования

Прямые Обратные

С детерминированными данными

Одноцелевые

Многоцелевые

Данные – случайные величины

Прямые задачи отвечают на вопрос, что будет если при заданных условиях мы выберем определеннее решение из множества допустимыx. Для выбранного решения рассчитываются показатели эффективности или целевая функция.

Обратные задачи отвечают на вопрос: как выбрать оптимальное решение из множества допустимых решений. Целевая функция (показатель эффективности) должна стремиться к min или max.

Если число допустимых вариантов решений невелико, то можно вычислить показатель эффективности для каждого варианта и выбрать оптимальный вариант по вычисленным значениям целевой функции. Такой способ нахождения оптимального решения называется простым перебором.

Если число допустимых вариантов велико, то поиск решения невозможен простым перебором. В этих случаях применяются методы направленного перебора. Оптимальное решение находится путем последовательных приближений, из которых каждое приближает нас к искомому оптимальному.

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

Одноцелевые задачи – задачи, в которых выбран один показатель эффективности.

Построим таблицу, позволяющую классифицировать математические методы и модели.

Основание классификации	Классы методов и моделей
Цели моделирования	Описание процессов и систем	Оценка системы	Оптимизация системы
Принцип построения модели	Кибернетическая	Статисти-ческая
Применяемые критерии оценки и оптимизации	Векторные	Скалярные
Условия принятия решений	Определенность	Риск	Конфликт	Неопределенность
Уровни (функции) управления	Целеобразование (целеполагание)	Организация	Планирование	Контроль
Управление системой	Централизованное (организация)	Децентрали-зованное (экономика)
Фактор времени	Статические модели	Динамичес-кие модели
Степень абстрактности моделей	Аналитические	Вычисли-тельные	Имитационные
Вид используемых функций	Линейные	Квадратич-ные	Степенные	Показательные
Дискретность	Непрерывные модели	Дискретные модели
Учет вероятностных факторов	Детерминирован-ные	Вероятност-ные (стохасти-ческие)

Классификация по целям моделирования.

Модели описания.

Это разомкнутые модели, предполагающие построение описания объекта или процесса Р, содержащего функциональные или алгоритмические связи между входами (m, u) и выходами Y.

Входами являются внешние воздействия на объект (управляемые и неуправляемые), выходами – реакция объекта (процесса).

m P(m, u) y