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

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

-6х₁+х₂ ≥ 3

-5х₁+9х₂ ≤ 45

х₁-3х₂ ≤ 3

х₁ ≥ 0 , х₂ ≥ 0

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

I. -6х₁+х₂=3

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

х₂=3 х₁= -1/2

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

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

х₂=5 х₁= -9

III. х₁-3х₂=3

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

х₂= -1 х₁=3

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

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

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

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

х₂=0 х₂= -2

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

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

х₂=2 х₁=3

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

значение в точке(0;0), при х₁=0 и х₂=0.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

х_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

у₁ ≤ 0

у₂ ≤ 0

у₁ ≥ 0 ; у₂ ≥ 0

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

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

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

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

2. 3у₁+4у₂ ≤ 13

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

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

3. -у₁+2у₂ ≤ 3

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

у₂=3/2 у₁= -3

IV. 2у₁-3у₂ ≤ 6

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

у₂= -2 у₁=3

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

F_A=9 - max

F_B=4/9*6=8/3=2*2/3 - min

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