Способы перехода от одной формы задачи лп к другой
Существует несколько форм записи задач линейного программирования. Рассмотрим их.
1. Общая форма записи задачи линейного программирования: необходимо найти экстремальное значение целевой функции
(4.1)
при ограничениях
на некоторые неизвестные могут быть наложены условия неотрицательности:
Здесь
(и везде далее)
заданные числа
2. Каноническая форма записи задачи линейного программирования: необходимо найти экстремальное значение целевой функции (4.1) при ограничениях
На все неизвестные наложены условия неотрицательности:
(4.2)
3. Симметричная форма записи задачи линейного программирования. Здесь принято выделять две стандартные задачи − задачу максимизации и задачу минимизации.
3.1. Стандартная задача максимизации: необходимо найти максимальное значение целевой функции (4.1) при ограничениях
и условиях неотрицательности (4.2).
3.2. Стандартная задача минимизации: необходимо найти минимальное значение целевой функции (4.1) при ограничениях
и условиях неотрицательности (4.2).
____________________Вопрос 39____________________
Базисное решение задачи лп Симплексный метод решения задач линейного программирования
Симплексный метод – это метод последовательного улучшения плана. Этим методом можно решать задачи линейного программирования с любым количеством переменных и ограничений.
Этот метод включает в себя три основные этапа:
Построение начального опорного плана.
Правило перехода к лучшему (не худшему) решению.
Критерий проверки найденного решения на оптимальность.
При симплексном методе выполняются вычислительные процедуры (итерации) одного и того же типа в определенной последовательности до тех пор, пока не будет получен оптимальный план задачи или станет ясно, что его не существует.
Необходимые условия для применения симплекс-метода:
Задача должна иметь каноническую форму.
У задачи должен быть явно выделенный базис.
____________________Вопрос 40____________________
Связь базисных решений с угловыми точками (вершинами) множества допустимых решений
Теорема. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка многогранника области допустимых решений.
Теорема. Каждой угловой точке множества допустимых решений соответствует допустимое базисное решение.
____________________Вопрос 41____________________
Графический метод решения задачи лп
Построить многоугольник решений системы неравенств
Начертить из семейства прямых, соответствующих линейной форме, лини. равных значений функции цели.
Для построения линии равных значений придадим F некоторое числовое значение. Во многих задачах удобно принять, что F=1. Тогда получим c1x1+c2x2=1. Запишем это уравнение прямой в отрезках
x11c1+x21c2=1
Затем, откладывая на оси х1 число 1c1, а на оси х2 - 1c2, найдем точки пересечения линии равных значений с осями координат. Прямая, проведенная через эти точки, и есть требуемая прямая.
Двигать прямую вдоль градиента-вектора параллельно линии равных значений в сторону многоугольника решений до соприкосновения с многоугольником решений. Если первая встреча с многоугольником решений произойдет в крайней точке с координатами (x1’, x2’), то в этой точке функция цели достигает минимального значения. Если первая встреча произойдет со стороной многоугольника, то данная функция цели достигает минимума во всех точках стороны.
Двигаясь дальше, придем к некоторому опорному положению, когда прямая будет иметь одну общую точку (x1’’, x2’’) с многоугольником решений. В этой точке функция цели достигает своего максимума.
Если первоначально построенная линия равных значений пересекает многоугольник решений, то функция цели достигает минимального значения в вершине многоугольника, расположенной ближе к началу координат, а максимального значения - в вершине, более удаленной от начала координат.
____________________Вопрос 42____________________