Классификация методов математического программирования
В зависимости от особенностей целевой функции 
и функций 
, задающих ограничения, задачи математического программирования можно отнести к следующим разделам:
1) Если целевая функция 
и функции 
, входящие в систему ограничений, линейны (первой степени) относительно входящих в модель задачи неизвестных 
, то такие задачи относят к разделу линейного программирования (ЛП).
2) Если в задаче математического программирования целевая функция 
и (или) хотя бы одна из функций системы ограничений является нелинейной относительно входящих в задачу неизвестных 
, то такие задачи относят к разделу нелинейного программирования (НЛП).
3) Если на все или некоторые переменные наложено условие дискретности, например целочисленности ( = 0,1,2…), то такие задачи рассматриваются в разделе математического программирования, называемом дискретным, в частности целочисленным программированием (ЦП).
4) Если параметры целевой функции или системы ограничений изменяются во времени или процесс решения задачи имеет многошаговый характер, то такие задачи решаются методами динамического программирования (ДП).
В перечисленных выше разделах математического программирования предполагается, что вся информация о протекании процессов заранее известна и достоверна. Такие методы оптимизации называются детерминированными.
5) Если параметры, входящие в функцию цели, или ограничения задачи являются случайными, недостоверными величинами или, если приходится принимать решения в условиях риска, неполной или недостоверной информации, то говорят о проблеме стохастической оптимизации, а соответствующий раздел называется стохастическим программированием (СП). К нему относятся теория массового обслуживания, математическая теория игр и некоторые другие.
|
|
|
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Задача линейного программирования (ЗЛП)
Общей задачей линейного программирования (ОЗЛП) называется следующая задача:
(2.1)
, (2.2)
, (2.3)
, (2.4)
, (2.5)
где 
– заданные действительные числа,
(2.1)- целевая функция, (2.2)-(2.5)-ограничения.
Вектор 
, координаты которого удовлетворяют ограничениям, называется допустимым решением задачи.
Множество допустимых решений задачи называют областью допустимых решений.
Допустимое решение, на котором целевая функция достигает своего максимума (минимума), называется оптимальным решением или оптимальным планом задачи ЛП.
Составим экономико-математические модели некоторых задач линейного программирования.
|
|
|
Пример 1
Имеются стержни, длиной 5 м. Необходимо их разрезать на заготовки 2-х видов: А - длиной 1,5 м; В - длиной 0,8 м для производства 20 изделий. На каждое изделие требуется две длинных заготовки (А) и три коротких (В). Определить число стержней, которое необходимо разрезать каждым из возможных способов, чтобы изготовить нужное число изделий и минимизировать отходы.
Решение
Прежде всего, перебрав все возможные способы, построим карту раскроя одного стержня (таблица 1).
Таблица 1
| Способ | Количество заготовок А (по 1,5 м) | Количество заготовок В (по 0,8 м) | Отходы, м |
| I | 3 | - | 0,5 |
| II | 2 | 2 | 0,4 |
| III | 1 | 4 | 0,3 |
| IV | - | 6 | 0,2 |
Для изготовления 20 изделий потребуется заготовок А: 20´2=40 шт. и заготовок В: 20´3=60 шт.
1) Введем переменные. Обозначим за 
- количество стержней, которые будут разрезаны I способом, 
- II способом, 
- III способом, 
- IV способом.
2) Целевая функция Z -отходы. Ее будем минимизировать. Найдем отходы, полученные при разрезании стержней:
- отходы, полученные при разрезании стержней I способом,
так как 5-3·1,5=0,5;
- отходы, полученные при разрезании стержней II способом,
так как 5-2·1,5-2*0,8=0,4;
- отходы, полученные при разрезании стержней III способом,
|
|
|
так как 5-1·1,5-4*0,8=0,3;
- отходы, полученные при разрезании 
стержней IV способом,
так как 5-6·0,8=0,2.
Тогда 
.
3) Составим систему ограничений задачи.
1 Ограничение на заготовки А.
При разрезании 
стержней I способом получим 
заготовок А,
стержней II способом – 
заготовок А, стержней III способом – 
заготовок А, при разрезании стержней IV способом заготовок А не образуется. Таким образом, всего получим + + заготовок А, что по условию задачи должно быть не менее 40, то есть 
+ 
+ 
.
2 Аналогично получим ограничение на заготовки В:
.
3 Составим ограничения на смысл переменных. Так как количество стержней может быть только неотрицательным числом, то 
и 
– целые.
Итак, экономико-математическая модель данной задачи имеет вид:
;
Пример 2
Предприятие за 10 часов должно произвести 31 единицу продукции вида Р1 и 36 единиц продукции вида Р2. Для производства продукции каждого вида может быть использовано оборудование А1 или А2.
Производительность оборудования этих групп различна и определяется величиной 
ед./ч, а стоимость 1 часа работы оборудования составляет 
усл. ден. ед./ч 
, где i – индекс, отличающий вид оборудования, а j – вид продукции. Требуется определить оптимальный план работы групп оборудования, на протяжении 10 часов, при котором будет выполнен план выпуска продукции с минимальной себестоимостью.
|
|
|
Решение
Для наглядности составим таблицу 2.
Таблица 2
| Продукция Р1 | Продукция Р2 | ||
| Оборудование А1 |  ед./ч
 усл. ден. ед./ч
|  ед./ч
 усл. ден. ед./ч
| 10 ч |
| Оборудование А2 |  ед./ч
 усл. ден. ед./ч
|  ед./ч
 усл. ден. ед./ч
| 10 ч |
| 31 ед. | 36 ед. |
1) Обозначим за 
- время работы оборудования 
по выпуску продукции 
, 
.
2) Целевая функция будет представлять собой затраты на выпуск продукции, которые необходимо минимизировать. Так как затраты по выпуску продукции на оборудование составляют 
, то целевая функция будет иметь вид:
, то есть 
.
3) Составим систему ограничений.
1 Ограничение на выпуск продукции Р1.
На оборудовании А1 будет произведено 
единиц продукции Р1.
На оборудовании А2 будет произведено 
единиц продукции Р1.
Таким образом всего продукции 
будет произведено 
, что по условию должно быть равно 31, то есть получим ограничение
, или 
.
2 Аналогично получим ограничение по выпуску продукции Р2:
, или 
.
3 Ограничение на время работы оборудования А1.
Время работы оборудования А1 по выпуску обоих видов продукции не превышает плановый период 10 ч, следовательно, ограничение будет иметь вид:
.
4 Аналогично получим ограничение на время работы оборудования А2:
.
5 Введем ограничения на смысл переменных, так как время не может быть отрицательным, то
.
Таким образом, экономико-математическая модель данной задачи будет иметь вид:
;
Пример 3
Предприятие может выпускать продукцию двух видов: П1 и П2. Используется три вида ресурсов: оборудование, сырье и электроэнергия. Нормы расхода, лимиты ресурсов и прибыль от единицы продукции представлены в таблице 3.
Таблица 3
| Ресурсы | Нормы расхода на единицу продукции | Лимит (запас) ресурса | |
| П1 | П2 | ||
| Оборудование Сырье Электроэнергия | 2 1 2 | 3 1 1 | 30 12 20 |
| Прибыль от единицы продукции | 5 | 4 | |
Найти оптимальный план выпуска продукции.
Решение
Введем переменные:
, 
– объем выпускаемой продукции П1 и П2 соответственно.
Z – прибыль от продажи всей выпущенной продукции.
Экономико-математическая модель данной задачи будет иметь вид:
;
Методы решения задач линейного программирования будут рассмотрены ниже.
Дата добавления: 2018-09-20; просмотров: 979; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!