Сущность параметрического программирования.
Область его практического использования. Параметрическое программирование (параметрическая оптимизация) используется, когда исходные данные (объём, грузооборот) задаются не однозначно, а в определённом диапазоне. Вводится параметр , который показывает, какая доля перевозок сверх минимальных (обязательных плановых) может быть освоена при оптимальной расстановке флота. В качестве примера рассмотрим задачу оптимизации расстановки флота в параметрической постановке: Qj – min (обязательный) объём перевозок на j – линии. Вj - дополнительный объём перевозок на j – линии. Q’j = (общий объём перевозок) Фij = - флот i – ого типа, работающий на j – линии. Xij = флот, необходимый для освоения min объёма перевозок. Zij = флот, необходимый для освоения дополнительного объёма перевозок.
Постановка обычной задачи. Постановка параметрической задачи.
Если в обычной задаче нужно найти только хij, то в параметрической нужно найти xij, Zij, и . Общий вид таблицы-матрицы при решении задачи параметрического програмирования:
Резерв флота | ||||||||||||||||||||
I | Qj | |||||||||||||||||||
Фi | bj ai | b1 | b2 | - | bn | |||||||||||||||
1 | Ф1 | a | P11 X11+ Z11 Э11 | P12 X12+ Z12 Э12 | - | P1n X1n+ Z1n Э1n | Ф1рез | |||||||||||||
2 | Ф2 | a | P21 Э21 | P22 X22+ Z22 Э22 | - | P2n Э2n | Ф2рез | |||||||||||||
- | - | - | - | - | - | - | - | |||||||||||||
m |
Ф m | a | Pm1 Э m1 | Pm Э m | - | Pm Э m | Ф m рез | |||||||||||||
Алгоритм решения параметрической задачи включает 3 этапа.
1) Решается обычная задача расстановки судов по линиям (симплекс-методом или модифицированным распределительным методом) для Qj.
2) Определяются значения Zij, т. е. количество флота, необходимого для освоения дополнительного объёма перевозок Bj.
- Сначала определяются значения Zij в столбцах где xij > 0- единственное по столбцу. В этих случаях Zij будет со знаком “+”; если xij = Фi, тогда Zij будет равно 0; если xij < Фi, то Zij > 0.
- Затем переходим к столбцам, где xij > 0 – не единственное в столбце. Здесь могут иметь место 2 случая: если , то Z будет со знаком “+”; если , то Z < 0 .
3) Находим по тем клеткам, где *Zij вычитается:
Рассмотрим реализацию алгоритма на примере:
Имеются 4 типа судна и 6 линий движения. До заполнения матрицы должна быть расписана обычная математическая постановка задачи расстановки флота по линиям. Все расчёты будем проводить в матрице
j | 2 | 3 | 4 | 5 | 6 | 7 | |||
i | Qj Фi | 130+ 13 | 20+ 5 | 190+ 20 | 50+ 8 | 100+ 10 | 150+ 10 | Резерв флота | |
1 | 5 | 55 2,36+ 0,23 200 | 30 210 | 45 215 | 48 0,64- 0,43 205 | 50 2+ 0,2 220 | 40 230 | ||
2 | 2 | 50 220 | 25 230 | 42 1,35+ 1,01 245 | 50 235 | 40 240 | 35 0,65- 1,01 250 | ||
3 | 7 | 40 215 | 18 1,11+ 0,28 225 | 32 230 | 44 210 | 55 220 | 30 4,25+ 1,51 235 | 1,64- 1,79 | |
4 | 4 | 45 190 | 22 205 | 37 3,6- 0,6 200 | 48 0,4+ 0,6 195 | 34 210 | 32 212 |
|
Z11 =
Z32 =
Z15 =
Z14 = l*0,2 + l*0,23 = l*0,43 Z44 =
Z43 = - 0,6 Z23 =
Z26 = - 1,01
Z36 =
Находим по тем клеткам, где Zij имеет знак « - ».
Т. о. на первом этапе мы определили xij, на втором - Zij, на третьем -
После получения решения необходимо рассчитать значение целевой функции и осуществить проверку ограничений.
Понятие имитационного моделирования.
2019-11-21 | 255 | Обсуждений (0) |
5.00
из
|
Обсуждение в статье: Сущность параметрического программирования. |
Обсуждений еще не было, будьте первым... ↓↓↓ |
Почему 1285321 студент выбрали МегаОбучалку...
Система поиска информации
Мобильная версия сайта
Удобная навигация
Нет шокирующей рекламы