РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ОСНОВЕ ВЫЧИСЛИТЕЛЬНЫХ МЕТОДОВ, НАЧЕРТАТЕЛЬНОЙ ГЕОМЕТРИИ МНОГОМЕРНОГО ПРОСТРАНСТВА И ТВЕРДОТЕЛЬНОГО                    МОДЕЛИРОВАНИЯ

Болотов В.П.
Различные по форме фигуры на плоскости и в пространстве могут быть областями ограничений целевой функции (ЦФ) в линейном и нелинейном программировании.

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

Пусть требуется структурировать область, ограниченную следующей системой неравенств:

x/100 + y/170 -1 < 0,  (1)
x/140 + y/120- 1  < 0,  (2)
x > 0,    (3)
y > 0.    (4)

Уравнения (1,2) можно представить как уравнения прямых в отрезках (рис.1):

x/100 + y/170 = 1,
x/140 + y/120 = 1.

Уравнения (3, 4) представляют  оси координат.
Решая уравнения (1,2), можно найти точку р4  и свести область ограничений к 4-х угольнику. Однако, поступим следующим образом. Используя операции сканирования при изменяющемся уi и сравнений, можно осуществить перебор точек в определяемой области ограничений. Такой перебор (рис.2,а) в системе "Вектор" можно выполнить с помощью двух рекурсивных циклов.

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

Пусть целевая функция задана следующим уравнением:

f(x,y) = x+y --> max.

Если ЦФ приравнять какому-либо числу, например, f(x,y)= x+y=200, то ее также можно записать уравнением прямой в отрезках x/200 + y/200 =1 и изобразить в координатной системе x,y отрезком прямой (рис.3).

Известно, что наибольшее (или наименьшее) значение функция f будет иметь  при тех значениях x и y области ограничений, когда точка (ребро) этой области будет находиться ближе (или дальше) от отрезка прямой ЦФ.

Условие зависимости расстояния s1 от отрезка прямой ЦФ до контура области ограничений можно отобразить графиком (рис. 3). Максимум на этом графике и даст искомую точку, в которой ЦФ будет максимальной.

Кроме того, вычисляя еще и значения ЦФ, можно отобразить ее графически также непосредственно над областью (контуром) ограничений.

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

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

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

Упражнение. Используя теоретико-множественные операции в системе "CG-Вектор", смоделируйте область ограничений, представленную следующей системой уравнений-неравенств:

x > 0,    (5)
y > 0,    (6)
x/100+y/50+z/150-1 < 0,  (7)
x/150+y/100+z/100-1 <0.  (8)

Схема решения:

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

2) задаем два полупространства, у которых вектора нормалей определяются из соотношений: {1/a,  1/b, 1/c } или [bc, ac, ab] плоскостей (7) и (8);

3) пересечения параллелепипеда и полупространств в одной конъюнкции и определят искомую фигуру.