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

1.   Определение цели, т.е чего хотят добиться решая поставленную задачу.

2.   Определение параметров модели, т.е. заранее известных фиксированных факторов, на значения которых исследователь не влияет.

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

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

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

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

 

 

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

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

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

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

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

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

.

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

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

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

.

Определение 3: Допустимым решением (планом) задачи линейного программирования называется вектор .

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

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

I раздел

Графический метод

Графический метод является наиболее простым и наглядным методом линейного программирования.

 

Применяется для решения задач линейного программирования с 2-мя переменными.

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

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

Алгоритм решения задач ГМ.

1. Находим область допустимых решений системы ограничений задачи.

2. Строим вектор С.

3. Проводим линию уровня L_0, которая перпендикулярна С.

4. Линию уровня перемещаем по направлению вектора С для задач на максимум и в направлении противоположном С, для задач на минимум.

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

5.Находим координаты точки экстремума и значение целевой функции в ней.

Возможны следующие случаи ОДР:

 

 

Пример. Выбор оптимального выпуска изделий.

Фирма выпускает 2 вида мороженого: сливочное и шоколадное. Для изготовления мороженого используются 2 вида продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы заданы в таблице.

Исходный продукт	Расход исходных продуктов		Запас,кг
	сливочное	шоколадное
Молоко	0,8	0,5	400
Наполнители	0,4	0,8	365

Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого 16 руб., шоколадного – 14 руб.

Какое количество мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным?

Решение.

Обозначим: х1 – суточный объем выпуска сливочного мороженого, кг; х2 - суточный объем выпуска шоколадного мороженого, кг.

Составим математическую модель задачи.

Целевая функция будет иметь вид:

L(x) = 16x1+14x2 – max при ограничениях:

0,8 x1+ 0,5x2£ 400,

0,4x1+0,8x2£ 365,

x1-x2£100,

x2£350,

x1³0, x2³0.

 

OABDEF – область допустимых решений. Строим вектор с(1;1). Линия уровня задается уравнением  L₀ = 16x1+14x2=const.

Перемещаем линию уровня по направлению вектора с. Точкой выхода L₀  из области допустимых решений является точка D, ее координаты определяются как пересечение прямых, заданных уравнениями:

0,8х1+0,5х2=400

0,4х1+0,8х2 = 365.

Решая систему, получим координаты точки D (312,5; 300), в которой и будет оптимальное решение, т.е Х_опт =(312,5; 300), при этом

L(x)_max = 16*312,5 + 14*300 = 9200.

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

 II раздел

Транспортная задача

Общая постановка задачи

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

В общем виде транспортную задачу можно представить следующим образом: Некий продукт (например, сталь) вырабатывается на m заводах , причем ежемесячная выработка составляет соответственно. Пусть эту сталь нужно доставить на предприятия (всего k), причем - ежемесячная потребность этих предприятий. Наконец, пусть задана стоимость ,  перевозки одной тонны стали с завода на предприятие .  Принято считать, что общее производство стали равно суммарной потребности в ней:

а₁+а₂+…+а_т= b₁+ b₂+… b_k.

Требуется составить план перевозок, при котором:

1) была бы точно удовлетворена потребность в стали предприятий ;

2) была бы вывезена вся сталь с заводов ;

3)общая стоимость перевозок была бы наименьшей.