Понятие математического программирования

Содержание

Введение
1. Понятие математического программирования.
2. Понятие линейного программирования. Виды задач.
3. Постановка задачи ЛП и исследование их структуры.
4. Решение задач ЛП симплекс - методом.
4.1. Метод полного исключения.
4.2. Табличный симплекс - метод.
4.3. Геометрическая интерпретация задач ЛП.
5. Моделирование работы механического цеха.
5.1. Построение математической модели.
5.2. Максимизация целевой функции F.
6. Решение задачи ЛП средствами MS Excel.
Заключение
Список использованной литературы

Введение

Практика свидетельствует: самое лучшее средство для определения свойств объекта - натурный эксперимент, т. е. исследование свойств и поведения самого объекта в нужных условиях. Дело в том, что при проектировании невозможно учесть многие факторы, расчет ведется по усредненным справочным данным, используются новые, недостаточно проверенные элементы (прогресс нетерпелив! ), меняются условия внешней среды и многое другое. Поэтому натурный эксперимент - необходимое звено исследования. Неточность расчетов компенсируется увеличением объема натурных экспериментов, созданием ряда опытных образцов и " доводкой" изделия до нужного состояния. Так поступали и поступают при создании, например, телевизора или радиостанции нового образца.

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

Например, наиболее полную оценку новому виду вооружения и способам его применения может дать война. Но не будет ли это слишком поздно?

Натурный эксперимент с новой конструкцией самолета может вызвать гибель экипажа.

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

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

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

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

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

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

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

Моделирование, в-третьих, это перенос полученных на модели сведений на оригинал или, иначе, приписывание свойств модели оригиналу. Чтобы такой перенос был оправдан, между моделью и оригиналом должно быть сходство, подобие.

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

Остановимся на основных целях моделирования.

Прогноз - оценка поведения системы при некотором сочетании ее управляемых и неуправляемых параметров. Прогноз - главная цель моделирования.

Объяснение и лучшее понимание объектов. Здесь чаще других встречаются задачи оптимизации и анализа чувствительности. Оптимизация - это точное определение такого сочетания факторов и их величин, при котором обеспечиваются наилучший показатель качества системы, наилучшее по какому-либо критерию достижение цели моделируемой системой. Анализ чувствительности - выявление из большого числа факторов тех, которые в наибольшей степени влияют на функционирование моделируемой системы. Исходными данными при этом являются результаты экспериментов с моделью.

Часто модель создается для применения в качестве средства обучения: модели-тренажеры, стенды, учения, деловые игры и т. п.

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

Гениальный полководец А. В. Суворов перед атакой крепости Измаил тренировал солдат на модели измаильской крепостной стены, построенной специально в тылу.

Метод полного исключения

Рассмотренный выше алгоритм симплекс-метода неудобен для программирования и решения задач на ЭВМ. Потребовалась его рационализация как по форме представления информации, так и в способе организации вычислений, чтобы сделать его пригодным для реализации на ЭВМ. С этой целью был разработан табличный вариант симплекс-метода. В его основе лежит метод полного исключения Жордана - Гаусса.

Пусть задана система линейных алгебраических уравнений

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

Ax=A₀.

Матрица A_p=[A, A₀] называется расширенной матрицей. Метод полного исключения Жордана - Гаусса состоит из конечного числа однотипных итераций и заключается в сведении матрицы к единичному виду. Метод основывается на двух операциях:

1. одну из строк расширенной матрицы умножают на множитель, отличный от нуля;

2. из каждой строки расширенной матрицы вычитают одну строку, умноженную на некоторое число.

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

Первая итерация метода полного исключения.

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

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

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

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

Если после k -й итерации главная часть матрицы A_p^{(k)} не содержит ни одного элемента или содержит только нули, то процесс заканчивается.

Пусть процесс оборвался после итерации 1. Предположим вначале, что среди строк матрицы A^(l) есть такие, которые не были направляющими ни в одной из предыдущих итераций, например, строка с номером i. Тогда очевидно,

a_ij=0; j = 1, 2, ., n.

Поскольку для любой строки справедливо

( 1.1)

то уравнение для i -й строки имеет вид

( 1.2)

Если , то уравнение (1.2) противоречиво, и данная система уравнений неразрешима.

Если , то уравнение (1.2) представляет собой тождество и i -я строка может быть отброшена.

Перебрав одну за другой все строки матрицы A^(l), которые не являлись направляющими, либо устанавливают неразрешимость системы уравнений, либо отбрасывают все нулевые строки.

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

( 1.3)

Пусть i -й направляющей строке соответствует i -й направляющий столбец вследствие соответствующего выбора направляющего элемента. Тогда

( 1.4)

Следовательно, (1.3) можно записать в виде:

( 1.5)

причем переменные x_i (i=1, ., l) являются базисными, а переменные x_j (j=l+1, ., n) - небазисными.

При x_j = 0 (j=l+1, ., n) получим одно из базисных решений системы уравнений .

Задавая для x_j произвольные значения , получим полное множество решений.

Если x_i - i -я компонента этого решения, то

( 1.6)

Обозначим

Тогда общее (полное) решение системы линейных уравнений определяется соотношением, аналогичным (1.6):

( 1.7)

где x₀ - базисное решение начальной системы уравнений; - полное решение соответствующей однородной системы уравнений (то есть при A₀=0 ).

Обозначим расширенную матрицу системы уравнений после k -й итерации через

Пусть - направляющий элемент преобразования на (k+1) -й итерации. Тогда в результате (k+1) -й итерации метода полного исключения Гаусса получим матрицу , элементы которой определяются следующими соотношениями:

1. для всех элементов направляющей строки

( 1.8)

2. для элементов направляющего столбца

( 1.9)

3. для всех остальных элементов матрицы

( 1.10)

Табличный симплекс - метод

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

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

A₁x₁+...+A_nx_n+e₁x_n+e₁x_n+1+...+e_mx_n+m=A₀=[a_i0],

где

для всех i = 1, 2,., n.

Применим одну итерацию метода полного исключения к расширенной матрице ограничений A_p=[A₁, ..., A_n, e₁, ..., e_m, A₀].

Пусть a_ij - направляющий элемент преобразования на данной итерации. Тогда в результате преобразований в соответствии с (1.10) получим новые значения свободных членов:

( 2.1)

Исследуем выражения (2.1) и выясним условия, при которых для всех l, то есть новое базисное решение будет также допустимым.

По предположению , тогда

Если , тогда , поскольку .

Если , то

будет больше нуля при всех l=1, 2, ..., m тогда и только тогда, когда

( 2.2)

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

a) направляющий столбец j выбирают из условия, что в нем имеется хотя бы один положительный элемент;

б) направляющую строку i выбирают так, чтобы отношение было минимально при условии, что a_ij> 0.

При таком преобразовании в базис вводится вектор A_j и выводится вектор А_i. Теперь надо определить, как выбрать вектор, вводимый в базис, чтобы при этом значение целевой функции увеличилось.

Для этого используют так называемые оценки векторов :

( 2.3)

где - множество индексов базисных векторов; x_ij - определяют из условия

( 2.4)

Величины равны симплекс-разницам для переменных {x_j} с противоположным знаком. Следовательно, для того чтобы значение целевой функции увеличилось, необходимо выбрать направляющий столбец А_j с наибольшей по модулю отрицательной оценкой, то есть

Для решения задачи симплекс-методом на каждой итерации заполняют симплекс-таблицу 2.1.

Таблица 2.1.
c			c₁	c₂	c₃	.	c_j	.	c_n
	B_x	a₀₀	A₁	A₂	A₃	.		.	A_n
c₁	x₁	a₁₀	a₁₁	a₁₂	a₁₃	.	a_1j	.	a_1n
c₂	x₂	a₂₀	a₂₁	a₂₂	a₂₃	.	a_2j	.	a_2n
.	.	.	.	.	.	.	.	.	.
	x_i	a_i0	a_i1	a_i2	a_i3	.	a_ij	.	a_in
.	.	.	.	.	.	.	.	.	.
c_m	x_m	a_m0	a_m1	a_m2	a_m3	.	a_mj	.	a_mn
						.		.

Последняя строка таблицы - индексная - служит для определения направляющего столбца. Ее элементы определяют по формуле (2.3). Очевидно, для всех базисных векторов {A_i} i=1,., m оценки .

Значение целевой функции a₀₀ определяется из соотношения

В столбце B_x записываем базисные переменные {x_i} i= 1, ..., m. Их значения определяются столбиком свободных членов a_i0, то есть

X_i=a_i0, i=1, 2,., m.

Направляющие строка A_i и столбец A_j указываются стрелками. Если в качестве направляющего элемента выбран a_ij, то переход от данной симплекс-таблицы к следующей определяется соотношениями (1.8) - (1.10).

Итак, алгоритм решения задачи ЛП табличным симплекс-методом состоит из этапов.

1. Рассчитывают и заполняют начальную симплекс-таблицу с допустимым единичным базисом, включая индексную строку.

2. В качестве направляющего столбца выбирают A_j, для которого

3. Направляющая строка A_і выбирают из условия

4. Делают один шаг (итерацию) метода полного исключения Гаусса с направляющим элементом a_ij, для чего используют соотношения (1.8) - (1.10). В частности, элементы индексной строки новой таблицы вычисляют в соответствии с формулой

Правильность вычислений контролируют по формулам непосредственного счета:

	(2.5)
	( 2.5)

В столбце B_x новой таблицы заменяют x_i на x_j, а в столбце С c_i на c_j.

5. Если все , то новое базисное решение - оптимально. В противном случае переходят к этапу 2 и выполняют очередную итерацию.

6. Второй, третий и четвертый этапы повторяют до тех пор, пока одна из итераций не закончится одним из двух исходов:

а) все . Это признак (критерий) оптимальности базисного решения последней симплекс-таблицы;

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

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

Если в качестве начального базиса выбирают базис из свободных переменных, для которых c_i=0, то оценки для всех небазисных переменных равны , а соответствующее значение целевой функции

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

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

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

Заключение

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

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

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

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

Список использованной литературы

1) Моделирование систем: учебно-метод. Комплекс / А. И. Васильев; Дальневосточный государственный технический университет. – Владивосток: Изд-во ДВГТУ, 2008. - 172с.

2) Моделирование систем. Практикум: Учеб. пособие для вузов / Б. Я. Советов, С. А. Яковлев. – 3-е изд., стер. – М.: Высш. шк., 2005. – 295 с.: ил.

3) Ильин В.В «Моделирование бизнес-процессов», 2006

4) Функциональная модель TO BE: http: //www.itstan.ru/funk-strukt-analiz/funkcionalnaja-model-to-be.html

5) Емельянов А.А., Власов Е.А., Дума Р.В. Имитационное моделирование экономических процессов: Учеб. пособие. Под ред. А.А.Емельянова. – М.: Финансы и статистика, 2004. –368 с.: ил.

6) Самарский А.А., Михайлов А.П. Математическое моделирование: Идеи. Методы. Примеры. 2 изд., испр. – М.: Физматлит, 2001. –320.

7) Антонов А.В. Системный анализ. учебник для вузов. – М.: Высшая школа, 2004. - 454 с.: ил. (главы 4, 11).

8) Цисарь И.Ф., Нейман В.Г. Компьютерное моделирование экономики. – М.: «Диалог-МИФИ», 2002.- 304 с.

9) Кудрявцев Е.М., Добровольский А.В. Основы работы с универсальной системой моделирования GPSS World / Учебное пособие. – Издательство Ассоциации строительных вузов, 2005. – 256 с.

Содержание

Введение
1. Понятие математического программирования.
2. Понятие линейного программирования. Виды задач.
3. Постановка задачи ЛП и исследование их структуры.
4. Решение задач ЛП симплекс - методом.
4.1. Метод полного исключения.
4.2. Табличный симплекс - метод.
4.3. Геометрическая интерпретация задач ЛП.
5. Моделирование работы механического цеха.
5.1. Построение математической модели.
5.2. Максимизация целевой функции F.
6. Решение задачи ЛП средствами MS Excel.
Заключение
Список использованной литературы

Введение

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

Натурный эксперимент с новой конструкцией самолета может вызвать гибель экипажа.

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

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

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

Остановимся на основных целях моделирования.

Понятие математического программирования

Математическое программирование занимается исследованием детерминированных и одноцелевых задач. Слово " программирование" в данном случае означает " планирование". К математическому программированию относится:

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

2. Нелинейное программирование: целевая функция и ограничения могут быть нелинейными функциями.

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

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

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

Математическая модель любой задачи линейного программирования включает в себя:

· набор констант, характеризующих, например, наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы;

· искомые переменные величины, например, количество запланированной к выпуску продукции по всему ассортименту;

· максимум или минимум целевой функции, например, запланированной прибыли;

· систему ограничений в форме линейных уравнений и неравенств, например, условие того, что расход материала не должен превышать его запас;

· требование не отрицательности переменных (если не предусмотрено иное).

Решение практической задачи всегда связано с исследованием, с преобразованием некоторого объекта (материального или информационного) или с управлением им (рисунок 1.1).

Рис. 1.1. Схема моделирования объекта (процесса)

При решении " стандартной" задачи в линейном программировании нужно определить максимум линейной целевой функции

при условиях

Здесь целевая функция формируется как скалярное произведение двух векторов. Один из них — вектор искомых переменных . Компонентами другого вектора являются целевые коэффициенты . Условия задачи можно сформулировать так: " Расход не должен превышать имеющиеся ресурсы ". Вектор расхода есть сумма произведений матрицы нормированных коэффициентов на вектор искомых переменных .

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

12 3 4 5 Следующая ⇒