ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ №1

	0,1,2	3,4,5,6	7,8,9
	f(x)=3x1-2x2; 2x1+x2≤2; x1+2x2≤2; x1,x2≥0;	f(x)=4x1+8x2; x1+x2≤3; x1+2x2≤2; x1,x2≥0;	f(x)=-4x1+8x2; 3x1+5x2≤15; x1-x3≤1; x1,x2≥0;
	f(x)=3x1-2x2; -x1+2x2≤2; 2x1-x2≤2; x1,x2≥0;	f(x)=-x1+6x2; 4x1+3x2≤12; -x1+x2≤1; x1,x2≥0;	f(x)=-x1+6x2; x1+x2≤3; -2x1+x2≤2; x1,x2≥0;
	f(x)=x1+6x2; 3x1+4x2≤12; -x1+x2≤2; x1,x2≥0;	f(x)=2x1+6x2; 3x1+4x2≤12; x1+2x2≤2; x1,x2≥0;	f(x)=8x1+12x2; 2x1+x2≤4; 2x1+5x2≤10; x1,x2≥0;
	f(x)=8x1+12x2; -3x1+2x2≤0; 4x1+3x2≤12; x1,x2≥0;	f(x)=3x1-2x2; 2x1+x2≤2; 2x1+3x2≤6; x1,x2≥0;	f(x)=6x1+4x2; x1+2x2≤2; -2x1+x2≤0; x1,x2≥0;
	f(x)=6x1+4x2; 3x1+2x2≤6; 3x1+x2≤3; x1,x2≥0;	f(x)=8x1+6x2; -x1+x2≤1; 3x1+2x2≤6; x1,x2≥0;	f(x)=8x1+6x2; -x1+x2≤2; 3x1+4x2≤12; x1,x2≥0;

 

Пример. Решить следующую задачу максимизации

F(x)=5x₁-x₂→max

2x₁-x₂+x₃≤3

3x₁+2x₂≤6

x₁≥0; x₂≥0

 

Запишем систему в каноническом виде

1) 2x₁-x₂+x₃=3

2) 3x₁+2x₂=6

3) x₁=0; x₂=0

 

Решение. В системе координат Х₁ОХ₂ построим ОДР.

Из первого уравнения:

При Х₁=0 X₂=-3 → (X₁,X₂)=(0,-3) прямая (1)

При Х₂=0 Х₁=3 → (X₁,X₂)=(3, 0)

2 2

 

Из второго уравнения:

При Х₁=0 X₂=3 → (X₁,X₂)=(0,3) прямая (2)

При Х₂=0 Х₁=2 → (X₁,X₂)=(2, 0)

 

Из условия (3) (Х₁, Х₂)=(0,0) Х₁=0 – прямая (3)

Х₂=0 – прямая (4)

 

Для определения с какой стороны прямых ОДР все точки удовлетворяют неравенствам возьмем точку (1,1). Таким образом, ОДР лежит внутри АВСD.

Для определения точки выхода, строим прямую:

F(x)=5x₁-x₂=0

5x₁=x₂→ x₁=x₂=0 при x₁=1, x₂=5

Строим нулевую линию уровня целевой функции.

Строим нормальный вектор q (5.-1)

Передвигая линию уровня целевой функции параллельно себе, по вектору q, фиксируем ее крайнее положение (т.В), которая принадлежит прямым (1) и (2).

2x₁-x₂+x₃=3

3x₁+2x₂=6

 

x₁=12 x₂=3, т.е. Х^*=(12, 3)

7 7 7 7

F(Х^*)=5х12 -3=57

7 7 7

 

 

2.8Двойственные задачи линейного программирования (ДЗЛП).

Рассмотрим пример 2.6 и пример 2.5 и представим их в виде таблице

 

Задача 1 (исходная)	Задача 2 (двойственная)
F=2x1+3x2→max при ограничениях: x1+3x2≤18 2x1+x2≤16 x2≤5 3x1≤21 x1, x2≥0 Составить такой план выпуска продукции X=(x1, х2) при котором прибыль при реализации будет max. В общем виде задача запишется: n F=∑Cjxj→max, j=1 при ограничениях: n j=1,2…m ∑aijхi≤ bi i=1,2…n j=1	Z=18 y1+16y2+5y3+21y4→min при ограничениях: y1+2y2+3y4≥2 3y1+y2+y3≥3 y1, y2, y3, y4≥0 Найти такой набор цен ресурсов Y=(y1,y2,y3,y4), при котором общие затраты на ресурсы будут минимальны. В общем виде задачу запишем: m Z=∑ biyi →min, i=1 при ограничениях: m j=1,2…m ∑ aijyi≤ cj i=1,2…n i=1

 

Из таблице видно, что задачи 1 и 2 обладают следующими свойствами:

1) В задаче 1 ищут max, во 2 ищут min.

2) Коэффициенты целевой ф-ции 1-ой задачи являются свободными членами системы ограничения 2-ой задачи.

3) Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида ≤, а в задаче минимизации вида ≥.

4) Матрицы коэффициентов в системе ограничения обеих задач являются транспонированными друг другу.

Для 1 3 18

задачи 1 A₁= 2 1 16

0 1 5

3 0 21

2 3 F

 

 

Для

задачи 2 A’₁= 1 2 0 3 2

3 1 1 0 21

18 16 5 21 Z

 

 

 

 

5) Число неравенств в системе ограничений 1-ой задачи совпадает с числом переменных 2-ой задачи.

6) условие не отрицательности переменных есть в обеих задачах.

Две задачи, обладающие указанными свойствами, называются симметричными взаимно – двойственными задачами.

2.9Алгоритм составления двойственных ЗЛП:

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

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

2) Составить расширенную матрицу системы A₁.

₃₎ Найти матрицу A₁, транспонированную к матрице A_1.

4) Сформулировать двойственную ЗЛП

Этот алгоритм можно проиллюстрировать следующим примером:

Составить задачу двойственную следующей задаче:

F=14x₁+10x₂+14x₃+11x₄→max

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

4х₁+2х₂+2х₃+3х₄≤35

х₁+х₂+2х₃+3х₄≤30

3х₁+х₂+2х₃+х₄≥40*

х₁≥0

х₂≥0

х₃≥0

х₄≥0

 

Решение:

Алгоритм	Конкретные ситуации данного алгoритма
1.Все неравенства системы ограничений привести к виду ≤;   2.Составить расширенную матрицу системы А1, в которую включить: - матрицу коэффициентов переменных системы ограничений. - столбец свободных членов. - строку коэффициентов при переменных линейной функции.   3.Найти матрицу A'1 транспонированную к матрице А1.   4.Сформулировать двойственную задачу на основании полученной матрицы A'1	Приведем третье неравенство к виду: -3х1-х2-2х3-х4≤-40     4 2 2 3 35 А1= 1 1 2 3 30 -3 -1 -2 -1 -40 14 10 14 11 F   4 1 -3 14 2 1 -1 10 A'1 = 2 2 -2 14 3 3 -1 11 35 30 -40 Z   Z=35y1+30y2-40y3→min 4y1+y2-3y3≥14 2y1+y2-y3≥10 2y1+2y2-2y3≥14 3y1+3y2-y3≥11 y1≥0; y2≥0; y3≥0

Выполнить самостоятельно:

1. Составить ДЗЛП следующей задачи

F=-x₁+2x₂→max

При ограничении: 2x₁-x₂≥1

-x₁+4x₂≤24

x₁ -x₂≤3

x₁ +x₂≥5

2. Составить ДЗЛП, используя исходные данные таблицы №1. Вариант задания выбирается по номеру зачетной книжки

–предпоследняя цифра - № строки

–последняя цифра - № столбца.

3.Теорема двойственности

Первая теорема двойственности

Устанавливает связь между оптимальными решениями ДЗЛП.

 

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

F_max=Z_min или F(X^*)=Z(Y^*)

Если линейная функция одной из задач не ограничена (F=∞), то по условию другой задачи противоречивы.

Рассмотрим пример подтверждающий справедливость I теоремы.

Задача 1. Даны 2 взаимно двойственные задачи

I F=2x1-3x2→max При ограничениях: x1+3x2≤ 18 2x1+x2≤16 x2≤5 3x1≤21 x1≥0 x2≥0

II Z=18y1+16y2+5y3+21y4→min При ограничениях: y1+2y2+3y4 ≥2 3y1+y2+y3≥3   yi≥0 (i=1,2,3,4)

 

Задача I об использовании ресурсов и двойственная ей задача II были решены ранее (§ 2.6, 2.7) получены оптимумы, F_max=24 и Z_min=24, т.е. заключение I теоремы двойственности верно.

 

Экономический смысл теоремы

План производства X^*=(x₁^*,x₂^*…x_n^*) и набор цен Y^*=(y₁^*,y₂^*…y_m^*) оказываются оптимальными только тогда, когда прибыль от продукции, найденная при “внешних” ценах c₁,c₂…c_n, равны затратам на ресурсы по “внутренним ” (определяемым из решения задачи) ценам, для всех же других планов, прибыль от продукции всегда меньше (или равна) затрат на ресурсы, т.е. F(X)≤Z(Y).

 

Вторая теорема двойственности

Пусть даны две взаимно двойственные задачи (табл. 1). Преобразуем эти две задачи для решения симплексным методом. Тогда системы ограничений каждой из задач будут

 

a_ij x_j + x_n+i = b_i j=1,2…n

 

a_ij y_j - y_m+j = c_ji=1,2…m

установим соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи. См табл.1

Переменные исходной задачи I
первоначальные	дополнительные
x1 x2 … xi … xn ↕ ↕ ↕ ↕ ym+1 ym+2 … ym+i …ym+n	xn+1 xn+2 … xn+j … xn+m ↕ ↕ ↕ ↕ y1 y2 … yj … ym
дополнительные	первоначальные
Переменные двойственной задачи II

Вторая теорема двойственности:

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

 

Справедливость I теоремы двойственности подтверждается решением задачи 1

На основании соответствий в табл. 1 установим следующие соотношения

x₁ x₂ x₃ x₄ x₅ x₆

↕ ↕ ↕ ↕ ↕ ↕

y₁ y₂ y₃ y₄ y₅ y₆

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

 

 

Компоненты оптимального решения двойственной задачи y_i^*=4/5, y₂^*=3/5, y₃^*=0, y₄^*=0, y₅^* =0, y₆^*=0 равны (по абсолютной величине) коэффициентом при соответствующих переменных линейной функции

F=24-4/5x₃-3/5x₄-0x₅-0x₆-0x₁-0x₂,

а компоненты оптимального решения исходной задачи x_i^*=6, x₂^*=4, x₃^*=0, x₄^*=0, x₅^* =1, x₆^*=3 равны коэффициентам при соответствующих переменных линейной функции II:

F=24+6y₅+4y₆+0y₁+0y₂+1y₃+3y₄

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

Развернуть

Открыть в широком формате