Рекомендуемая литература.

1. Х. Таха «Введение в исследование операций». – М.: Мир, 1985. Т.1,2.

2. М.С. Красс, Б.П. Чупрынов «Основы математики и ее приложения в экономическом образовании». – М.: Изд. Дело, 2001.

3. О.М. Кудряшова «Нахождение оптимального решения прямой и двойственной задач ЛП и проведение анализа мат. моделей на чувствительность», метод. указания к курсовой работе.

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

Чтобы составить математическую модель задачи необходимо:

• Определить переменные данной задачи;

• Определить ограничения, которые накладываются на переменные по условию задачи;

• Определить цель, то есть целевую функцию задачи.

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

Исходные данные	Переменные	Зависимости	Задача	Обозначения
Детерминированные	Непрерывные Целочисленные Непрер.,целочисл.	Линейные Линейные Нелинейные	Лин. прогр-я. Целоч.прогр-я Нелин. прогр-я	ЛП ЦЧП НЛП
Случайные	Непрерывные	Линейные	Стохастич.прогр-я	СТП

Исходные данные, которые заданы определенными постоянными величинами, называются детерминированными. Исходные данные, как например, имеющиеся ресурсы, производительность оборудования и другие, которые зависят от ряда случайных факторов (своевременности поставки ресурсов, исправности оборудования и т.д.), называются случайными величинами. Переменные могут быть непрерывными и дискретными. Непрерывными называются такие величины, которые в заданном интервале могут принимать любые значения, т.е. такие величины являются результатами измерений: масса добываемого угля, объем выпуска ткани и т.д. Дискретными или целочисленными называются такие величины, которые могут принимать только целые значения, т.е. такие величины являются результатом счета: количество машин, людей, зданий – нет смысла говорить о 0,3 паровоза и т.д. Зависимости между переменными в целевой функции и в ограничениях могут быть линейными и нелинейными. Сочетание различных элементов модели приводит к различным классам задач оптимизации. Различные классы задач требуют разных методов решения и как следствие разных программных средств. Наиболее распространенными задачами оптимизации, возникающими в экономике, планировании, управлении, являются задачи ЛП. Задачи оптимизации, которые требуют решения в технических системах, как правило, являются нелинейными.

Раздел: Линейное программирование Построение математических моделей

Линейное программирование (ЛП) – это наука о методах исследования и нахождения экстремальных значений линейной функции, на неизвестные которой наложены линейные ограничения. Эта линейная функция называется целевой. Ограничения, записанные с помощью неравенств – системой ограничений. Направление оптимизации целевой функции (max или min ) называется критерием оптимальности.

В общем виде математическая модель задачи ЛП может быть записана:

max Z = C₁X₁ + C₂X₂ + … + C_nX_n

(min)

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

{	a11x1 + a12x2 + … + x1nxn ≤ b1 a21x1 + a22x2 + … + x2nxn ≤ b2
	… am1x1 + am2x2 + … + xmnxn ≤ bm

x₁ , x ₂ , … , x_n ≥ 0

_n

либо max Z = Σ c_j x_j

(min) ^j=1 n ____ ____

при ограничениях Σ а_ij х_j ≤b_i ; х_j ≥0 (i = 1,m ; j=1 , n)

j=1

Допустимым решением (планом) задачи ЛП можно считать вектор х =(х₁, х₂, …, х_n), удовлетворяющий системе ограничений. Множество допустимых решений образуют область допустимых решений.

Допустимое решение, при котором целевая функция достигает своего экстремального значения (max или min), называется оптимальным. Существует два способа решения задач ЛП. Графический способ (используется если модель содержит только две переменные):

• Построить прямые соответствующие системе ограничений;

• Отметить ОДР, удовлетворяющую всем ограничениям системы;

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

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

Пример: Фабрика выпускает два вида красок: для наружных работ и для внутренних работ. Для производства красок используется два исходных продукта А и В.

Исходный продукт	Расход исходного продукта (т)		Максимально возможный запас (т)
	Краска 1	Краска 2
А	1	2	6
В	2	1	8

Суточный спрос на краску 2 никогда не превышает спроса на краску 1 более чем на одну тонну. Спрос на краску 2 никогда не превышает двух тонн в сутки.

Оптовые цены на краску 1 – 3 тыс. ден. ед., на краску 2 – 2 тыс. ден. ед.

Какое количество краски должна производить фирма, чтобы доход был максимальным? Для построения мат. модели обозначим:

1. х₁ – суточный объем производства краски 1 (т)

х₂ – суточный объем производства краски 2 (т).

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

{	х1 + 2 х2 ≤ 6 2х1 + х2 ≤ 8 ; х1, х2 ≥ 0
	Х2 – х1 ≤ 1 х2 ≤ 2

3. Суточный доход от продажи краски 1 вида составит 3 тыс. д.е., краски 2 вида – 2 тыс.д.е. Общий доход будет равен сумме доходов от продаж двух видов краски, который требуется максимизировать. Поэтому целевая функция будет иметь вид:

max Z = 3x₁ + 2 x₂

Решим задачу графическим способом. Отобразим на графике все прямые, соответствующие ограничениям модели. Найдем область допустимых решений, удовлетворяющую всем ограничениям модели. Эта область - многоугольник ABCDEF. Построим ряд параллельных прямых, соответствующих уравнению целевой функции, например:

3x₁+2x₂=6,

3x₁+2x₂=12. Это так называемые линии уровня.

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

{	х1 + 2 х2 = 6 2х1 + х2 = 8

{	х1 = 6 - 2 х2 2(6 - 2 х2) + х2 = 8

…

{	х1 = 10/3 х2 = 4/3

Тогда т. С имеет координаты (10/3;4/3) и Z = 3 (10/3) + 2 (4/3) = 38/3

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