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

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

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

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

Пример: Симплексным методом решить задачу максимизации.

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

2x₁-x₂+x₃≤3

3x₁+2x₂≤6

x₁≥0; x₂≥0

1. Переведем систему ограничений в канонический вид, введя выравнивающие (базисные) неизвестные – x₃ и x₄.

Задача принимает следующий вид:

2x₁-x₂+x₃=3

3x₁+2x₂=6

x₁=x₂=x₃=x₄=0

F-5x₁+x₂=0

2. Заполняем первую симплексную таблицу. В ней x₃, x₄ – основные переменные (базис).

Таблица 1.

Базис	Свободный член	Переменные	Оценочные отношения
х1	х2	х3	х4
x3		2	-1			3/2
x5
F		-5

← разрешающая строка

↑

разрешающий столбец

3. Проверяем выполнение критерия на max – первый опорный план не оптимальный, т.к. в F коэффициент при х₁<0

4. Выбираем наибольший по модулю отрицательный коэффициент F, который определяет разрешающий столбец.

5. Делим свободные члены на коэффициенты разрешающего столбца (определяем оценочные отношения). Выбираем разрешающую строку, где это отношение минимально

Min (3, 2)= 3

2 2

Разрешающий элемент будет а₁₁=2

Для построения таблицы 2 в качестве основной переменной выбираем х₁, т.к. она образует разрешающий столбец таблицы 1.

Таблицы 2.

Базис	Свободный член	Переменные	Оценочные отношения
х1	х2	х3	х4
х1	3/2		-1/2	1/2		-3
х4	3/2		7/2	-3/2		3/7
F	15/2		-3/2	5/2

← разрешающая строка

↑

разрешающий столбец

Построение таблицы №2.

1. Заменим переменные в базисе с х₃ на х₁.

2. Делим элементы разрешающей строки (табл.1) на разрешающий элемент, результаты занесем в строку х₁ в табл. №2.

3. В остальных клетках разрешающего столбца (табл. 1) записываем 0.

4. Остальные клетки заполняем по правилу прямоугольника

НЭ=СТЭ-(АхВ)/РЭ

СТЭ А

В РЭ

5. Критерий эффективности опять не выполнен, т.к. F имеет два коэффициента - 3 < 0

Построение таблицы №3

Таблицы 3.

Базис	Свободный член	Переменные	Оценочные отношения
х1	х2	х3	х4
х1	12/7			2/7	1/7
х2	3/7			-1/7	2/7
F	57/7			13/7	3/7

Из таблицы 3 видно – критерий оптимальности выполнен.

Оптимальные базисные решения Х^*=(12, 3,0,0)

7 7

F=5x₁-x₂=5x 12 - 3 = 57

7 7 7

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ №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.Составить расширенную матрицу системы А₁, в которую включить: - матрицу коэффициентов переменных системы ограничений. - столбец свободных членов. - строку коэффициентов при переменных линейной функции.   3.Найти матрицу A'₁ транспонированную к матрице А₁.   4.Сформулировать двойственную задачу на основании полученной матрицы A'₁

Приведем третье неравенство к виду: -3х₁-х₂-2х₃-х₄≤-40    

4 2 2 3 35

А₁= 1 1 2 3 30

-3 -1 -2 -1 -40

14 10 14 11 F

4 1 -3 14

2 1 -1 10

A'₁ = 2 2 -2 14

3 3 -1 11

35 30 -40 Z

Z=35y₁+30y₂-40y₃→min

4y₁+y₂-3y₃≥14

2y₁+y₂-y₃≥10

2y₁+2y₂-2y₃≥14

3y₁+3y₂-y₃≥11

y₁≥0; y₂≥0; y₃≥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₄

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

Дата добавления: 2014-01-06