12. Модели и методы линейного программирования (лп).
13. Примеры и формы записи задач лп.
Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции
(10.10)
при условиях
(10.11)
(10.12)
.
(10.13)
функции (10.10) при условиях (10.11) (10.12) (10.13)
Функция (10.10) называется целевой функцией (или линейной формой) задачи (10.10) – (10.13), а условия (10.11) – (10.13) – ограничениями данной задачи.
2. Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального для «≤» (минимального для «≥») значения функции (10.10) при выполнении условий (10.11) и (10.13), где k = m, s = n.
3. Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции (10.10) при выполнении условий (10.12) и (10.13), где k = 0, s = n.
Каноническая (основная) форма |
Стандартная (симметричная) форма |
Общая форма |
1) ограничения |
||
Уравнения
|
Неравенства
|
Уравнения и неравенств
|
2) условия неотрицательности |
||
Все переменные
|
Все переменные , |
Часть переменных
, |
3) цель задачи
|
||
max F(x) или minF(x) |
max F(x) [min F(x)] |
max F(x) или min F(x) |
.
.
.
, 
, 
.
max F(x) = – min[– F(x)], min F(x) = – max[– F(x)].
Указанные
выше три формы задачи линейного
программирования эквивалентны в том
смысле, что каждая из них может быть
преобразована к форме другой. Совокупность
чисел 
,
удовлетворяющих ограничениям (10.11) –
(10.13), называется допустимым
решением (или планом).
Запишем основную задачу линейного
программирования в векторной форме.
Найти максимум (минимум) функции
при условиях
,
(10.14)
где 
–
скалярное произведение; 
и 
– m-мерные
вектор-столбцы, составленные из
коэффициентов при неизвестных и свободных
членов системы уравнений задачи.
План Х называется опорным
планом основной
задачи линейного программирования,
если система векторов 
,
входящих в разложение (10.14) с положительными
коэффициентами 
,
линейно независима.
Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае он является вырожденным.
План 
,
при котором целевая функция принимает
свое максимальное (минимальное) значение,
называется оптимальным.
17. Модификации задач лп: задачи транспортного типа, задача производства с запасами, задача о назначениях.
18. Сетевые задачи выбора маршрута. Задачи упорядочения.
19. Многокритериальные задачи принятия решений в условиях определенности. Задачи векторной оптимизации.
в многокритериальных задачах принятия решений понятие оптимальности плана теряется, так как не существует такого плана, который доставлял бы одновременно экстремальное значение отдельным критериям. Это обстоя-тельство и является причиной того, что методы решения много-критериальных задач предусматривают в том или ином виде учет мнения лица, принимающего решение. Чтобы выбрать из области Парето лучшие решения, ЛПР обязан ввести соответ-ствующие принципы выбора компромиссного решения, приво-дящие к тому или иному методу решения задачи.
наиболее часто употребляемые методы решения многокритериальных задач: