- •Математические модели задач лп
- •1.1. Постановка задачи лп
- •1.2. Рекомендации к составлению математических моделей
- •1.3. Пример задачи лп --- задача о диете
- •Графическое решение задач лп
- •2.1. Каноническая форма задачи лп
- •2.2 Пример
- •2.3. Общие рекомендации к графическому решению задач лп
- •2.4. Пример
- •3. Численные методы решения задач лп
- •3.1. Симплекс – метод
- •3.2. Алгоритм симплекс-метода для задачи на минимум
- •3.3. Алгоритм симплекс-метода для задачи на максимум
- •На шаге 2::
- •На шаге 4: .
- •3.4. Пример
- •3.5. Метод искусственного базиса
- •3.6. Пример
- •3.7. Двойственный симплекс-метод
- •3.8. Пример
- •4. Двойственность в лп
- •4.1. Постановка задачи
- •4.2. Пример
- •4.3. Теоремы двойственности
- •4.4. Пример
- •4.5. Пример
- •5. Метод Гомори
- •5.1. Постановка задачи цлп
- •5.2. Алгоритм метода Гомори
- •Замечания.
- •5.3. Пример
- •6. Транспортная задача лп
- •6.1. Постановка задачи
- •6.2. Построение опорного плана транспортной задачи
- •6.3. Метод северо-западного угла
- •6.4. Пример
- •6.5. Метод минимальной стоимости
- •6.6. Пример
- •6.7. Метод потенциалов
- •6.8. Вычислительная схема метода потенциалов
- •6.9. Пример
- •7. Задания для самостоятельной работы
- •7.1. Построить математическую модель задачи
- •7.2. Привести задачу лп к канонической форме
- •Список литературы
Графическое решение задач лп
2.1. Каноническая форма задачи лп
Для численного решения задачи ЛП требуется предварительно привести ее к каноническому виду:
………………………
Каноническая форма (КФ) задачи характеризуется следующими тремя признаками:
однородная система ограничений в виде системы уравнений;
однородные условия неотрицательности, распространяющиеся на все переменные, участвующие в задаче;
минимизация (максимизация) целевой функции.
Известно, что для произвольной задачи ЛП можно построить эквивалентную ей каноническую задачу ЛП (эквивалентность двух задач означает, что оптимальному решению одной задачи соответствует оптимальное решение другой)[1,2,3].
2.2 Пример
Привести задачу к КФ на минимум.
В данной задаче нарушены все три признака КФ.
Начнем с преобразования смешанной системы ограничений в систему уравнений. Для этого введем в первое и второе ограничения неотрицательные переменные y1, y2, которые называютсядополнительнымиилислабыми. В результате система ограничений запишется в следующем виде:
Условия неотрицательности не выполняются только для переменной x2. Для приведения задачи к однородным условиям неотрицательности можно воспользоваться двумя приемами.
Первый прием. Представим переменнуюx2в виде разности двух неотрицательных переменных:После преобразования системы ограничений и целевой функции получим задачу
Второй прием.Найдем из какого-либо уравнения переменнуюx2. Пусть из первого уравнения. Подставим это выражение во все уравнения и в целевую функцию, исключив таким образом переменнуюx2из задачи. Получим
3. Переход к задаче минимизации целевой функции Lосуществляется путем введения новой функциииз равенства
в первом случае,
во втором случае.
2.3. Общие рекомендации к графическому решению задач лп
1. Графически могут решаться [1]:
задачи, заданные в произвольной форме, содержащие не более двух переменных;
задачи, заданные в канонической форме, с числом свободных переменных ;
задачи в произвольной форме записи, которые после приведения к канонической форме будут содержать не более двух свободных переменных.
2. Основной формой для графического решения является 1-й тип задач. Поэтому, если встречается 2-й или 3-й тип задач, то предварительно их модель должна быть приведена к первому типу.
3. Решение задач 1-го типа выполняется в два этапа:
этап 1 -- построение области допустимых решений;
этап 2 -- построение в допустимой области оптимального решения.
4. При построении области допустимых решений может встретиться один из трех случаев:
а) пустая область – задача не имеет решения из-за несовместности системы ограничений в области допустимых решений;
%\input{p2.pic}
б) выпуклый многоугольник – задача всегда имеет оптимальное решение;
%\input{p1.pic}
в) неограниченная выпуклая многогранная область – в зависимости от направления вектора c(вектора коэффициентов целевой функцииL) задача может иметь или не иметь решение. Последнее связано с неограниченностью целевой функции в области допустимых решений.
%\input{p6.pic}
5. Если оптимальное решение существует, то возможен один из трех исходов:
а) оптимальное решение единственное и совпадает с одной из вершин области;
%\input{p3.pic}
б) оптимальные решения соответствуют всем точкам отрезка, соединяющего две вершины областии:
%\input{p4.pic}
в) оптимальные решения соответствуют всем точкам допустимого луча, исходящего из вершины области :
%\input{p5.pic}