- •2) Переход от общей (стандартной) формы злп к канонической.
- •Переход от канонической формы к стандартной.
- •1.1.3. Контрольные вопросы:
- •1.1.4. Варианты индивидуальных заданий:
- •1.2 Графический метод решения задач
- •1.2.2. Теоретическая часть:
- •1.2.3. Контрольные вопросы:
- •1.2.4. Варианты индивидуальных заданий:
- •1.3 Симплекс-метод решения задач линейного программиро-вания
- •1.3.2. Теоретическая часть
- •1.3.2.1. Симплекс-метод
- •1.3.2.2. Cимплекс-метод для неполного базиса (м-метод).
- •1.3.3. Контрольные вопросы:
- •1.3.4. Варианты индивидуальных занятий
- •1.4 Двойственность в линейном программировании
- •1.4.2. Теоретическая часть:
- •1.4.2.1. Общая модель задачи
- •1.4.2.2. Решение злп с помощью графического анализа двойственной задачи
- •1.4.3. Контрольные вопросы:
- •1.4.4. Варианты индивидуальных заданий.
- •1.5 Транспортная задача (т-задача)
- •1.5.2. Теоретическая часть:
- •1.5.2.1. Алгоритм решения т-задачи.
- •1.5.2. Примеры решения т-задачи.
- •1.5.3. Контрольные вопросы.
- •1.5.4. Варианты индивидуальных заданий:
- •1.6 Целочисленное программирование
- •1.6.2. Теоретическая часть: Описание метода отсечений (метода Гомори).
- •1.6.3. Контрольные вопросы:
- •1.6.4. Варианты индивидуальных заданий.
- •2.1.2.2. Метод Франка-Вулфа решения задач квадратичного программирова-
- •2.2 Контрольные вопросы.
- •2.3. Индивидуальные задания.
1.2 Графический метод решения задач
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЗЛП)
1.2.1. Цель: научиться строить область допустимых решений (ОДР) задачи, ли-нию уровня и находить решение ЗЛП графическим способом.
1.2.2. Теоретическая часть:
Графический метод основан на геометрической интерпретации ЗЛП и применим:
- к задачам в стандартной форме записи, содержащим не более двух перемен-
ных,
-
задачам в канонической форме с числом свободных переменных n-r2,
-
задачам общего вида, которые после приведения к канонической форме будут
содержать не более двух свободных переменных.
Основной формой для графического решения ЗЛП является стандартная, к кото-рой должны быть предварительно приведены общая и каноническая модели.
Решение выполняется в два этапа:
-
построение области допустимых решений (ОДР)
-
нахождение в ней оптимального решения.
При построении ОДР возможны три случая:
-
ОДР пустая (ЗЛП не имеет решения из-за несовместимости системы ограниче-ний в ОДР);
-
выпуклый многоугольник;
-
неограниченная выпуклая область.
ЗЛП может иметь единственное оптимальное решение, совпадающее с одной из вершин области, или бесчисленное множество оптимальных решений, соответствую-щее всем точкам отрезка, соединяющего две вершины ОДР, или не иметь решения, ес-ли происходит неограниченное возрастание или убывание линейной формы в ОДР. В случае неограниченной ОДР среди множества оптимальных решений может оказаться только одно, совпадающее с вершиной области.
ОДР представляет общую часть неравенств, которые определяют условия ограни-ченности и неотрицательности задачи. Она ограничена прямыми, описываемыми урав-нениями, которые получены преобразованием неравенств. Пересечение этих прямых определяет вершины многоугольника или многоугольной неограниченной области. Це-левая функция ЗЛП геометрически представляет собой линию уровня на плоскости L, которую можно перемещать параллельно самой себе в направлении нормали, задавае-мой вектором С = (с1,с2). Пересечение линии уровня с ОДР в том ее положении, когда дальнейшее перемещение дает пустое пересечение, и будет соответствовать единствен-ному оптимальному решению ЗЛП (или множеству).
Пример: Решить задачу:
2x1 x2 max,
x1 x2 2,
x1 x2 1,
0 x2 4,
x1 0.
Рис.1. Построенная ОДР задачи.
Так как задача выражена в общей форме и содержит две переменные, то ее можно решать графическим способом.
Областью допустимых решений задачи является выпуклый многоугольник ABCD (см. рис.1), сторона |AB| которого построена на основании первого неравенства систе-мы ограничений, сторона |BC| - четвертого неравенства, |CD| - третьего, а |DA| - второ-го. Линия уровня движется в направлении нормали, заданной вектором С=(2;-1), коор-динатами которого являются коэффициенты ЦФ(целевой функции). Направление дви-жения линии уровня на рисунке показано стрелкой. Последней точкой ОДР, в которой оказывается линия уровня L, двигаясь в заданном направлении, является точка D=(5; 4). Это и будет решением.
Значит, х1=5, а х2=4, т.е. хопт=(5; 4). Подставим полученные значения в ЦФ L(xопт) = 2 5 4 6 .