- •Математические модели задач лп
- •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.4. Пример
Решить графически задачу ЛП, заданную в канонической форме:
(6)
(7)
(8)
Число уравнений задачи m=3, число неизвестныхn=5. Тогдаn-m=2 и задача может быть сведена к задаче на плоскости относительно свободных переменных.
Возьмем в качестве базисных переменныеи выразим их черезсвободные (небазисные переменные):
(9)
По условию (8) переменные могут принимать только неотрицательные значения, т.е. допустимой областью задачи ЛП (6) - (8) будет область, определяемая условиями (8),(9), или
(10)
Чтобы получить задачу ЛП относительно переменных x1,x2, подставим значения базисных переменных (9) в целевую функцию (6). В результате получим
(11)
Задача (10), (11) эквивалентна задаче (6) - (8), поэтому решая графически задачу (10), (11), получим решение задачи (6) - (8).
Этап 1.Построение допустимой области.
Каждое из неравенств (10) определяет некоторую полуплоскость :
Так, неравенство определяет правую полуплоскость. Неравенствоопределяет полуплоскость, лежащую по ту сторону от прямой, где. Подставляя значенияв это неравенство, получим 0>-2, значит, координаты (0,0) удовлетворяют первому неравенству (10) и область решений этого неравенства включает начало координат. Аналогично определяют полуплоскости остальных неравенств (10).
На рисунке прямые, соответствующие условию , отмечены цифрой в скобках.
Получили допустимую область M– выпуклый пятиугольник OABCD.
Этап 2.В допустимой областиMнаходим оптимальное решение.
Строим прямую и определяем направление возрастания функции, это направление вектора . Перемещая прямуюLпараллельно самой себе в направлении векторадо тех пор, пока она будет сохранять общие точки с областью допустимых решений, найдем, что в крайнем возможном положении прямаяLпройдет через точку. Этому положению прямойLсоответствует значение. Для нахождения координат точкинеобходимо совместно решить систему уравнений граничных прямых, на которых лежит точка:
В результате получаем искомое оптимальное решение . Подставляя значенияив целевую функцию и в равенства (9), получим оптимальное значение целевой функциии оптимальное решение
3. Численные методы решения задач лп
3.1. Симплекс – метод
Рассмотрим задачу ЛП в канонической форме:
(12)
……………………… (13)
(14)
Будем предполагать, что (иначе, умножим соответствующее уравнение на -1), уравнения системы (13) линейно независимы,m<nи система (13) -(14) совместна.
При сделанных предположениях можно выбрать mнеизвестных (к примеру) таких, чтобы определитель, составленный из коэффициентов при этих неизвестных, не обращался в ноль. Тогда задача (12) - (14) может быть приведена к виду, который называетсяспециальной формой задачи ЛП:
…………………………………….. (15)
Одно из допустимых решений этой задачи можно найти, если переменные положить равными нулю. Такое решение называетсядопустимым базисным решением. Оно имеет вид:
Этому решению соответствует значение целевой функции . Переменныеназываютбазисными, набор переменныхназываютбазисом, а переменныеназываютнебазиснымиилисвободными. Число возможных базисов в задаче размерностиnсmограничениями не превосходит величину.
Известно, что каждому допустимому базисному решению соответствует вершина многоугольника допустимых решений и оптимальное решение задачи (при условии его существования) достигается в одной из вершин многоугольника. Поэтому оптимальное решение задачи ЛП находится среди допустимых базисных решений. Существуют рациональные способы последовательного перебора допустимых базисных решений, которые позволяют рассматривать не все допустимые базисные решения, а их минимальное число. К таким методам относится симплекс-метод [1,2,3].