Учебная работа. Реферат: Задачи линейного программирования 2

(5 оценок, среднее: 4,80 из 5)

Загрузка...

Учебная работа. Реферат: Задачи линейного программирования 2

Лабораторная работа.

Тема задачки линейного программирования

Цель:
преобретение практических способностей внедрения способов линейного программирования

задачка линейного программирования (ЛП) состоит в определении наибольшего (малого) значения мотивированной функции:

(1.1)

При критериях :

(1.2)

(1.3)

где aij
, bi
, cj
– данные неизменные числа. Функция F(1) именуется мотивированной функцией, выражения (2), (3) – ограничениями. значения xj
, удовлетворяющие ограничениям (2), (3) образуют область допустимых решений (ОДР) и именуются допустимыми. Допустимое решение xj
*
, при которых мотивированная функция (1) воспринимает экстремальное задачки ЛП могут применяться разные способы, которые рассмотрены ниже.

1.1.
Графический способ решения задач ЛП.

Постановка задачки.

способ применяется в этом случае, если количество переменных задачки ЛП (1), (2), (3) равно двум, т.е.:

(1.4)

(1.5)

(1.6)

методика решения

.
процесс решения задачки ЛП графическим способом включает последующие этапы:

1) На плоскости Х1
ОХ2
строятся граничные прямые, уравнения которых получают методом подмены неравенств (5), (6) на строгие равенства

2) Находятся полуплоскости, определяемые каждым из ограничений (5), (6).

3) Определяется область допустимых решений ОДР задачки на плоскости Х1
ОХ2
. Если система ограничений (5), (6) несовместна, то задачка ЛП не имеет решения.

4) Строится вектор

5) Строится ровная с1
х1
+с2
х2
= 0, перпендикулярная вектору и передвигается в направлении вектора (при поиске максимума мотивированной функции); в итоге определяется точка А, принадлежащая ОДР, в какой мотивированная функция F воспринимает наибольшее задачка ЛП не имеет решений.

6) Определяют координаты точки А – (х1
*
,х2
*
) и наибольшее

Пример.

Решить задачку ЛП:

1. На плоскости Х1
ОХ2
строим уравнения прямых: х1
–х2
= 3; х1
+ 2х2
= 4; х2
= 4; х1
=0; х2
=0

2. Для всякого из ограничений определяем допустимую полуплоскость и отмечаем ее стрелками. к примеру, условие при х1
=0; х2
=0 производится. означает точка (0,0) лежит в допустимой полуплоскости.

3. Определяем допустимую область для всех ограничений задачки (ОДР). Это многоугольник ABCD.

4. Строим вектор .

5. Строим прямую F=2×1
+x2
= 0. Передвигая ее в направлении вектора , определяем крайнюю точку А, принадлежащую ОДР – это т. А. В т. А функция имеет наибольшее

6. Координаты т. А находятся методом решения системы

Аналогично определяются координаты точки минимума С:

Личные задания. Решить графическим способом.

Вариант 1.

F = x1
+ x2

max

-3×1
+ 2×2
≤ 1

x1
+ 2×2
≤ 14

2×1
+ x2
≤ 13

3×1
– x2
≤ 12

x1
, x2
≥ 0

Вариант 2.

F = 3×1
+ x2

min

3×1
+ 5×2
≥ 15

5×1
+ 3×2
≥ 15

x1
≥ 1

x2
≥ 1

x1
, x2
≥ 0

Вариант 3.

F = 3×1
+ 3×2

min

x1
+ 4×2
≥ 4

4×1
+ x2
≥ 4

x1
, x2
≥ 0

Вариант 4.

F = 6×1
– 5×2

max

2×1
+ 5×2
≤ 10

5×1
+ 2×2
≤ 10

x1
, x2
≥ 0

Вариант 5.

F = 8×1
+ 2×2

max

x1
– 4×2
≤ 4

–4×1
+ x2
≤ 4

x1
+ x2
≤ 6

x
1

,
x
2

≥ 0

Вариант 6.

F = 2×1
+ 3×2

min

x1
+ 5×2
≥ 10

3×1
+ 2×2
≥ 12

2×1
+ 4×2
≥ 10

x1
≥ 1

x1
, x2
≥ 0

Вариант 7.

F = 5×1
+ 4×2
+ 6×3

max

x1
+ x2
+ x3
≤ 6

2×1
+ x2
+ x3
≥ 9

3×1
+ x2
+2×3
≥ 11

x1
, x2
, x3
≥ 0

Вариант 8.

F = –7×1
+ 2×2

min

x1
+ x2
≥ 1

5×1
+ x2
≥ 3

–3×1
+ x2
≤ 3

2×1
+ x2
≤ 4

x1
, x2
≥ 0

Вариант 9.

F = 6×1
+ 4×2

min

2×1
+ x2
≥ 3

x1
– 2×2
≤ 2

x1
, x2
≥ 0

Вариант 10.

F = – x1
– 2×2

min

5×1
– 2×2
≤ 4

– x1
+ 2×2
≤ 4

x1
+ x2
≥ 4

x1
, x2
≥ 0

Вариант 11.

F = 3×1
+ 3×2

max

x1
+ x2
≤ 4

3×1
+ x2
≥ 4

x1
+ 5×2
≥ 4

0 ≤ x1
≤ 3

0 ≤ x2
≤ 3

Вариант 12.

F = 7×1
– 2×2

max

x1
+ x2
≤ 5

2×1
– 3×2
≤ 6

3×1
+ x2
≥ 3

x1
+ x2
≥ 2

x1
– x2
≥ –3

x1
, x2
≥ 0

Вариант 13.

F = 6×1
– x2

min

x1
+ x2
≥ 3

4×1
– x2
≥ –4

3×1
– 2×2
≤ 24

x2
≤ 6

x1
, x2
≥ 0

Вариант 14.

F = –3×1
– 2×2

max

x1
– 2×2
≤ –3

2×1
+ x2
≤ 10

3×1
– x2
≥ –5

–x1
+ x2
≥ 3

x1
, x2
≥ 0

Вариант 15.

F = x1
+ 2×2

max

2×1
+ 3×2
≤ 8

2×1
+ x2
≤ 6

x1
+ x2
≥ 1

x1
, x2
≥ 0

Вариант 16.

F = –2×1
+ x2

min

2×1
+ x2
≤ 8

x1
+ 3×2
≥ 6

3×1
+ x2
≥ 3

x1
, x2
≥ 0

Вариант 17.

F = 6×1
+ 4×2

min

2×1
+ x2
≥ 3

x1
– 2×2
≤ 1

–x1
+ 2×2
≥ 1

x1
, x2
≥ 0

Вариант 18.

F = 4×1
+ 3×2

max

5×1
+ 2×2
≥ 20

x1
+ 3×2
≤ 15

x1
, x2
≥ 0

Вариант 19.

F = x1
+ 3×2

max

x1
+ x2
≥ 3

6×1
+ x2
≤ 42

2×1
– 3×2
≥ 6

x1
, x2
≥ 0

Вариант 20.

F = x1
– 2×2

max

5×1
– 2×2
≤ 3

x1
+ x2
≥ 1

–3×1
+ x2
≤ 3

x1
, x2
≥ 0

Вариант 21.

F = 8×1
+ 2×2

max

x1
– 4×2
≤ 4

–4×1
+ x2
≤ 4

x1
+ x2
≤ 6

x1
, x2
≥ 0

Вариант 22.

F = 2×1
+ 3×2

min

x1
+ 5×2
≥ 16

3×1
+ 2×2
≥ 12

2×1
+ 4×2
≥ 16

x1
≥ 1

x1
, x2
≥ 0

Вариант 23.

F = 3×1
+ 3×2

max

x1
+ x2
≤ 4

3×1
+ x2
≥ 4

x1
+ 5×2
≥ 4

0 ≤ x1
≤ 3

0 ≤ x2
≤ 3

Вариант 24.

F = 7×1
– 2×2

max

x1
+ x2
≤ 5

2×1
– 3×2
≤ 6

3×1
+ x2
≥ –3

x1
, x2
≥ 0

Вариант 25.

F = –7×1
+ 2×2

min

x1
+ x2
≥ 1

5×1
+ x2
≥ 3

–3×1
+ x2
≤ 3

2×1
+ x2
≤ 4

x1
, x2
≥ 0

Вариант 26.

F = 2×1
– x2

max

3×1
+ x2
≥ 16

x1
+ 2×2
≤ 12

x1
, x2
≥ 0

Вариант 27.

F = 6×1
+ 4×2

min

2×1
+ x2
≥ 3

x1
– 2×2
≤ 2

3×1
+ 2×2
≥ 1

x1
, x2
≥ 0

Вариант 28.

F = –x1
– 2×2

min

5×1
– 2×2
≤ 4

–x1
+ 2×2
≤ 4

x1
+ x2
≥ 4

x1
, x2
≥ 0

Вариант 29.

F = x1
+ 2×2

min

5×1
– 2×2
≤ 20

x1
– 2×2
≥ –20

x1
+ x2
≥ 16

x1
, x2
≥ 0

Вариант 30.

F = x1
+ x2

max

2×1
+ x2
≤ 18

x1
+ 2×2
≤ 16

x1
, x2
≥ 0

1.2.
Симплексный способ решения задач ЛП.

До этого чем решать задачку ЛП симплекс-методом ее нужно привести к каноническому виду
:

(1.7)

(1.8)

(1.9)

Для этого в случае необходимости задачка (1.1) поиска минимума сводится к задачке на поиск максимума (1.7) методом конфигурации символов коэффициентов Сj

;

Неравенства (1.2) преобразуются в строгие равенства методом введения доп неотрицательных переменных; условия неотрицательности (1.3) распространяются на все переменные методом введения подстановок.

Пример

. Дана задачка ЛП в общем виде:

Приведем ее к каноническому виду. Условие неотрицательности не распространяется на переменную х2
. Потому введем подстановку: х2
= х5
– х4
, где .

Тогда

Изменим вид экстремума на максимум:

Изменим неравенства на строгие равенства методом введения доп неотрицательных переменных. Тогда

Главные понятия и определения

.
Начальная задачка (1.7), (1.8), (1.9) быть может представлена в векторной форме:

x1
Р1
+x2
Р2
+…+xn
Pn
=P0

С=(c1
, c2
… cn
); X=(x1
,x2
… xn
); P1
,P2
…Pn
, P0
– m-мерные вектор-столбцы.

Вектор X=(x1
,x2
… xn
) именуется опорным планом задачки ЛП, если он удовлетворяет ограничениям (1.8); (1.9) и содержит m хороших от нуля положительных компонент. Другие (n-m) частей опорного плана равны нулю. метод симплекс-метода подразумевает переход от 1-го опорного плана к другому с повышением при всем этом значения мотивированной функции.

В неких вариантах начальный опорный план можно просто найти. Это происходит тогда, когда посреди векторов Pj имеется m единичных. В этом случае надлежащие единичным векторам переменные в опорном плане будут отличны от нуля. Они именуются базовыми. Другие переменные равны нулю; они именуются вольными.

Симплекс-преобразования длятся до того времени, пока посреди чисел не будет отрицательных.

Начальная симплекс-таблица в общем случае имеет вид

Базис

Сб

…

Cm+1

…

Pm+1

…

a1m+1

…

a1n

…

a2m+1

…

a2n

…

amm+1

…

amn

M+1

…

Δm+1

…

Δn

В столбце Сб
записываются коэффициенты мотивированной функции с теми же индексами, что и векторы базиса.

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

В (m+1)-й строке: F0
– текущее
записаны числа .

метод решения
.

1. Задачку ЛП приводят к каноническому виду и находят начальный опорный план.

2. Составляют начальную симплекс-таблицу.

3. Определяют, имеется ли хотя бы одно отрицательное число Δj в (m+1)-й строке. Если нет, то отысканный опорный план оптимален.

4. Находят меньшее отрицательное Δj и соответственный столбец обозначают как разрешающий. Если в разрешающем столбце посреди чисел aij
нет положительных, то мотивированная функция не ограничена сверху, а задачка ЛП не имеет решения.

5. Находят дела bi
к положительным aij
разрешающего столбца. Малое из этих отношений описывает разрешающую строчку.

6. На пересечении разрешающих строчки и столбца определяют разрешающий элемент.

7. Все элементы разрешающей строчки делят на разрешающий элемент.

8. Все элементы разрешающего столбца (не считая разрешающего элемента) подменяют нулями.

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

10. Перебегают к пт 3.

правило прямоугольника

…

p. строчка

…

А4

p. столбец

Пример.

Решить задачку ЛП:

1. Представим задачку в каноническом виде:

Найдем опорный план X=(0,0,0,360,192,180). Т.о. базовые переменные x4
, x5
, x6
; вольные – x1
, x2
, x3
.

2. Составим начальную симплекс-таблицу:

Базис

Сб

bi
/aij

360

360/12=30

192

192/8=24

p.стр

180

180/3=60

-9

–10

–16

p.ст.

Δ1
= 0·18 + 0·6 + 0·5 – 9 = – 9

Δ2
= 0·15 + 0·4 + 0·3 – 10 = – 10

Δ3
= 0·12 + 0·8 + 0·3 – 16 = – 16

Δ4
= 0·1 + 0·0 + 0·0 – 0 = 0

Δ5
= 0·0 + 0·1 + 0·0 – 0 = 0

Δ6
= 0·0 + 0·0 + 0·1 – 0 = 0

3. Отысканный опорный план X=(0,0,0,360,192,180) не оптимален, т.к. Δ1
, Δ2
, Δ3
– отрицательны.

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

5. – разрешающая строчка

6. а23
= 8 – разрешающий элемент.

7, 8, 9, 10 Строим новейшую симплекс-таблицу по приведенному выше методу, вводя в базис P3
заместо P5
.

Базис

Сб

bi
/aij

–3/2

72/9=8

p.стр

6/8

1/2

1/8

24 :1/2 = 48

108

11/4

3/2

–3/8

108 : 3/2=72

384

–2

p.ст.

Приобретенный опорный план X=(0,0,24,72,0,108) так же не оптимален, т.к. Δ2
= – 2 < 0. Потому по методу симплекс-метода перебегаем к новенькому опорному плану, вводя в базис P2
заместо P4
.

Базис

Сб

bi
/aij

1/9

–1/6

1/4

–1/8

5/24

5/4

–1/6

–1/8

400

2/9

5/3

Этот опорный план X*
=(0; 8; 20; 0; 0; 96) оптимален, т.к. все Δj
неотрицательны.

Наибольшее

Fmax
= 0·9 + 8·10 + 20·16 + 0·0 + 0·0 + 0·96 = 400

Решение общей задачки ЛП: x1
*
= 0; x2
*
= 8; x3
*
= 20; Fmax
= 400.

Личные задания.

Решить задачку ЛП симплексным способом. Варианты заданий взять из личных заданий пт 1.1.

1.3. способ искусственного базиса.

В общем случае опосля приведения задачки ЛП к каноническому виду конкретно записать опорный план не удается, т.к. посреди векторов Pj
. нет m единичных. В этом случае задачка ЛП решается способом искусственного базиса.

Постановка задачки
. Требуется отыскать максимум функции

(1.10)

При критериях

(1.11)

m<n,

но посреди векторов Pj
нет m единичных.

Определение
.
задачка, состоящая в определении максимума функции

(1.12)

при критериях

(1.13)

именуется расширенной по отношению к начальной задачке (1.10), (1.11).

тут M некие огромные положительные числа, значения которых не задаются.

Расширенная задачка (1.12), (1.13) имеет опорный план:

Переменные xn+1
, xn+2
… xn+m
именуются искусственными, а система единичных векторов Pn+1
, Pn+2
… Pn+m
образует искусственный базис.

Если в рациональном плане расширенной задачки (1.12), (1.13) значения искусственных переменных равны нулю, то – есть лучший план начальной задачки (1.10), (1.11).

Потому процесс решения задачки ЛП (1.10), (1.11) включает последующие этапы:

1. Для начальной задачки составляют расширенную задачку вида (1.12), (1.13).

2. Находят опорный план расширенной задачки.

3. При помощи вычислений симплекс-метода исключают искусственные вектора из базиса. В итоге находят опорный план начальной задачки. Если искусственные переменные исключить из базиса не удается, то задачка ЛП неразрешима.

4. Используя отысканный опорный план начальной задачки (1.10), (1.11), или находят симплекс-методом ее лучший план, или устанавливают ее неразрешимость

Пример.

Отыскать минимум функции

при критериях:

Представим эту задачку в каноническом виде:

Для образования базиса нужно три единичных вектора, т.к. m = 3. Но посреди векторов Pj
:

есть лишь два единичных – P4
и P5
. Потому составим расширенную задачку, введя искусственную переменную x7
в мотивированную функцию и в третье ограничение:

Расширенная задачка имеет опорный план X=(0;0;0;24;22;0;10), определяемый базисом P4
, P5
, P7
.

Составим начальную таблицу:

Базис

Сб

–3

-M

bi
/aij

–2

22/4

–M

–1

10/2

p.стр.

–8

–10

–1

–2

р.ст.

F=1·24+0·22+(–M) ·10 = 24 – 10M
Δ1
= 2·1 + 1·0 + 1·(–M) – 2 = 0 – M

Δ2
= 1·1 + 2·0 + 2(–M)–(–3) =4 + M

Δ3
= (–2)·1 + 4·0 + 2(–M)–6=–8–2M

Δ4
= 1·1 + 0·0 + 0·(–M) – 1 = 0

Δ5
= 0·1 + 0·0 + 0·(–M) – 0 = 0

Δ6
= 0·1 + 0·0 + (–1)·(–M) – 0=M

Δ7
= 0·1 + 0·0 + 1·(–M) – (–M)=0

При всем этом в (m+2)-й строке записываем коэффициенты при М. Сначала проверяем условие для крайней (пятой) строчки. тут есть отрицательные числа: и .

Перебегаем к новенькому опорному плану по методу симплекс-метода. Для этого исключим вектор P7
из базиса, а вектор P3
введем заместо него. В предстоящем искусственный вектор P7
не имеет смысла вводить в базис, потому столбец P7
исключаем из таблицы.

Потому что все искусственные векторы исключены из базиса то нет смысла включать в таблицу и (m+2)-ю (пятую для нашей задачки) строчку.

Потому новенькая таблица имеет четыре строчки и 6 столбцов:

Базис

Сб

–3

bi
/aij