Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
и записаны со знаком меньше или равно (), то ограничения двойственной задачи записываются со знаком больше или равно ( ).
.Если ограничение прямой задачи задано в виде уравнения, то соответствующее неизвестное двойственной задачи не ограничено знаком.
.Если какое-либо неизвестное прямой задачи не ограничено знаком, то соответствующее ограничение двойственной задачи будет задано в виде равенства.
.Если целевая функция прямой задачи сформулирована на максимум, то целевая функция двойственной задачи будет сформулирована на минимум.
Существует много различных комбинаций ограничений и целевой функции для записи исходной задачи. Для упрощения задачи построения двойственной задачи запишем прямую задачу в некотором стандартном виде прямой задачи. Этот вид предполагает, что:
4)все ограничения имеют знак ;
5)целевая функция сформулирована на максимум;
)все неизвестные неотрицательны.
Чтобы записать прямую задачу в стандартном виде, необходимо:
5)неравенство со знаком умножить на (-1);
)равенство заменить на два неравенства противоположных знаков, одно из которых следует умножить на (-1);
)формулировку целевой функции меняют заменой знаков коэффициентов на противоположные;
)если переменное xj не ограничено знаком, его можно представить в виде разности двух неотрицательных переменных.
Пример. Составить двойственную задачу к исходной.
.
программирование симплекс матричный граф
Решение. 1) Стандартный вид прямой задачи.
) Двойственная задача:
Задачу можно записать в виде, соответствующем исходной прямой задаче, если заменить: а) - не ограничена знаком,
б) два последних ограничения соответствуют равенству.
.