Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
§ 8. Основная задача линейного программированияЛюбую задачу линейного программирования можно свести к стандартной форме, так называемой «основной задаче линейного программирования» (ОЗЛП), которая формулируется так: найти неотрицательные значения переменных
и обращали бы в максимум линейную функцию этих переменных:
Убедимся в этом. Во-первых, случай, когда L надо обратить не в максимум, а в минимум, легко сводится к предыдущему, если попросту изменить знак L на обратный (максимизировать не L, а Пусть требуется найти неотрицательные значения переменных
и обращающие в максимум линейную функцию от этих переменных:
Начнем с того, что приведем условия (8.3) к стандартной форме, так, чтобы знак неравенства был а справа стоял нуль. Получим:
А теперь обозначим левые части неравенств (8.5) соответственно через
Из условий (8.5) и (8.6) видно, что новые переменные Какая же теперь перед нами стоит задача? Найти неотрицательные значения переменных Переход к ней от первоначальной задачи с ограничениями-неравенствами (8.3) «куплей» ценой увеличения числа переменных на два (число неравенств). Возможен и обратный переход: от ОЗЛП к задаче с ограничениями-неравенствами. Пусть перед нами основная задача линейного программирования с ограничениями-равенствами (8.1). Предположим, что среди этих Итак, всякая задача линейного программирования может быть сведена к стандартной форме ОЗЛП. Мы не будем подробно останавливаться на способах решения этой задачи. Им посвящены специальные руководства (например, [4, 53), они описаны во многих книгах по исследованию операций (например, [6, 7]). В следующем параграфе мы изложим только некоторые соображения общего характера относительно существования решения ОЗЛП и способов его нахождения. Никакими расчетными алгоритмами мы заниматься не будем, а отошлем интересующегося читателя к вышеупомянутым руководствам.
|
1 |
Оглавление
|