![]() |
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Геометрическая интерпретация задачи ЛП и графо-аналитический метод ее решения.
Как известно, в Взаимодействие линий уровня с ОДР Пусть задача ЛП в
ОДР Множество называется выпуклым, если выполняется условие:
В Семейство линий уровня целевой функции в Находим вектор В пространстве Изобразим графически наиболее характерные случаи решения задачи ЛП в пространстве
Оптимальные планы находятся в вершинах выпуклого многоугольника.
Задача ЛП имеет бесконечное множество решений, т.к. линия уравнения
Целевая функция
ЛК №6 08.10.2003
Основная теорема линейного программирования (ОТЛП).
Теоремы о свойствах решения задачи ЛП. Представим задачу ЛП в виде:
где Задача ЛП (1), (2), (3) будет иметь решение тогда, когда совместна система линейных уравнений (2); последняя совместна при выполнении условия: Если Если Предположим, что Если положить СП равными нулю и при этом
Теорема: Если система векторов Доказательство см. в [5]. Теорема: Если задача ЛП имеет решение, то целевая функция
ОТЛП легко наблюдаема при усмотрении 1-го и 2-го случая геометрической интерпретации задачи ЛП в
точках Доказательство см. в [5].
Симплексный метод решения задачи ЛП. Симплексный метод (СМ) – универсальный аналитико-численный эффективный метод решения задач ЛП.
Идея СМ. В соответствии с ОТЛП целевая функция Эта теорема позволяет сформулировать основные этапы алгоритма прямого метода решения задач ЛП: 1) нахождение координат крайних точек многогранника решений; 2) вычисление значений 3) нахождение минимального (максимального) значения Неэффективность этого метода очевидна, особенно с ростом размерности пространства. Симплексный метод (метод последовательного получения планов), также как и прямой метод, состоит из 3-х этапов: 1) построение начального опорного плана; 2) формулировка критерия оптимальности опорного плана; 3) переход к нехудшему опорному плану, и в конечном итоге, оптимальному плану Эффективность СМ значительно выше эффективности " прямого" метода. Универсальность СМ в сочетании с эффективностью позволяют использовать его в решении значительной части задач ЛП кроме наиболее легких. Идея СМ легко понимаема при графической интерпретации задачи ЛП.
ЛК №7 15.10.2003
Из решения видно, что прямой метод предполагает вычисление СМ предполагает нахождение начального опорного плана (при поиске СМ " выбирает" оптимальную траекторию поиска экстремальных точек во множестве крайних точек многогранника планов.
3.6.1. Построение начального опорного плана. Пусть каноническая задача ЛП имеет систему линейных уравнений ограничений вида:
Для того, чтобы найти начальный опорный план Система (1) будет иметь предпочтительный вид, если каждое ее уравнение будет содержать переменную, входящую в него с коэффициентом, равным (+1); во все другие уравнения эта переменная должна входить с коэффициентом, равным нулю.
Заметим, что переменные Полагая Начальный опорный план: Легко понять, что предпочтительная переменная – базисная переменная, в соответствии с определением опорного плана. Предположим, что система ограничений задач ЛП имеет вид:
Известно, что вводя дополнительные (балансовые) переменные:
Поскольку дополнительные (балансовые) переменные входят в каждое уравнение системы с коэффициентом, равным 1 и входят в другие уравнения с коэффициентом, равным 0.
Система (3) имеет предпочтительный вид: каждая СП Предположим, что система неравенств ограничения имеет вид:
Вводя балансовые переменные
Начальный опорный план Рассмотрим случай, когда в системе линейных уравнений ограничений ни одно из уравнений не имеет предпочтительного вида:
В этом случае вводят искусственный базис – множество переменных Следует особо отметить, что эти переменные входят в выражение для целевой функции с коэффициентом Итак, с введением искусственного базиса исходная каноническая задача ЛП преобразуется в расширенную задачу ЛП
Знак "
Очевидно, что начальный опорный план (7) имеет вид:
Легко показать, что в оптимальном плане Пусть
3.6.3. Симплексные таблицы. Признак оптимальности опорного плана. Как известно, корректно сформулированную задачу ЛП всегда можно представить в канонической форме вида:
Заметим, что целевая функция представляется как функция только СП:
При решении (1), (2), (3) СМ целесообразно представить ее с помощью таблицы, которая называется симплексной таблицей (СТ).
ЛК №8 22.10.2003
СМ - итерационный метод и каждому опорному плану будет соответствовать своя СТ.
Как видно, СТ состоит из Значительную часть СТ занимает система уравнений ограничений экономической задачи ЛП. Система представлена в предпочтительном виде:
Следует особо отметить, что последняя
Величина
Заметим, что из СТ с очевидностью вытекает структура вектор-столбца
Легко понять, что Как было выше замечено, последняя
Признак оптимальности опорного плана. Теорема 1: Пусть решается задача ЛП на максимум. Если для некоторого опорного плана все оценки СП неотрицательны, т.е. Доказательство: Известно, что целевая функция представима выражением:
Поскольку
Итак, условия Теорема 2: Пусть решается задача ЛП на минимум. Если для некоторого опорного плана все оценки СП неположительны, т.е.
Доказательство: Известно, что целевая функция представима выражением:
Поскольку
Итак, условия Каждому опорному плану соответствует своя СТ, т.е. СМ – итерационный метод. В связи с этим, если рассматриваемый опорный план не оптимален, то следует перейти от него к нехудшему опорному плану.
3.6.4. Переход к нехудшему опорному плану; симплексное преобразование. Пусть каноническая задача ЛП – задача на максимум имеет вид:
Известно, что система уравнений ограничений (2) имеет предпочтительный вид, поэтому начальный опорный план легко определить: Если в последней строке Вектор-столбец
ЛК №9 29.10.2003
цом СТ, а соответствующая ему переменная Пусть все свободные переменные (кроме
Причем Из (7) следует, что увеличивая СП Однако, увеличивать перспективную переменную Рассмотрим в связи с этим (2), зная, что все СП (кроме
Из (9') при следует, что увеличение Перепишем (9') в виде:
Выражение (12) позволяет найти разрешающую строку Выясним структуру составляющих (компонент) нехудшего опорного плана с учетом выражения (13) для перспективной координаты
Переменная Соответственно,
Как изменятся элементы СТ при перестановке вида (15)? Выясним детально этот вопрос, используя так называемое симплексное преобразование. Исходными являются уравнения системы ограничений:
Выделим из (16) уравнение
Далее подставим выражение для
Итак, найденное для
где
ЛК №10 05.11.2003
После элементарных преобразований (18) преобразуется к виду:
Система уравнений (18а) соответствует новой СТ, представляющей нехудший опорный план Легко понять, что
Элементы
Из (22) следует, что элементы
Совершив симплексные преобразования, получили аналитические выражения (17), (18а), (19), (20), (23), (24), позволяющие относительно просто заполнить новую СТ нехудшего опорного плана. Основные правила заполнения новой СТ: 1) Элементы разрешающей строки
Заметим, что элемент
2) Элементы разрешающего столбца 3) Элементы
Приведем простую вычислительную схему для нахождения элементов (19'). 4) Отметим, что структура формул, определяющих элементы новой СТ для
5) Следует отметить, что элементы
Эти два способа должны дать одинаковый результат, что используется при контроле вычислений. Представляет интерес найти на каждом шаге итерации СМ приращение целевой функции:
Как известно
где Значение Итак, завершен анализ всех 3-х этапов СМ. однако, анализ
3.6.5. Теорема бесконечности множества оптимальных планов задачи ЛП. Теорема: Пусть в последней СТ, таблице, содержащей оптимальный план, |
Последнее изменение этой страницы: 2017-04-12; Просмотров: 853; Нарушение авторского права страницы