ВУЗ:
Составители:
26 27
БП
Z
1
y
2
y
3
y
4
y
5
y
6
y
Реше-
ние
1
y
0 1 0
8
3
4
1
−
4
1
8
3
−
8
9
2
y
0 0 1
4
1
−
2
1
2
1
−
4
1
4
1
Z
1 0 0 4 3 2 2 16
Для окончательного получения последней симплекс-
таблицы двойственной задачи остается умножить элементы
столбцов
3
y ,
4
y ,
5
y и
6
y во всех строках, кроме строки
целевой функции
2
, на (–1):
БП
Z
1
y
2
y
3
y
4
y
5
y
6
y
Реше-
ние
1
y
0 1 0
8
3
−
4
1
4
1
−
8
3
8
9
2
y
0 0 1
4
1
2
1
−
2
1
4
1
−
4
1
Z
1 0 0 4 3 2 2 16
В результате получилась такая же симплекс-таблица,
как и после применения симплекс-метода в примере 3.
2
Коэффициенты в строке целевой функции умножаются на (–1) в двой-
ственной задаче на минимизацию, в нашем примере двойственная зада-
ча – на максимизацию.
Типовой расчет
«Основная задача линейного программирования»
Задание для самостоятельной работы
Дано условие задачи линейного программирования.
Требуется:
1)
Решить исходную задачу графическим методом.
2)
Решить исходную задачу симплекс-методом, введя
при необходимости искусственный базис.
3)
Составить условие задачи, двойственной к данной.
4)
Решить двойственную задачу симплекс-методом,
введя при необходимости искусственный базис.
5)
Решить двойственную задачу с использованием
теорем двойственности.
Индивидуальные условия (в 20 вариантах)
0,0
8
42
2
max3
21
21
21
21
21
≥≥
⎪
⎩
⎪
⎨
⎧
≤+
≤+−
≥+
→−=
xx
xx
xx
xx
xxF
1
В
ариант
0,0
102
22
4
min2
21
21
21
21
21
≥≥
⎪
⎩
⎪
⎨
⎧
≤+
≤+−
≥+
→−=
xx
xx
xx
xx
xxF
2
В
ариант
БП Z y1 y2 y3 y4 y5y 6 Реше-
ние
3 1 1 3 9
y1 0 1 0 − − Типовой расчет
8 4 4 8 8
1 1 1 1 1
y2 0 0 1 − − «Основная задача линейного программирования»
4 2 2 4 4
Z 1 0 0 4 3 2 2 16
Задание для самостоятельной работы
Для окончательного получения последней симплекс-
таблицы двойственной задачи остается умножить элементы Дано условие задачи линейного программирования.
Требуется:
столбцов y 3 , y 4 , y 5 и y 6 во всех строках, кроме строки
1) Решить исходную задачу графическим методом.
целевой функции2, на (–1): 2) Решить исходную задачу симплекс-методом, введя
при необходимости искусственный базис.
БП Z y1 y2 y3 y4 y5y 6 Реше- 3) Составить условие задачи, двойственной к данной.
ние 4) Решить двойственную задачу симплекс-методом,
3 1 1 3 9 введя при необходимости искусственный базис.
y1 0 1 0 − −
8 4 4 8 8 5) Решить двойственную задачу с использованием
1 1 1 1 1 теорем двойственности.
y2 0 0 1 − −
4 2 2 4 4
1 0 0 4 3 2 2 16 Индивидуальные условия (в 20 вариантах)
Z
Вариант 1 Вариант 2
В результате получилась такая же симплекс-таблица,
как и после применения симплекс-метода в примере 3. F = x1 − 3x 2 → max F = 2 x1 − x 2 → min
⎧ x1 + x2 ≥ 2 ⎧ x1 + x2 ≥ 4
⎪ ⎪
⎨− x1 + 2 x2 ≤ 4 ⎨− x1 + 2 x2 ≤ 2
⎪ x + x2 ≤ 8 ⎪ x + 2 x2 ≤ 10
⎩ 1 ⎩ 1
x1 ≥ 0, x 2 ≥ 0 x1 ≥ 0, x 2 ≥ 0
2
Коэффициенты в строке целевой функции умножаются на (–1) в двой-
ственной задаче на минимизацию, в нашем примере двойственная зада-
ча – на максимизацию.
26 27
