Глава 1. Математические методы

1. Графический метод решения задач

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

Z(X) =c₁x₁+c₂x₂ → max (min)

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

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

Областью решений линейного неравенства a_i1x₁+a_i2x₂≤b_i является одна из двух полуплоскостей, на которые прямая a_i1x₁+a_i2x₂=0, соответствующая данному неравенству, делит всю координатную плоскость. Для того, чтобы определить, какая из полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство: если оно удовлетворяется, то областью решений является полуплоскость, содержащая эту точку, если не удовлетворяется – то полуплоскость, не содержащая данную точку.

Для нахождения среди допустимых решений оптимального используют линии уровня и опорные прямые. Линией уровня называется прямая, на которой целевая функция задачи принимает постоянное значение. Уравнение линии уровня имеет вид c₁x₁+c₂x₂=L, где L = const. Все линии уровня параллельны между собой. Опорной прямой называется линия уровня, которая имеет хотя бы одну общую точку с областью допустимых решений и по отношению к которой эта область находиться в одной из полуплоскостей. Важное свойство линии уровня: при параллельном смещении линии в одну сторону уровень возрастает, а в другую сторону – убывает.

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

Z(x)=2х₁+3х₂ → max

-6х₁+х₂ ≥ 3

-5х₁+9х₂ ≤ 45

x₁-3х₂ ≤ 3

х₁ ≥ 0, х₂ ≥ 0

Найдем точки пересечения прямых с осями координат:

I. -6х₁+х₂=3

1) х₁=0 2) х₂=0

x₂=3 х₁= -1/2

II. -5х₁+9х₂=45

1. х₂=0 2) х₂=0

x₂=5 х₁= -9

III. х₁-3х₂=3

1. х₁=0 2) х₂=0

x₂= -1 х₁=3

Построим область решения данной системы:

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

Z(х)=2х₁+3х₂=0

1. х₁=0 2) х₁=3

x₂=0 х₂= -2

Z(х)=2х₁+3х₂=6

1. х₁=0 2) х₂=0

x₂=2 х₁=3

Ответ: Целевая функция принимает максимальное значение в точке (0;0), при х₁=0 и х₂=0.

2. Теория двойственности

Любой задаче линейного программирования, называемой исходной, можно поставить в соответствие другую задачу, которая называется двойственной. Обе эти задачи образуют пару двойственных задач. Каждая из задач является двойственной к другой задаче.

Алгоритм составления двойственной задачи:

1) Привести все неравенства ограничений исходной задачи к единому смыслу: если в исходной задаче ищется максимум линейной функции, то все неравенства системы ограничений привести к виду «≤», а если минимум – к виду «≥». Для этого неравенства, в которых данное требование не выполняется, умножить на -1.

2) Составить расширенную матрицу системы – А, в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.

3) Найти матрицу А' транспонированную к матрице А

4) Сформулировать двойственную задачу на основании полученной матрицы А` и условия неотрицательности переменных.

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

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

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

Z(х)=4х₁+13х₂+3х₃+6х₄ → min

При ограничениях:

-5х₁+3х₂-х₃+2х₄+х₅ = -1

9х₁-4х₂+2х₃-3х₄+х₆ = 6

Учитывая условия неотрицательности:

x_j ≥ 0 , j=1,2,3,4.

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

-5х₁+3х₂-х₃+2х₄+х₅ ≥ -1

9х₁-4х₂+2х₃-3х₄+х₆ ≥ 6

Составим расширенную матрицу системы уравнений:

-5 3 -1 2 1 0 -1

А = 9 -4 2 -3 0 1 6

4 13 3 6 0 0 Z

Найдем транспонированную матрицу системы уравнений:

-5 9 4

3 -4 13

-1 2 3

А′ = 2 -3 6

1 0 0

0 1 0

-1 6 F

Составим новую систему ограничений:

F(y)= -у₁+6у₂ → max

-5у₁+9у₂ ≤ 4

3у₁+4у₂ ≤ 13

-у₁+2у₂ ≤ 3

2у₁-3у₂ ≤ 6

y₁≤ 0

у₂ ≤ 0

у₁ ≥ 0; у₂ ≥ 0

Найдем точки пересечения прямых с осями координат:

I. -5у₁+9у₂ ≤ 4

1) у₁=0 2) у₂=0

y₂=4/9 у₁= -4/5

II. 3у₁+4у₂ ≤ 13

1. у₁=0 2) у₂=0

y₂= -13/4 у₁=13/3

III. –у₁+2у₂ ≤ 3

1. у₁=0 2) у₂=0

у₂=3/2 у₁= -3

IV. 2у₁-3у₂ ≤ 6

1. у₁=0 2) у₂=0

у₂= -2 у₁=3

Построим область решений системы неравенств:

FA=9– max

FB=4/9*6=8/3=2*2/3– min

Ответ: по теореме двойственности F_max = Z_min = 9.