Графический метод математического программирования

Рис. 7.2.3. Решение задачи 7.2 для

Исходя из рисунка 7.2.3, видно, что оптимальное решение задачи 7.2 при находится так же в точке А, то есть А ().

Значит, наибольшее значение функции F при равно

Так как значит следующее значение параметра . Подставим данное значение в систему ограничений задачи, получим:



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

Рис. 7.2.4. Решение задачи 7.2 для

Исходя из рисунка 7.2.4, видно, что оптимальное решение задачи 7.2 при находится так же в точке А, то есть А (). Значит, наибольшее значение функции F при равно

Ответ:

При оптимальное решение задачи находится в точке А (), при этом

При оптимальное решение задачи находится в точке А (), при этом

При оптимальное решение задачи находится в точке А (), при этом

При оптимальное решение задачи находится в точке А (), при этом

Таким образом, при всех исследуемых значениях параметра t оптимальное решение остается в точке А, при этом .

Теперь рассмотрим графический метод задач параметрического программирования, в случае задачи (7.7) -- (7.9), то есть задачи, в которой от параметра зависят свободные члены системы ограничений и коэффициенты целевой функции. Рассмотрим на примере.

Пример 7.3.

Решить задачу параметрического программирования:

Решение:

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

Решая данную систему, находим, что Рассмотрим нашу задачу при t равном левой границе полученного промежутка:

Решение данной задачи представлены на рисунке 7.3.1.

Рис. 7.3.1. Решение задачи 7.3 для



Исходя из рисунка видно, что оптимальное решение находится в точке А, чтобы найти координаты точки А в общем виде решим систему:

Решая данную систему, находим, что , то есть точка А в общем виде имеет следующие координаты: А( Рассмотрим поведение точки А при увеличении параметра t. Исключим из системы уравнений

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

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

Придавая параметру t значения, близкие к , нетрудно установить, что с увеличением параметра t вектор вращается против часовой стрелки. Выясним, при каком значении t вектор будет ортогонален прямой, соответствующей второму ограничению системы исходной задачи. Из условия ортогональности двух прямых находим, что



При исходная задача примет вид:

Графическое решение задачи при представлено на рисунке 7.3.2.

Рис. 7.3.2. Решение задачи 7.3 для

Как мы видим, многоугольником решений является четырехугольник OABC. Так как вектор лежит на прямой, перпендикулярной прямой АВ, то координаты любой точки, принадлежащей отрезку [A; B], где

А (;), В () представляют оптимальное решение задачи при

При всех оптимальное решение находится в точке В (0; -9 + 5t). В этом случае

Графическое решение исходной задачи при t = 2 представлено на рисунке 7.3.3, сама задача при t = 2 примет вид:

Рис. 7.3.3. Решение задачи 7.3 для

При всех оптимальное решение находится в точке А (30 - 14t; 6 - 2t), при этом

Ответ:

При оптимальное решение находится в точке А (30 - 14t; 6 - 2t), при этом

Координаты любой точки, принадлежащей отрезку [A; B], где А (;), В () представляют оптимальное решение задачи при при этом

При всех оптимальное решение находится в точке В (0; -9 + 5t). В этом случае



Глава II. Теоретические сведения о графическом способе решения задач математического программирования в трехмерном пространстве

§1. Решения задач линейного программирования графическим методом в трехмерном пространстве

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

где коэффициенты целевой функции , коэффициенты в системе неравенств, определяющих многогранник решений , свободные члены в системе неравенств, определяющих многогранник решений (.

Так же уместна здесь и теорема:

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

Итак, каким же образом решают задачи линейного программирования графическим методом в трехмерном пространстве:

1. Определяем многогранник решений:

· Строим плоскость ;

· Строим плоскость ;

· …

· Строим плоскость ;

· Определяем прямые пересечения данных плоскостей;

· Определяем точки пересечений полученных прямых.

2. Строим поверхность, определяемую целевой функцией, а так же вектор = (c₁; c₂; c₃).

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

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

Пример 1.1. Решить графическим методом задачу математического программирования:

,

Решение:

Итак, воспользуемся выше приведенным алгоритмом.

Сначала определим многогранник решений. Итак, построим плоскость определяемую выражением , обозначим ее . Так как , то найдем прямые, по которым плоскость пересекает плоскости YOZ, ZOX, XOY. Если плоскость пересекает плоскость YOZ, то значит переменная , подставим ее в уравнение плоскости . Тогда плоскость пересекает плоскость YOZ по прямой Если плоскость пересекает плоскость ZOX, то значит переменная , подставим ее в уравнение плоскости . Тогда плоскость пересекает плоскость ZOX по прямой Если плоскость пересекает плоскость XOY, то значит переменная , подставим ее в уравнение плоскости . Тогда плоскость пересекает плоскость XOY по прямой . Получаем следующую плоскость (рис. 1.1.1):

Рис. 1.1.1. Плоскость .

Аналогично рассуждая для плоскостей и получим, что плоскость пересекает плоскость YOZ по прямой , плоскость ZOX по прямой , плоскость XOY по прямой , а плоскость пересекает плоскость YOZ по прямой , плоскость ZOX по прямой плоскость XOY по прямой (рис.1.1.2 и 1.1.3).



Теперь объединяем получившиеся плоскости в один рисунок, для определения многогранник решений (рис. 1.1.4).

Рис. 1.1.4. Многогранник решений задачи 1.1

Примерный многогранник мы видим, осталось определить вершины многогранника. Точки A, B и Е определяются сразу из построения, то есть A(2; 0; 0), B(0; 0; 2), Е(0; 1,5; 0). Остальные найдем пересечением соответствующих прямых. Итак, точка С является точкой пересечения прямых и , составим систему из этих двух уравнений:



Решая данную систему, мы получаем координаты точки С(0 ;1; 2,5). Рассмотрим точку D, она является пересечением прямых и Аналогично, составляя систему и решая ее, мы получим координаты точки D(0; . Точка F является точкой пересечения прямых и тогда ее координаты F(3; 2;0). Точка G является общей точкой для всех плоскостей, найдем ее, решив систему:

.

Итак, получили многогранник решений (рис. 1.1.5)



Рис. 1.1.5. Многогранник решений задачи 1.1

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

1. Используя вышеописанный алгоритм, пункты 2 и 3;

2. Подсчитав значение целевой функции в каждой вершине многоугольника.

Мы используем второй способ. Итак, найдем значение целевой функции в вершинах многогранника:

точка A(2; 0; 0): ;

точка B(0; 0; 2): ;

точка С(0 ;1; 2,5): ;

точка D(0; : ;

точка Е(0; 1,5; 0): ;

точка F(3; 2;0): ;

точка .



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

Ответ: в точке целевая функция принимает максимальное значение .

§2. Решения задач нелинейного программирования графическим методом в трехмерном пространстве

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

(2.1)

. (2.2)

Неравенства (2.2) и целевая функция (2.1) представляют собой некоторые известные функции трех переменных, где хотя бы одна из них не линейна.

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

1. Определяем область решений:

· Строим плоскость ;

· Строим плоскость ;

· …

· Строим плоскость ;

· Определяем прямые пересечения данных поверхностей;

· Определяем точки пересечений полученных прямых.

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

Применив следующий алгоритм, решим задачу.

Пример 2.1. Решить графическим методом задачу математического программирования:

,

Решение:

Воспользуемся выше приведенным алгоритмом.

Сначала определяем область решений. Рассмотрим первое неравенство, обозначим поверхность . Данное уравнение определяет параболоид, определим кривые, по которым параболоид пересекает плоскости ZOY, XOZ, XOY. Для того чтобы найти кривую, по которой параболоид пересекает плоскость ZOY, обнуляем координату . Получим: Данное уравнение определяет ветвь параболы, расположившейся в плоскости ZOY. Для того чтобы найти кривую, по которой параболоид пересекает плоскость XOZ, обнуляем координату . Получим: Данное уравнение определяет ветвь параболы, расположившейся в плоскости XOZ. Для того чтобы найти кривую, по которой параболоид пересекает плоскость XOY, обнуляем координату . Получим: . Это уравнение будет верным только при , то есть поверхность касается плоскость XOY в точке О(0; 0; 0). Зная, что , можем построить часть параболоида, удовлетворяющей нашей системе (рис. 2.1.1).



Рис. 2.1.1. Поверхность

Теперь рассмотрим второе неравенство, обозначим поверхность . Данное уравнение определяет эллипсоид, определим кривые, по которым эллипсоид пересекает плоскости ZOY, XOZ, XOY. Для того чтобы найти кривую, по которой эллипсоид пересекает плоскость ZOY, обнуляем координату . Получим:

Данное уравнение определяет часть эллипса, расположившегося в плоскости ZOY. Для того чтобы найти кривую, по которой параболоид пересекает плоскость XOZ, обнуляем координату . Получим:

Данное уравнение определяет часть окружности с центром в точке О и радиусом , расположившейся в плоскости XOZ. Для того чтобы найти кривую, по которой параболоид пересекает плоскость XOY, обнуляем координату . Получим:



Данное уравнение определяет часть эллипса, расположившегося в плоскости XOY. Зная, что , можем построить часть эллипсоида, удовлетворяющей нашей системе (рис. 2.1.2).

Рис. 2.1.2. Поверхность

Теперь объединяем получившиеся плоскости в один рисунок, для определения области решений (рис. 2.1.3).

Рис. 2.1.3.Область решений задачи 2.1



Итак, областью решений является область OACB (Рис. 2.1.4).

Рис. 2.1.4.Область решений задачи 1

Теперь найдем координаты точек пересечения кривых, которые являются вершинами нашей области решений. Из рисунка 4 мы можем сразу определить 2 точки, точка О(0; 0; 0) и точка С(0; 0; ), остается найти точку А и точку В. Точка А является точкой пересечения кривых и

Решая данную систему получим координаты точки А(. Аналогично, находим координаты точки В(0; 1; 2).

Теперь построим поверхность целевой функции. Поступим следующим образом, сначала найдем прямые, по которым поверхность целевой функции пересекает плоскости ZOY и XOZ. Чтобы найти прямую, по которой поверхность целевой функции пересекает плоскость ZOY, обнулим переменную , получим:



.

Графиком этого уравнения является прямая, расположенная в плоскости XOZ (рис. 2.1.5).

Рис. 2.1.5. Плоскость ZOY с целевой функцией

Чтобы найти прямую, по которой поверхность целевой функции пересекает плоскость XOZ, обнулим переменную , получим:

Графиком этого уравнения является прямая, расположенная в плоскости XOZ (рис. 2.1.6).



Рис. 2.1.6. Плоскость ZOХ с целевой функцией

Рассматривая полученные рисунки, можно заметить, что при перемещении плоскости вдоль вектора , мы получим точку С, в которой целевая функция будет иметь наибольшее значение, а именно .

Ответ: в точке С(0; 0; ) целевая функция принимает максимальное значение .



Глава III. Решение задач математического программирования графическим способом в двумерном пространстве

§1. Графический способ решения задач линейного программирования

Задача 1.1.

Найти наибольшее значение функции L = -x₁ + 2x₂ при ограничениях:

Решение:

Воспользуемся алгоритмом данном в главе I в §3.

Строим прямые, уравнения, которых получаются в результате замены в ограничениях задачи знаков неравенств на знаки точных равенств. Получим прямые: l₁: x₂ = - , l₂: x₂ = 1 - x₁, l₃: x₂ = 1 + , l₄: x₂ = 3 - . Затем находим полуплоскости, определяемые каждым из ограничений задачи. Получаем многоугольник решений - ABCD. Строим вектор = (-1; 2), затем прямую: l₅: -x₁ + 2x₂ = h, проходящую через многоугольник решений;

Передвигаем прямую l₅: -x₁ + 2x₂ = h в направлении вектора (рис. 1.1), в результате чего находим точку В (4; , в которой целевая функция принимает максимальное значение: L = -.



Рис. 1.1. Решение задачи 1.1

Ответ: в точке В (4; целевая функция L = -x₁ + 2x₂ принимает наибольшее значение: L = -.

Задача 1.2.

Найти наибольшее значение функции L = 3x₁ - 4x₂ при ограничениях:

Решение:

Воспользуемся алгоритмом данном в главе I в §3.

Строим прямые, уравнения, которых получаются в результате замены в ограничениях задачи знаков неравенств на знаки точных равенств. Получим прямые: m₁: x₂ = - , m₂: x₂ = - , m₃: x₁ = 0, m₄: x₁ = 6. При построении прямых находим полуплоскости, определяемые каждым из ограничений задачи. В ходе чего получим многоугольник решений - ABCDЕ. Строим вектор = (3; -4). Затем строим прямую целевой функции: m₅: 3x₁ - 4x₂ = h, проходящую через многоугольник решений. Передвигаем прямую m₅: 3x₁ - 4x₂ = h в направлении вектора , в результате чего находим точку D (6; , в которой целевая функция принимает максимальное значение: L = 18.

Рис. 1.2. Решение задачи 1.2

Ответ: в точке D (6; целевая функция L = 3x₁ - 4x₂ принимает наибольшее значение: L = 18.

Задача 1.3.

Найти наибольшее значение функции L = 8x₁ - 2x₂ при ограничениях:

Решение:

Воспользуемся алгоритмом данном в главе I в §3.

Строим прямые, уравнения, которых получаются в результате замены в ограничениях задачи знаков неравенств на знаки точных равенств. Получим прямые: n₁: x₂ = , n₂: x₂ = 3x₁ - 3, n₃: x₂ = 6, n₄: x₂ = 18 - 2х₁, n₅: x₂ = 4х₁ -24. Находим полуплоскости, определяемые каждым из ограничений задачи. В ходе чего находим многоугольник решений - ABCDЕ. Затем строим вектор = (8; -2). Потом построим прямую целевой функции: n₆: 8x₁ - 2x₂ = h, проходящую через многоугольник решений. Передвигаем прямую n₆: 8x₁ - 2x₂ = h в направлении вектора , в результате чего находим отрезок DE. В каждой точке отрезка DE целевая функция принимает максимальное значение: L = 48.

Рис. 1.3. Решение задачи 1.3

Ответ: Целевая функция L = 3x₁ - 4x₂ принимает наибольшее значение L = 48 в любой точке отрезка DE.

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



Задача 1.4.

Найти наибольшее значение функции L = -x₄ + x₅ при ограничениях:

Решение:

Путем отбрасывания переменных х₁, х₂, х₃ из системы уравнений, замены их неравенствами и выражения отбрасываемых переменных в целевой функции через х₄ и х₅, задача может быть приведена к виду:

L = -x₄ + x₅

Теперь можно воспользоваться алгоритмом данном в главе I в §3.

Построим прямые, уравнения, которых получаются в результате замены в ограничениях задачи знаков неравенств на знаки точных равенств. Получим прямые: m₁: x₅ = , m₂: x₅ = 2 + 2х₄, m₃: x₅ = 3 - 3х₄.. В ходе построения определяем полуплоскости, соответствующие каждым из ограничений задачи. Получаем многоугольник решений - ABCD. Затем строим вектор = (-1; 1) и прямую целевой функции: m₄: -x₄ + x₅ = h, проходящую через многоугольник решений. Передвигаем прямую m₄: -x₄ + x₅ = h в направлении вектора , в результате чего находим точку В (0; , в которой целевая функция принимает максимальное значение: L = 2.



Рис. 1.4. Решение задачи 1.4

Ответ: в точке В (0; целевая функция L = -x₄ + x₅ принимает наибольшее значение: L = 2.

§2. Графический способ решения задач нелинейного программирования

Задача 2.1.

Найти наибольшее и наименьшее значение функции F = + (x₂ - 4)² при ограничениях:

Решение:

Воспользуемся алгоритмом решения задачи данном в главе I в §4.

Областью допустимых решений задачи является треугольник АВС, который был получен из ограничений системы, путем замены в ограничениях задачи знаков неравенств на знаки точных равенств. Полагая значение целевой функции равное некоторому числу h, получаем линии уровня, а именно окружности + (x₂ - 4)² = h с центром в точке Е(3; 4). С увеличением (уменьшением) числа h значения функции F соответственно увеличиваются (уменьшаются).

Проводя из точки Е окружности разных радиусов, видим, что минимальное значение целевая функция принимает в точке D, в которой окружность касается области решений. Для определения координат этой точки воспользуемся равенством угловых коэффициентов прямой 10x₁--х₂ = 8 и касательной к окружности в точке D.

Из уравнения прямой х₂ = 10х₁ - 8 видим, что ее угловой коэффициент в точке D равен 10. Угловой же коэффициент касательной к окружности в точке D определим как значение производной функции х₂ от переменной х₁ в этой точке. Рассматривая х₂ как неявную функцию переменной х₁ и дифференцируя уравнение окружности, получим:

2(х₁ - 3) + 2(х₂ - 4) = 0 откуда -(х₁ - 3) / (х₂ - 4)

Приравнивая найденное выражение числу 10, получаем одно из уравнений для определения координат точки D. Присоединяя к нему уравнение прямой, на которой лежит точка D, имеем систему:

Решая данную систему получим х₁ = 123/101, х₂ = 422/101. Таким образом F_min = 324/101.

Как видно из рис. 2.1, целевая функция принимает максимальное значение в точке С (2; 12). Ее координаты определены путем решения системы уравнений прямых, на пересечении которых находится точка С. Таким образом, максимальное значение функции F_max =65.



Рис. 2.1. Решение задачи 2.1

Ответ: Минимальное значение целевая функция принимает в точке D(123/101; 422/101) равное F_min = 324/101, а максимальное значение она принимает в точке С(2;12) равное F_max =65.

Задача 2.2.

Найти наибольшее значение функции F = + 4x₂ при ограничениях:

Решение

Областью допустимых решений задачи является область АВСЕ, которая была получена из ограничений системы, путем замены в ограничениях задачи знаков неравенств на знаки точных равенств.

Затем строим вектор = (-3; 4) и прямую целевой функции: + 4x₂ = h, проходящую через многоугольник решений.

Передвигая прямую целевой функции вдоль вектора получим максимальное значение в точке В, в которой прямая касается окружности . Для определения координат точки В воспользуемся равенством угловых коэффициентов прямой + 4x₂ = h (где h -- некоторая постоянная) и касательной к окружности в точке В. Рассматривая х₂ как неявную функцию переменной х₁, почленно дифференцируем уравнение окружности и получим

2х₁ + 2х₂ = 0 или -х₁/х₂

Приравнивая найденное выражение числу к = - 3/4, получаем одно из уравнений для определения координат точки В. В качестве второго уравнения возьмем уравнение окружности. Таким образом, для определения координат точки В имеем систему:

Решая данную систему получим х₁ = 4, х₂ =3. Тогда F_max =25.

Рис. 2.2. Решение задачи 2.2



Ответ: максимальное значение целевая функция принимает в точке В(4;3) равное F_max =25.

Задача 2.3.

Найти максимальное значение функции

F = - x₂

при условиях:

Решение:

Областью допустимых решений задачи является многоугольник ABCDE (рис. 2.3). Полагая значение целевой функции F = - x₂ равным некоторому числу h, получим линии уровня, а именно кубические параболы - x₂ = h. С увеличением числа h значения функции F соответственно увеличиваются.

Увеличивая значение h, мы видим, что наша кубическая парабола перемещается вверх по оси ОХ₂, до тех пор пока мы не получим точку К - точку касания кубической параболы и многоугольника решений. В полученной точке К целевая функция принимает максимальное значение.

Для определений координат точки К воспользуемся равенством угловых коэффициентов прямой и касательной к кубической параболе в точке К. Из уравнения прямой мы видим, что ее угловой коэффициент в точке К равен 1,5. Угловой же коэффициент касательной к кубической параболе в точке К, определим как значение производной функции от переменной в этой точке. Рассматривая как неявную функцию переменной и дифференцируя уравнение гиперболы, получим:



,

= .

Тогда получим систему:

Решая которую с учетом , мы получим = , 3 + . Таким образом,

F_max = - 3.

Рис. 2.3. Решение задачи 2.3

Ответ: = , 3 + . F_max = - 3.



Задача 2.4.

Найти минимальное значение функции

F = - x₂

при условиях:

Решение:

Областью допустимых решений задачи является многоугольник ABCDE (рис. 2.4). Следовательно, для нахождения решения задачи нужно определить такую точку многоугольника ABCDE, в которой функция F = - x₂ принимает минимальное значение. Построим линию уровня F = - x₂ = h, где h -- некоторая постоянная, и исследуем ее поведение при различных значениях h. При каждом значении h получаем график логарифмической функции, который при увеличении значения h перемещается вверх вдоль оси ОХ_2. Значит, функция F принимает маинимальное значение в точке касания одной из логарифмических функций с границей многоугольника ABCDE. В данном случае это точка М, в которой линия уровня F = - x₂ касается стороны DC многоугольника ABCDE.

Для определений координат точки М воспользуемся равенством угловых коэффициентов прямой и касательной к логарифмической функции в точке М. Из уравнения прямой мы видим, что ее угловой коэффициент в точке М равен 1. Угловой же коэффициент касательной к логарифмической функции в точке М, определим как значение производной функции от переменной в этой точке. Рассматривая как неявную функцию переменной и дифференцируя уравнение гиперболы, получим:

Тогда получим систему:

Решая которую с учетом , мы получим = , . Таким образом, F_max =.

Рис. 2.4. Графическое решение задачи 2.4

Ответ: = , . F_max =.

§3. Графический способ решения задач дробно-линейного программирования

Задача 3.1.

Найти наибольшее значение функции F = при ограничениях:

Решение:

Для решения воспользуемся алгоритмом данном в главе I в §5.

В системе ограничений задачи заменили знаки неравенств на знаки точных равенств и построили определяемые этими равенствами прямые: m₁: x₂ = x₁, m₂: x₂ = 4 + 2x₁, m₃: x₂ = 3 - 1/3x₁.

Нашли полуплоскости, определяемые каждым из неравенств системы ограничений задачи. Таким образом, определили многоугольник решений задачи - треугольник АВС.

Построили прямую: . Чтобы определить направление вращения прямой целевой функции, воспользуемся теоремой 5.1 из главы I §5, то есть найдем значение выражения: , тогда с увеличением h функция будет вращаться по часовой стрелке.

Вращая построенную прямую вокруг начала координат по часовой стрелке, получаем точку максимума - С(6;1). Находим значение целевой функции в точке максимума: F_max = 2.



Рис. 3.1. Решение задачи 3.1

Ответ: максимальное значение целевая функция принимает в точке С(6;1) равное F_max =2.

Задача 3.2.

Найти наименьшее значение функции F = при ограничениях:

Решение:

Для решения воспользуемся алгоритмом данном в главе I в §5.

В системе ограничений задачи заменили знаки неравенств на знаки точных равенств и построили определяемые этими равенствами прямые: n₁: x₂ = x₁ - 3, n₂: x₂ = 4 + 0,5x₁, n₃: x₂ = 10 - x₁.

Нашли полуплоскости, определяемые каждым из неравенств системы ограничений задачи. Получили область решений задачи - АВСD.

Построили прямую: . Чтобы определить направление вращения прямой целевой функции, воспользуемся теоремой 5.1 из главы I §5, то есть найдем значение выражения: , тогда с увеличением h функция будет вращаться по часовой стрелке.

Вращая построенную прямую вокруг начала координат по часовой стрелке, определили точку минимума - С(4;6). Нашли значение целевой функции в точке максимума: F_min = -2/13.

Рис. 3.2. Решение задачи 3.2

Ответ: минимальное значение целевая функция принимает в точке С(4;6) равное F_max =-2/13.

§4. Графический способ решения задач целочисленного программирования

Задача 4.1.

Найдите решение задачи целочисленного программирования:

(4.1)



Решение:

Для решения задачи воспользуемся алгоритмом данном в главе I в §6.

Построим область решения CAXV, удовлетворяющую условиям (4.1) задачи (рис. 4.1).

Рис. 4.1. Решение задачи 4.1

Условию целочисленности переменных области решения ABCD, удовлетворяют точки, показанные на рисунке.

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

Так как наша задача является задачей линейного программирования, то строим вектор = (3; 1), прямую = h, проходящую через область целочисленных решений.

Передвигаем прямую = h в направлении вектора С, до тех пор, пока она не дойдет до первой общей точки с областью целочисленных решений, то есть точка Е (0; 19). Координаты этой точки и определяют оптимальный план, а значение целевой функции в ней является минимальным - F_min = 19.

Ответ: F_min = 19 при Е (0; 19).

Задача 4.2.

Найдите решение задачи целочисленного программирования:

(4.2)

Решение:

Для решения задачи воспользуемся алгоритмом данном в главе I в §6.

Построим многоугольник решений ABC, удовлетворяющий условиям (4.2) задачи (рис. 4.2).

Рис. 4.2. Решение задачи 4.2



Условию целочисленности переменных многоугольника решений ABC, удовлетворяют точки, показанные на рисунке.

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

Так как наша задача является задачей линейного программирования, то строим вектор = (5; 7), прямую = h, проходящую через область целочисленных решений.

Передвигаем прямую = h в направлении вектора , до тех пор, пока она не дойдет до первой общей точки с областью целочисленных решений, то есть точка К (2; 6). Координаты этой точки и определяют оптимальный план, а значение целевой функции в ней является минимальным - F_min = 52.

Ответ: F_min = 52 при К (2; 6).

Задача 4.3.

Найдите решение задачи целочисленного программирования:

(4.3)

Решение:

Для решения задачи воспользуемся алгоритмом данном в главе I в §6.

Построим многоугольник решений ABC, удовлетворяющий условиям (4.3) задачи (рис. 4.3). Условию целочисленности переменных многоугольника решений ABC, удовлетворяют точки, показанные на рсиунке.

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

Рис. 4.3. Решение задачи 4.3

Так как наша задача является задачей дробно - линейного программирования, то строим прямую = h, которая проходит через начало координат. Чтобы определить направление вращения прямой целевой функции, воспользуемся теоремой 5.1 из главы I §5, то есть найдем значение выражения: , тогда с увеличением h функция будет вращаться против часовой стрелки.

Вращая прямую = h вокруг начала координат против часовой стрелки, до тех пор, пока она не дойдет до первой общей точки с областью целочисленных решений, то есть точка G (7; 1). В этой точке целевая функция принимает наименьшее значение - F_min 1,65. Вращая прямую дальше до последней общей точки, получим точку К (1; 5), в которой целевая функция принимает наибольшее значение - F_max 4,15.

Ответ: F_max 4,15 при К (1; 5), F_min 1,65 при G (7; 1).

Задача 4.4.

Найдите решение задачи целочисленного программирования:

(4.4)

Решение:

Для решения задачи воспользуемся алгоритмом данном в главе I в §6.

Построим многоугольник решений ABCDE, удовлетворяющий условиям (4.4) задачи (рис. 4.4).



Рис. 4.4. Решение задачи 4.4

Условию целочисленности переменных многоугольника решений ABCDE, удовлетворяют точки, показанные на рисунке.

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

Так как наша задача является задачей нелинейного программирования, то строим линию уровня F = = h, где h -- некоторая постоянная, и исследуем ее поведение при различных значениях h. При каждом значении h получаем график параболы, который при увеличении значения h перемещается вверх вдоль оси ОХ_2. Значит, функция F принимает максимальное значение в точке касания одной из параболических функций с областью целочисленных решений. В данном случае это точка К (1; 4). В этой точке целевая функция принимает максимальное значение - F_max = 4.

Ответ: F_max = 4 при К (1; 4).

§5. Графический способ решения задач параметрического программирования

Задача 5.1.

Найдите решение задачи параметрического программирования, если :

(5.1)

Решение:

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

Рис. 5.1. Решение задачи 5.1



Теперь рассмотрим задачу при условии, что t равно левой границе заданного интервала, а именно t = 0. Тогда целевая функция исходной задачи примет вид Следовательно, строим прямую с допустимым вектором Точкой максимума в этом случае является точка С(. Тогда максимальное значение целевой функции есть .

Из рисунка видно, что оптимальное решение будет оставаться в точке С( до тех пор, пока прямая, перпендикулярная вектору не станет параллельной прямой ВС, это произойдет тогда когда соответствующие коэффициенты станут пропорциональны:

При координаты любой точки отрезка ВС дают оптимальное решение. Таким образом, при задача имеет оптимальный план в точке С(, где .

Несложно предположить, что допустимый вектор вращается против часовой стрелки, причем только в первой четверти координатной плоскости при заданном отрезке для параметра t (так как координаты вектора будут положительными), тогда при остальных значениях параметра t оптимальный план будет достигаться в точке В(, значит максимум целевой функции будет иметь вид .

Ответ: при задача имеет оптимальный план в точке С(, где ; задача имеет оптимальный план в точке (, где .



Задача 5.2.

Найдите решение задачи параметрического программирования, если :

(5.2)

Решение:

Исследуем все значения из данного отрезка. Итак, Подставим данное значение в систему ограничений задачи, получим:

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

Рис. 5.2.1. Решение задачи 5.2 для



Исходя из рисунка 5.2.1, видно, что оптимальное решение задачи 5.2 находится в точке В. Для определения координат точки В в общем виде, решим систему уравнений:

Решая данную систему, имеем, что это и есть координаты точки В в общем виде: В (). Значит, наименьшее значение функции F равно

Так как значит следующее значение параметра . Подставим данное значение в систему ограничений задачи, получим:

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

Рис. 5.2.2. Решение задачи 5.2 для



Исходя из рисунка, видно, что оптимальное решение задачи 5.2 находится так же в точке В, то есть В (). Значит, наименьшее значение функции F при равно

Так как значит следующее значение параметра . Подставим данное значение в систему ограничений задачи, получим:

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

Рис. 5.2.3. Решение задачи 5.2 для

Исходя из рисунка 5.2.3, видно, что оптимальное решение задачи 5.2 при находится так же в точке В, то есть В (). Значит, наименьшее значение функции F при равно .

Ответ:

При оптимальное решение задачи находится в точке В (), при этом

При оптимальное решение задачи находится в точке В (), при этом

При оптимальное решение задачи находится в точке В (), при этом .



ГЛАВА IV. РЕШЕНИЕ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ ГРАФИЧЕСКИМ СПОСОБОМ В ТРЕХМЕРНОМ ПРОСТРАНСТВЕ

§1. Примеры задач линейного программирования в трехмерном пространстве, решенные графическим способом

Задача 1.1. Решить графическим методом задачу математического программирования:

Решение

Построим сначала многогранник решений. Сначала построим , данное уравнение определяет плоскость в трехмерном пространстве. Найдем прямые, по которым пересекает плоскости YOZ, ZOX, XOY. Итак, если плоскость пересекает координатную плоскость YOZ, то обнулив переменную , мы получим уравнение прямой, по которой плоскость , пересекает координатную плоскость YOZ, то есть по прямой . Соответственно, обнулив , мы получим уравнение прямой, по которой плоскость , пересекает координатную плоскость ZOX, то есть по прямой . И обнулив уравнение прямой . Таким образом, мы получим плоскость , при условии, что (рис. 1.1.1).



Рис. 1.1.1. Плоскость .

Аналогично, рассуждая, построим плоскость (рис. 1.1.2).

Рис. 1.1.2. Плоскость

Плоскость является плоскость параллельной плоскости XOY (рис. 1.1.3).



Рис. 1.1.3. Плоскость

Теперь объединяем получившиеся плоскости в один рисунок, для определения многогранника решений (рис. 1.1.4).

Рис. 1.1.4. Многогранник решений задачи 1.1

Примерный многогранник мы видим, теперь найдем координаты его точек. Итак, точка А является точкой пересечения прямых и в плоскости ZOY, составим систему из этих двух уравнений, решая которое, мы получим координаты точки А(0; . Точка В является точкой пересечения прямых и в плоскости ZOY, следовательно координаты точки В(0; 1; 1). Точка D есть точка пересечения прямых и в плоскости ZOY, тогда координаты точки D(0; . Точка С есть общая точка для плоскостей , следовательно, чтобы найти координаты точки С необходимо решить систему:

Решая данную систему, мы получили координаты точки С( Итак, мы получили многогранник решений для нашей задачи (рис. 1.1.5).

Рис. 1.1.5. Многогранник решений задачи 1.1

В одной из вершин, полученного многогранника решений, находится оптимальное решение задачи 1.1. Найдем ее, подсчитав значение целевой функции в каждой из вершин:

точка A(0; ): ;

точка B(0; 1; 1): ;

точка С(; 1): ;

точка D(0; : .

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



Ответ: в точке A(0; ) целевая функция принимает минимальное значение .

Задача 1.2. Решить графическим методом задачу математического программирования:

Решение:

Cначала построим плоскость определяемую выражением , обозначим ее . Так как , то найдем прямые, по которым плоскость пересекает плоскости YOZ, ZOX, XOY. Если плоскость пересекает плоскость YOZ, то значит переменная , подставим ее в уравнение плоскости . Тогда плоскость пересекает плоскость YOZ по прямой Если плоскость пересекает плоскость ZOX, то значит переменная , подставим ее в уравнение плоскости . Тогда плоскость пересекает плоскость ZOX по прямой Если плоскость пересекает плоскость XOY, то значит переменная , подставим ее в уравнение плоскости . Тогда плоскость пересекает плоскость XOY по прямой . Получаем следующую плоскость (рис. 1.2.1):



Рис. 1.2.1. Плоскость .

Аналогично, рассуждая, получаем плоскость (рис. 1.2.2).

Рис. 1.2.2. Плоскость

Теперь объединяем получившиеся плоскости в один рисунок, для определения многогранник решений (рис. 1.2.3).



Рис. 1.2.3. Многогранник решений задачи 1.2

Примерный многогранник мы видим, это ABCDO, осталось определить вершины многогранника. Точки B, C и D определяются сразу из построения, то есть B(2; 0; 0), D(1; 0; 0), C(0; 2; 0). Точку А найдем, как точку пересечений прямых и , получим координаты точки А(. Итак, получили многогранник решений (рис. 1.2.4)

Рис. 1.2.4. Многогранник решений задачи 1.2



В одной из вершин, полученного многогранника решений, находится оптимальное решение задачи 4.1.2. Найдем ее, подсчитав значение целевой функции в каждой из вершин:

точка A(): ;

точка B(2; 0; 0): ;

точка С(; 0): ;

точка D(0; : .

Исходя из последних вычислений, максимальное значение целевая функция принимает в точках A() и B(2; 0; 0), а следовательно, и во всех точках отрезка АВ.

Ответ: в каждой точке отрезка АВ целевая функция принимает максимальное значение .

Задача 1.3. Решить графическим методом задачу математического программирования:

Решение:

Построим сначала многогранник решений. Сначала построим , данное уравнение определяет плоскость в трехмерном пространстве. Найдем прямые, по которым пересекает плоскости YOZ, ZOX, XOY. Итак, если плоскость пересекает координатную плоскость YOZ , то обнулив переменную , мы получим уравнение прямой, по которой плоскость , пересекает координатную плоскость YOZ , то есть по прямой . Соответственно, обнулив , мы получим уравнение прямой, по которой плоскость , пересекает координатную плоскость ZOX , то есть по прямой . И обнулив уравнение прямой . Таким образом, мы получим плоскость , при условии, что (рис. 1.3.1).

Рис. 1.3.1. Плоскость

Аналогично, рассуждая, построим плоскость (рис. 1.3.2).

Рис. 1.3.2. Плоскость



Плоскость является плоскость параллельной плоскости XOY (рис. 1.3.3).

Рис. 1.3.3. Плоскость

Теперь объединяем получившиеся плоскости в один рисунок, для определения многогранник решений (рис. 1.3.4).

Рис. 1.3.4. Многогранник решений задачи 1.3

Примерный многогранник мы видим, теперь найдем координаты его шрифтов. Итак, точка А является точкой пересечения прямых и в плоскости ZOX, составим систему из этих двух уравнений, решая которое, мы получим координаты точки А(. Точка В ( исходя из построения. Точка С является точкой пересечения прямых и в плоскости XOY, следовательно координаты точки С(; 0; 2). Точка D(0; 3; 0) исходя из построения. Точка Е есть точка пересечения прямых и в плоскости ZOY, тогда координаты точки Е(0; . Точка F(0; 0; 3) исходя из построения. Точка G есть точка пересечения прямых и в плоскости ZOX, тогда координаты точки G(1; . Итак, мы получили многогранник решений для нашей задачи (рис. 1.3.5).

Рис. 1.3.5. Многогранник решений задачи 1.3

В одной из вершин, полученного многогранника решений, находится оптимальное решение задачи 4.1.1. Найдем ее, подсчитав значение целевой функции в каждой из вершин:

точка А(: ;

точка В (: ;

точка С(; 0; 2): ;

точка D(0; 3; 0): ;

точка F(0; 0; 3):

точка G(1; :10.

Исходя из последних вычислений, максимальное значение целевая функция принимает в точке G(1;

Ответ: в точке G(1; целевая функция принимает максимальное значение 10.

§2.Примеры задач нелинейного программирования в трехмерном пространстве, решенные графическим способом

Задача 2.1. Решить графическим методом задачу математического программирования:

Решение:

Найдем область решений. Рассмотрим первое неравенство, обозначим поверхность . Данное уравнение определяет двуполостный гиперболоид, определим кривые, по которым гиперболоид пересекает плоскости ZOY, XOZ, XOY. Для того чтобы найти кривую, по которой гиперболоид пересекает плоскость ZOY, обнуляем координату . Получим:

Данное уравнение не имеет решение, следовательно, поверхность не пересекает плоскость ZOY. Для того чтобы найти кривую, по которой гиперболоид пересекает плоскость XOZ, обнуляем координату . Получим:



Данное уравнение определяет ветвь параболы, расположившейся в плоскости XOZ. Для того чтобы найти кривую, по которой гиперболоид пересекает плоскость XOY, обнуляем координату . Получим:

.

Данное уравнение определяет ветвь параболы, расположившейся в плоскости XOY. Зная, что , можем построить часть гиперболоида, удовлетворяющей нашей системе (рис. 2.1.1).

Рис. 2.1.1. Поверхность

Аналогично, рассуждая, построим плоскость это уже эллипсоид (рис. 2.1.2).



Рис. 2.1.2. Поверхность

Теперь объединяем получившиеся плоскости в один рисунок, для определения области решений (рис. 2.1.3).

Рис. 2.1.3.Область решений задачи 2.1



Итак, областью решений является область ABCD (рис. 2.1.4).

Рис. 2.1.4.Область решений задачи 2.1

Теперь найдем координаты точек пересечения кривых, которые являются вершинами нашей области решений. Точку D и В мы можем определить из построения, таким образом D( и В(. Точка А является точкой пересечения кривых и , объединяя эти 2 уравнения в систему и решая ее, получим А(. Рассуждая аналогично для точки С, получим С(2; .

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

точка А(: ;

точка В(: ;

точка С(2; : ;

точка D(: .

Исходя из последних вычислений, максимальное значение целевая функция принимает в точке С(2; .

Ответ: в точке С(2; целевая функция принимает максимальное значение .

Задача 2.2. Решить графическим методом задачу математического программирования:

Решение:

Сначала построим область решений. Построим плоскости , , , , и , которые вытекают из системы ограничений (рис. 2.2.1).

Рис. 2.2.1. Область решений задачи 2.2

Теперь построим поверхность целевой функции, это параболоид (рис. 2.2.2).



Рис. 2.2.2. Поверхность целевой функции задачи 2.3

Объединим, получившиеся рисунки (рис. 2.2.3).

Рис. 2.2.3. Область решений задачи 2.3

Изменяя значение h в условии целевой функции , мы сможем определить, в какой точке целевая функция принимает максимальное значение. Если значение h взять отрицательным, то вершина параболы переместиться вверх по оси OZ, что никогда не даст вершину, в которой значение целевой функции максимально. Если значение h взять положительным, вершина параболы переместиться вниз по оси OZ, что, в конечном счете, даст точку С, в которой целевая функция принимает наибольшее значение, так как чем ниже вершина параболоида, тем шире становится часть параболоида в плоскости XOY (рис. 2.2.4-5).

Рис. 2.2.4-5. Положение поверхности целевой функции при разном значении h

Итак, мы получили точку С(3; 3; 0), в которой целевая функция принимает максимальное значение, а именно .

Ответ: в точке С(3; 3; 0) целевая функция принимает максимальное значение .

Заключение

графический линейный математическое программирование

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

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

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

В дробно-линейном программировании в двумерном пространстве после определения области решения, строят целевую функцию графиком которой является прямая, проходящая через начало координат, затем определяют направление вращения этой прямой, далее вращая ее, вокруг начала координат, определяем точки максимума и минимума, после считаем значение целевой функции в этих точках.

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

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

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

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

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

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



Список использованной литературы