Лекции по "Развитию операционных систем"

Лекция 17.

 

п.16.  Линейное программирование.

 

16.3.  Геометрическая интерпретация ЗЛП.

 

Геометрическая интерпретация оптимизационных задач дает возможность нагляд-но представлять их структуру, выявить особенности и открывает пути исследования более сложных свойств. Задача линейного программирования всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в пространствах, размерность которого больше трех, графическое решение, вообще говоря, невозможно.

Случай двух переменных не имеет особого практического значения, однако его рассмотрение проясняет свойства ОЗЛП, приводит к идее решения, делает геометрически наглядными способы решения и пути их практической реализации.

Пусть дана задача: найти - план задачи, если

                                                      (16.3.1.)

                                                     (16.3.2.)

                                                         (16.3.3.)

Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограни-чений (16.3.2.) и (16.3.3.) задает на плоскости некоторую полуплоскость. Полуплос-кость – выпуклое множество. Пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (16.3.1.) - (16.3.3.) есть выпуклое множество.

На рисунке представлены возможные случаи области допустимых решений задачи линейного программирования.

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП – непустое множество, например, многоугольник .

Выберем произвольное значение целевой функции . Получаем . Это уравнение прямой линии. В точках прямой MN целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве (16.3.1.) Z пара-метром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

Возникает вопрос: как установить направление возрастания (убывания) целевой функции?

Найдем частные производные целевой функции по и :

                                                               (16.3.4.)

                                                              (16.3.5.)

Частная производная (16.3.4.) [(16.3.5.)] функции показывает скорость ее возрас-тания вдоль данной оси. Следовательно, и – скорости возрастания Z соответственно вдоль осей и . Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

.

Вектор ( ) указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.

Вектор перпендикулярен к прямой семейства .

 

 

 

Графический метод решения ЗЛП.

 

Из геометрической интерпретации элементов задачи линейного программирования следует порядок ее графического решения.

1.  С учетом системы  ограничений строим область допустимых  решений W.

2.  Строим вектор  наискорейшего возрастания целевой функции – век-тор градиентного направления.

3.  Проводим произвольную  линию уровня  (проще всего провести , перпендикулярную к вектору ).

4.  При решении задачи  на максимум перемещаем линию уровня в направ-лении вектора так, чтобы она касалась области допустимых решений в ее крайнем поло-жении (крайней точке). На рисунке выше – это точка . В случае решения задачи на минимум линию уровня перемещаем в антиградиентном направлении. На рисунке выше – это точка .

5.  Определяем оптимальный  план  и экстремальное значение целевой функции .

 

В результате решения задачи линейного программирования возможны следующие случаи оптимального плана, которые представлены на рисунке.

     (а)  оптимальный план  единственный: линия уровня и область допустимых решений W в разрешающем положении имеют одну общую точку;

     (б)  оптимальных планов  бесчисленное множество: в разрешающем  положении линия уровня проходит  через сторону области допустимых  решений;

     (в), (г)  целевая функция не ограничена: линия уровня, сколько бы ее не перемещали, не может занять разрешающего положения; только в случае (в) возможно решение задачи на минимизацию целевой функции;

     (д)  область допустимых  решений состоит из единственной  точки, где целевая функция достигает одновременно и максимального, и минимального значений;

     (е)  задача не имеет  решения: область допустимых решений  – пустое множество, т.е. система  ограничений задачи несовместна.

 

Пример 16.5.  Решить ЗЛП

,     .

Решение.  Для построения области допустимых решений строим в системе соответствующие данным ограничениям-неравенствам граничные прямые:

.

Находим полуплоскости, в которых выполняются данные неравенства. Для этого вследствие выпуклости любой полуплоскости достаточно взять произвольную точку, через которую не проходит соответствующая граничная прямая, и проверить, удовлетворяет ли эта пробная точка ограничению-неравенству. Если удовлетворяет, то данное неравенство выполняется в полуплоскости, содержащей пробную точку. В противном случае берется полуплоскость, не содержащая пробной точки. В качестве пробной точки часто удобно брать начало координат . Для нашего примера область допустимых решений – множество точек четырехугольника ABCD.

 

Координаты точки C можно найти из системы

,

откуда . Таким образом, .

,

Пример 16.6.  При производстве продукции П1 и П2 используют четыре группы оборудования A, B, C и D. На выпуск единицы продукции П1 расходуется 1; 0,5; 2 и 0 ед. времени оборудования A, B, C и D соответственно, а на выпуск продукции П2 – 1; 1; 0 и 2 ед. времени оборудования. Фонд рабочего времени оборудования группы A – 18 ед. времени; B – 12 ед.; C – 24 ед. и D – 18 ед. Предприятие реализует единицу продукции П1 по цене 40 ден. ед., П2 – 60 ден. ед. Найти план выпуска продукции, при котором выручка предприятия будет максимальной.

Решение.  1)  Запишем условие задачи в виде таблицы.

 

Вид оборудования	Продукция		Фонд рабочего времени, ед.
	П1	П2
A B С D	1 0,5 2 0	1 1 0 2	18 12 24 18
Цена единицы продукции, ден. ед.	40	60

 

Пусть - объем выпускаемой продукции вида П1, - объем выпуска продукции П2, т.е. - план выпуска продукции предприятием. Прибыль, которую получает предприятие от реализации продукции, стремиться максимизировать, т.е. целевая функ-ция имеет вид

.

На производство двух видов продукции будет затрачено единиц времени оборудования группы A; - оборудования B; - оборудования С; - обору-дования D. При этом, учитывая фонд рабочего времени каждого вида оборудования, получаем системы ограничений:

.

По смыслу задачи все переменный .

Таким образом, получаем экономико-математическую модель, которая является задачей линейного программирования. Итак,

;

;

.

2)  Так как план  выпуска продукции содержит две  переменные, то ЗЛП можно решить графическим способом.

Для построения области допустимых решений строим в системе соответст-вующие данным ограничениям-неравенствам граничные прямые:

.

 

 

 

Область допустимых решений – множество точек многоугольника OABCD.

Строим вектор и линию уровня Z=0. Параллельным перемещением прямой Z=0 находим крайнюю точку C, в которой целевая функция достигает максимум. Координаты точки C определяются системой

,

откуда .

Следовательно, (ден. ед.).

,

Графическим методом можно решить ЗЛП с переменными, если в ее канонической записи число неизвестных n и число линейно независимых уравнений m связаны соотношением . В этом случае каноническую форму задачи преобразовывают в симметричную, которая будет содержать не более двух переменных. Решая эту задачу графически, находят два компонента оптимального плана. Подставляя их в ограничения задачи, определяют и остальные компоненты.