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

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

 

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

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

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

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

Становление современного математического аппарата оптимальных экономических решений началось в 1940-е гг., благодаря первым работам Н. Винера, Р. Беллмана, С. Джонсона, Л. В. Канторовича.

В 1938 г. Перед двадцатипятилетним профессором ЛГУ Л. В. Канторовичем была поставлена задача: как наилучшим образом распределить работу восьми станков фанерного треста при условии, что известна производительность каждого станка по каждому из пяти видов обрабатываемых материалов. В 1939г. Канторович опубликовал работу «Математические методы оптимизации и планирования производства», в которой впервые сформулировал задачу линейного программирования и разработал алгоритм ее решения. В 1975г. Совместно с американским ученым Т. Купмансом Канторович получил Нобелевскую премию в области экономика за вклад в теорию оптимизации распределения ресурсов.

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

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

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

Рассмотрим основные понятия математического программирования.

Целевой функцией (показателем эффективности, критерием оптимальности) называют функцию, экстремальное значение которой нужно найти.

Экстремальным значением называют максимальное или минимальное значение.

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

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

 

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

1. Экономическая постановка задачи

В некоторых пунктах A_i сосредоточен однородный товар в количестве соответственно а_i . Пункты B_j имеют потребность в этом товаре в количестве b_j соответственно. Известны тарифы перевозок единицы товара. Необходимо составить план перевозок, который обеспечит минимум транспортных затрат.

2. Математическая модель

2.1. Исходные параметры

– количество пунктов A_i

– количество пунктов B_j

– количество товара в пункте A_i

– количество товара в пункте B_j, причем .

– тариф перевозки единицы товара из пункта A_i в пункт B_j.

2.2. Управляемые параметры

– количество товара, перевезенного из пункта A_i в пункт B_j.

– матрица управляемых параметров (решение, план перевозок).

2.3 Формулировка критерия оптимальности

Сформулируем критерий оптимальности. Пусть – стоимость произвольного плана перевозок . Требуется найти план перевозок наименьших транспортных затрат.

2.4. Ограничения модели

Необходимо вывезти весь товар из пунктов A_i и полностью удовлетворить потребности пунктов B_j в этом товаре Система ограничений имеет вид:

 

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

на котором достигается наименьшее значение критерия

при условии

.

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

IV. Задача о раскрое.

1. Экономическая постановка задачи

Имеются стержни длиной 5 м. Необходимо их разрезать на заготовки 2-х видов: А – длиной 1, 5 м; В – длиной 0, 8 м для производства 20 изделий. На каждое изделие требуется две длинных заготовки (А) и три коротких (В). Определить число стержней, которое необходимо разрезать каждым из возможных способов, чтобы изготовить нужное число изделий и минимизировать отходы.

2. Математическая модель

Прежде всего, перебрав все возможные способы, построим карту раскроя одного стержня (таблица 1).

 

Таблица 1

 

Способ	Количество заготовок А (по 1, 5 м)	Количество заготовок В (по 0, 8 м)	Отходы, м
		-	0, 5
			0, 4
			0, 3
	-		0, 2

 

Для изготовления 20 изделий потребуется 40 заготовок А (20´ 2=40) и 60 заготовок В (20´ 3=60).

Введем переменные (управляющие параметры). Обозначим за – количество стержней, которые будут разрезаны I способом, – II способом, – III способом, – IV способом.

Сформулируем критерий оптимальности. Пусть целевая функция Z описывает отходы. Ее будем минимизировать. Найдем отходы, полученные при разрезании стержней:

– отходы, полученные при разрезании стержней 1-м способом, так как 5 - 3·1, 5 = 0, 5;

– отходы, полученные при разрезании стержней 2-м способом, так как 5 - 2·1, 5 - 2· 0, 8 = 0, 4;

– отходы, полученные при разрезании стержней 3-м способом, так как 5 - 1·1, 5 - 4· 0, 8 = 0, 3;

– отходы, полученные при разрезании стержней 4-м способом, так как 5–6· 0, 8 = 0, 2.

Тогда .

Составим систему ограничений задачи.

Ограничение на заготовки А.

При разрезании стержней 1-м способом получим заготовок А, стержней 2-м способом – заготовок А, стержней 3-м способом – заготовок А, при разрезании стержней 4-м способом заготовок А не образуется. Таким образом, всего получим + + заготовок А, что по условию задачи должно быть не менее 40, т.е. + + .

Аналогично получим ограничение на заготовки В:

.

Составим ограничения на смысл переменных. Так как количество стержней может быть только неотрицательным числом, то и – целые.

Итак, математическая модель данной задачи имеет вид

;

 

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

Пример 3

Предприятие может выпускать продукцию двух видов: П₁ и П₂. Используется три вида ресурсов: оборудование, сырье и электроэнергия. Нормы расхода, запасы ресурсов и прибыль от реализации единицы продукции представлены в таблице 3.

Таблица 3

Ресурсы	Нормы расхода на единицу продукции	Запас ресурса
П1	П2
Оборудование, ч
Сырье, кг
Электроэнергия, кВт-ч
Прибыль от реализации единицы продукции, ден. ед.

 

Найти оптимальный план выпуска продукции, учитывая, что предприятие уже заключило контракт на поставку 2 единиц продукции П₂.

Решение

Введем переменные (управляющие параметры):

, – объем выпускаемой продукции П₁ и П₂ соответственно.

Z – прибыль от реализации всей выпущенной продукции.

Экономико-математическая модель данной задачи будет иметь вид

;

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

Затем определим, какую полуплоскость определяет соответствующее неравенство, подставив координаты какой-нибудь точки, например начала координат. Ограничения (2.10) означают, что ОДР лежит в I четверти системы координат . Соответствующие полуплоскости на рисунке показаны стрелками. Пересечение указанных полуплоскостей и определяет многоугольник решений данной задачи (ОДР).

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

 

Рис. 4 Пример решения задачи графо-аналитическим методом.

Точка является точкой пересечении прямых и . Для определения ее координат необходимо решить систему уравнений:

Откуда . Это и есть оптимальный план задачи. Подставив значение и в целевую функцию Z, получаем

.

Таким образом, для того чтобы получить максимальную прибыль в размере 56 ден. ед., необходимо запланировать выпуск 8 ед. продукции вида П₁ и 4 ед. продукции П₂.

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

с помощью Поиска решений в среде EXCEL

1) Ввести исходные данные.

2) Ввести первоначальные значения управляемых параметров.

3) Ввести зависимость для целевой функции.

4) Ввести зависимости для ограничений.

Запустить Поиск решения.

5) Указать адрес целевой ячейки (установить целевую ячейку) и вид оптимизации.

6) Указать адрес изменяемых ячеек.

7) Ввести ограничения.

8) Ввести параметры для решения ЗЛП.

 

Пример решениязадачи с помощью Поиска решений в среде EXCEL.

Задача

Решение

Заполняем электронную таблицу

1) В ячейках А2: С5, Е2: Е5, А9: С9 – исходные данные.

2) В ячейки А12: С12 вводим нули.

3) В целевой ячейке В13 вводим формулу: =СУММПРОИЗВ(A9: C9; A12: C12).

4) В ячейках D2: D4 водим формулы:

D2=СУММПРОИЗВ(A2: C2; A12: C12)

D3=СУММПРОИЗВ(A3: C3; A12: C12)

D4=СУММПРОИЗВ(A4: C4; A12: C12).

 

 

 

Запускаем Поиск решения. И выполняем шаги 5 - 8 алгоритма:

 

Нажимаем Параметры.

Отмечаем Линейная модель

Неотрицательные значения

Нажимаем Ок.

Возвращаемся в предыдущее окно.

Нажимаем Найти решение.

В результате получаем

Нажимаем Ок.

Получаем результат:

 

Вывод: целевая функция достигает минимума, равного 19, 375 при x₁=1, 875, x₂=13, 75, x₃=0.

Пример решениятранспортнойзадачи с помощью Поиска решений в среде EXCEL.

Найти оптимальный план транспортной задачи, где - матрица стоимости перевозки единицы груза, - его запасы и - спрос в данном грузе.

.

Заполняем электронную таблицу:

1) В ячейках B2: E4, F2: F4, B5: E5 – исходные данные.

2) В ячейки B8: E10 вводим нули.

3) В целевой ячейке В13 вводим формулу:

=СУММПРОИЗВ(B2: E4; B8: E10).

4) В ячейках F8: F10 и B11: E11 водим формулы:

F8=СУММ (B8: E8)

F9=СУММ (B9: E9)

F10=СУММ (B10: E10)

B11=СУММ (B8: B10)

C11=СУММ (C8: C10)

D11=СУММ (D8: D10)

E11=СУММ (E8: E10).

 

Запускаем Поиск решения. И выполняем шаги 5 - 8 алгоритма:

Нажимаем Параметры.

 

Отмечаем Линейная модель

Неотрицательные значения

Нажимаем Ок.

Возвращаемся в предыдущее окно.

Нажимаем Выполнить.

В результате получаем

 

Нажимаем Ок.

Получаем результат:

 

 

Вывод: оптимальный план перевозок следующий:

¾ от 1-го поставщика 2-му потребителю необходимо перевезти 150ед. товара, а 4-ому потребителю – 90 ед. товара,

¾ от 2-го поставщика 1-ому потребителю необходимо перевезти 130ед. товара, а 2-ому потребителю – 80 ед. товара;

¾ от 3-го поставщика 3-ому потребителю необходимо перевезти 190ед. товара, а 4-ому – 40 ед.

При этом стоимость перевозки будет минимальной, т.е. будет составлять 2720 у.е.

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

 

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

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

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

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

Становление современного математического аппарата оптимальных экономических решений началось в 1940-е гг., благодаря первым работам Н. Винера, Р. Беллмана, С. Джонсона, Л. В. Канторовича.

В 1938 г. Перед двадцатипятилетним профессором ЛГУ Л. В. Канторовичем была поставлена задача: как наилучшим образом распределить работу восьми станков фанерного треста при условии, что известна производительность каждого станка по каждому из пяти видов обрабатываемых материалов. В 1939г. Канторович опубликовал работу «Математические методы оптимизации и планирования производства», в которой впервые сформулировал задачу линейного программирования и разработал алгоритм ее решения. В 1975г. Совместно с американским ученым Т. Купмансом Канторович получил Нобелевскую премию в области экономика за вклад в теорию оптимизации распределения ресурсов.

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

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

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

Рассмотрим основные понятия математического программирования.

Целевой функцией (показателем эффективности, критерием оптимальности) называют функцию, экстремальное значение которой нужно найти.

Экстремальным значением называют максимальное или минимальное значение.

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

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

 

1234Следующая ⇒

Поделиться: