Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата

В примерах, приведенных выше, имеется нечто общее. Каждый из них требует нахождения наиболее выгодного варианта в определенной экономической ситуации. С чисто математической стороны в каждой задаче требуется найти значение нескольких неизвестных так, чтобы

1) все эти значения были неотрицательны;

2) удовлетворяли системе линейных уравнений или линейных неравенств;

3) при этих значениях некоторая линейная функция имела бы минимум (или максимум). Таким образом, линейное программирование - это математическая дисциплина, изучающая методы нахождения экстремального значения линейной функции нескольких переменных при условии, что последние удовлетворяют конечному числу линейных уравнений и неравенств. Запишем это с помощью формул: дана система линейных уравнений и неравенств.

Запишем это с помощью формул: дана система линейных уравнений и неравенств

(7.80)

и линейная функция

(7.81)

Требуется найти такое неотрицательное решение

(7.82)

системы (7.80), чтобы функция/принимала наименьшее (или наибольшее) значение.

Условия (7.80) называют ограничениями данной задачи, а функцию f- целевой функцией (или линейной формой). В приведенных выше примерах ограничения имели вид не уравнений, а неравенств. Заметим, что ограничения в виде неравенств, всегда можно свести к системе в виде равенств (способом введения добавочных неизвестных).

Так, для неравенства

(7.83)

вводя добавочное неизвестное хn+1, получаем

(7.84)

Потребовав его неотрицательности наряду с остальными неизвестными, получим, что условие хn+1( 0 превращает (7.84) в (7.83). Введя по отдельному дополнительному неизвестному для каждого из неравенств, получим систему уравнений, равносильную исходной системе неравенств.

Пример. Дана система неравенств

Сведем ее к системе уравнений. Получим

После оптимизации значениями дополнительных неизвестных следует пренебречь.

СИМПЛЕКС-МЕТОД

Для решения ряда задач линейного программирования существуют специальные методы. Есть, однако, общий метод решения всех таких задач. Он носит название симплекс-метода и состоит из алгоритма отыскания какого- нибудь произвольного допустимого решения и алгоритма последовательного перехода от этого решения к новому допустимому решению, для которого функция f изменяется в нужном направлении (для получения оптимального решения).

Пусть система ограничений состоит лишь из уравнений

(7.85)

и требуется отыскать минимум линейной функции (7.81). Для отыскания произвольного опорного решения приведем (7.85) к виду, в котором некоторые r неизвестных выражены через остальные, а свободные члены неотрицательны
(как это сделать - обсудим позднее):

Рекомендуем скачать другие рефераты по теме: рефераты бесплатно скачать, сообщения бесплатно.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата