Курсовая работа - Сведение матричной игры к задаче линейного программирования

4.1 Алгоритм симплекс-метода.

Рассмотрю систему ограничений и линейную форму вида:













;

2211

2222212 1

11212111

mnmnmm

nn

bxaxaxa







(4.1)

;

22110min nn

xcxcxccZ  

(4.2)

0

i

x

,

ni ,1

. (4.3)

Используя метод Жордана-Гауса, приведём записанную систему к виду, где

выделены базисные переменные.

Введём условные обозначения:

r

xxx ,,,

21



– базисные переменные;

nrr

xxx ,,,

21





– свободные переменные.

 















;

2211

222211222

122111111

nrnrrrrrrrr

nnrrrr

xxxx









(4.4)

 

nnrurr

xxxZ









22110min

. (4.5)

По последней системе ограничений построим табл. 4.1.

Таблица 4.1

Симплекс-таблица

Свободные

неиз-

вест-

ные

Базисные

неизвестные

Свободный

член

1r

x

2r

x



n

x

1

x

2

x



r

x

min

Z

1



2





r



0



11 r



12 r





1rr



1r



21 r



22 r





1rr



2r





n1



n2





rn



n



Данная таблица называется симплекс-таблицей. Все дальнейшие

преобразования связаны с изменением содержания этой таблицы.

Алгоритм симплекс-метода сводится к следующему.

43

1. В последней строке симплекс-таблицы находится наименьший

положительный элемент, не считая свободного члена. Столбец, соответствующий

этому элементу, считается разрешающим.

2. Вычисляют отношение свободных членов к положительным элементам

разрешающего столбца (симплекс-отношение). Находят наименьшее из этих

симплекс-отношений, оно соответствует разрешающей строке.

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

элемент.

4. Если имеется несколько одинаковых по величине симплекс-отношений, то

выбирают любое из них, то выбирают любое из них. То же самое относится к

положительным элементам последней строки симплекс-таблицы.

5. После нахождения разрешающего элемента переходят к следующей

таблице. Неизвестные переменные, соответствующие разрешающей стоке и

столбцу, меняют местами. При этом базисная переменная становится свободной

переменной, и наоборот. Симплекс таблица преобразована следующим образом

Таблица 4.2

Симплекс-таблица

Свободные

неиз-

вест-

ные

Базисные

неизвестные

Свободный

член

1r

x

2r

x



n

x

1

x

2

x



r

x

min

Z

21

1

r

a





21

11



r

a





21



r

a



21

22



r

a



21

1



r

rr

a



21

2



r

a





21

1

r

n

a





44

6. Элемент табл. 4.2 соответствующий разрешающему элементу табл. 4.1,

равен обратной величине разрешающего элемента.

7. Элементы строки табл. 4.2, соответствующие элементам разрешающей

стоки табл. 4.1, получаются путём деления соответствующих элементов табл. 4.1

на разрешающий элемент.

8. Элементы столбца табл. 4.2, соответствующие элементам разрешающего

столбца табл. 4.1, получаются путём деления соответствующих элементов табл.

4.1 на разрешающий элемент и берутся с противоположным знаком.

9. Остальные элементы вычисляются по правилу прямоугольника: мысленно

вычерчиваем прямоугольник в табл.4.2, одна вершина которого совпадает с

разрешающим элементом, а другая – с элементом, образ которого мы ищем;

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

4.2 будет равен соответствующему элементу табл. 4.1 минус дробь в знаменателе

который стоит разрешающий элемент, а в числителе произведение элементов из

двух неиспользованных вершин прямоугольника.

10. Как только получится таблица, в которой в последней стоке все элементы

отрицательны, считается, что минимум найден. Минимальное значение функции

равно свободному члену в строке целевой функции, а оптимальное решение

определяется свободными членами при базисных переменных. Все свободные

переменные в этом случае равны нулю.

11. Если в разрешающем столбце все элементы отрицательны, то задача не

имеет решений (минимум не достигается).

45

5. Методы нахождения опорного решения задачи линейного

программирования.

5.1. Метод искусственного базиса.

Сформулированный выше алгоритм Симплекс-метода можно применять

лишь в том случае, если выделено первое допустимое решение, т.е. исходная

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

 















;

2211

122111111

nrnrrrrrrrr

nnrrrr

xxxx









 

;

22110min nnrrrr

xxxZ









При этом

0,,0

1



r





, тогда, положив свободные неизвестные

nrr

xxx ,,

21 

равными нулю, получаем опорное решение

rr

xxx



 ;;;

2211



.

Рассмотрю метод нахождения опорного решения, основанный на введении

искусственных переменных. Для этого запишем задачу линейного

программирования в общем виде. Будем рассматривать задачу с числом

неизвестных

n

и

r

ограничениями:













.

;

2211

11212111

bxaxaxa

nrnrr

nn







(5.1)

Перепишем систему (5.1) в другом виде. Для этого введём искусственные

переменные

r

yyy ,,,

21



так, чтобы был выделен базис. Тогда система примет вид

 













.

;

2211

121211111

nrnrrrr

nn

xaxaxaby







(5.2)

Системы (5.1) и (5.2) будут эквивалентны в том случае, если все

i

y

, для

ri ,1

будут равны 0. Кроме того, считаю, что все

0

i

b

для

ri ,1

. В противном

случае соответствующие ограничения из системы (5.1) умножим на – 1. Для того

чтобы

i

y

были равны 0, мы должны преобразовать задачу таким образом, чтобы

все искусственные переменные

i

y

перешли в свободные неизвестные.

В этом случае система (5.2) после преобразования примет вид:

 















.

;

112211

1111122111111

rrrrnrnrrrrrrrr

rrnnrrrr

ycycxxxx









(5.3)

От системы (5.2) к системе (5.3) всегда можно перейти шагами симплекс-

метода. При таком переходе в качестве линейной формы рассматривают функцию

r

yEyyF 

21min

, (5.4)

46

равную сумме искусственных переменных. Переход заканчивают, когда

0

min

F

и

все искусственные переменные

i

y

переведены в свободные неизвестные.

Анализ вариантов решений

1. Если

0

min

F

, а все

i

y

переведены в свободные переменные, то задача не

имеет положительного решения.

2. Если

0

min

F

, а часть

i

y

осталась в базисе, то для перевода их в свободные

необходимо применять специальные приёмы.

В симплекс-таблице, соответствующей системе (5.3), после того как

0

min

F

,

а все

i

y

- свободные, вычёркивают строку для

min

F

и столбцы для

i

y

и решают

задачу для исходной линейной формы

min

Z

.

Рекомендуется вводить минимум искусственных переменных.

47

5.2. Второй алгоритм отыскания опорного плана.

Пусть задача линейного программирования записана в каноническом виде:













;

2211

11212111

mnmnmm

nn

bxaxaxa







(5.5)

;

2211min nn

xcxcxcZ  

(5.6)

0

i

b

,

mi ,1

,

0

j

x

,

nj ,1

.

Построим первую таблицу Жордана-Гаусса для задач (5.5) и (5.6). Для

единообразия вычислительной процедуры к исходной таблице приписываем

строку целевой функции:

n

mnmm

n

ccc

aaa







21

11211

0

1

m

b



.

1

n

m





(5.7)

После приведения системы ограничений к единичному базису целевая

функция, как и базисные переменные, будет выражена через свободные

переменные. Аналогичным приёмом я пользовался, когда решали задачи

графическим методом с числом переменных более двух.

Алгоритм метода

1. Запишем задачу в форме (5.7), при этом все элементы столбца свободных

членов

i

b

должны быть неотрицательны

0

i

b

,

mi ,1

. Уравнения системы (5.5),

в которых свободные члены отрицательны, предварительно нужно умножить на –

1.

2. Таблицу (5.7) преобразуем шагами Жордана-Гаусса исключений. При этом

на каждом шаге разрешающим может быть выбран любой столбец, содержащий

хотя бы один положительный элемент. Строка целевой функции на выбор

разрешающих столбцов влияние не оказывает.

3. Разрешающая строка определяется по наименьшему из отношений

свободных членов к элементам разрешающего столбца.

4. В процессе преобразований вычёркиваем строки, состоящие из одних

нулей.

48

5. Если в процессе преобразований встречается строка, все элементы которой

нули, а свободный член отличен от нуля, то задача не имеет решения. Если

встретится строка, в которой, кроме свободного члена, других положительных

элементов нет, то говорят, что задача не имеет положительных решений.

Пояснение. В п.1.1 алгоритма предполагается, что все элементы столбца

свободных членов неотрицательны. Это требование необязательно. В случае

когда в столбце свободных членов встречаются отрицательные числа, будем

пользоваться теоремой.

Теорема. Если разрешающий элемент выбирать по наименьшему

положительному симплекс-отношению, то после шага Жордана-Гаусса

свободный член в разрешающей строке становится положительным, а остальные

члены сохраняют свой знак.

Выбор разрешающего элемента производят иначе, а именно.

1. Просматривают строку, соответствующую какому-либо отрицательному

свободному члену. Выбирают в ней какой-либо отрицательный элемент –

соответствующий этому элементу столбец будет разрешающим.

2. Выбор разрешающего элемента производится по минимальному

положительному симплекс-отношению. Если задача разрешима, то через

конечное число шагов получают первое допустимое решение и можно применять

симплекс-метод.

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

является также и оптимальным решением.

49

6. Двойственные задачи линейного программирования.

6.1. Взаимодвойственные задачи.

Рассмотрим задачу об использовании ресурсов. Пусть предприятие №1

производит

n

видов продукции и использует

m

видов сырья. Известна прибыль,

получаемая с единицы продукции

j

с

,

nj ,1

. Известны технологические

коэффициенты

ij

a

,

mi ,1

,

nj ,1

Требуется организовать производство так,

чтобы предприятию была обеспечена максимальная прибыль.

Таблица 6.1

Исходные данные

Цены

на ресурсы

Запасы

сырья

Продукция

П

1

П

2



П

n

1

u

2

u



m

u

1

a

2

a



m

a

11

a

21

a



1m

a

12

a

22

a



2m

a



n

a

1

n

a

2



mn

a

Прибыль с

единицы

продукции

1

с

2

с



т

с

Запишем в общем виде экономико-математическую модель задачи об

использовании ресурсов. Для этого введём переменные

j

x

,

nj ,1

– количество

продукции j-го вида. Тогда ограничения на сырье запишутся в виде

.

;

2211

22222121

11212111

mnmnmm

nn

axaxaxa









(6.1)

Целевая функция, определяющая максимум прибыли, имеет вид

nn

xcxcxcZ  

2211max

; (7.2)

0

j

x

,

nj ,1

.

По этим же исходным данным сформулирую задачу по предприятию №2.

Допустим, предприятие №2 решило закупить все ресурсы, которыми

располагает предприятие №1. В этом случае предприятию №2 необходимо

установить оптимальные цены на эти ресурсы, исходя из следующих условий:

50

1) общая стоимость ресурсов для предприятия №2 должна быть

минимальной;

2) за каждый вид ресурса предприятию №1 надо уплатить не менее той

суммы, которую это предприятие может получить при переработке данного вида

ресурса в готовую продукцию.

Обозначу цены, по которым предприятие №2 покупает ресурсы у

предприятия №1, через

i

u

,

mi ,1

. Запишу экономико-математическую модель

для предприятия №2 с учётом вышеуказанных условий 1) и 2).

Целевая функция, определяющая минимальную суммарную стоимость

ресурсов, имеет вид

mm

uauauaL  

2211min

. (6.3)

В соответствии с условием 2) запишем систему ограничений:

.

;

2211

22222112

11221111

nmmnnn

mm

cuauaua









(6.4)

Сравню математические модели задач (6.1), (6.2) и (6.3), (6.4):

1) число неизвестных одной задачи равно числу ограничений другой задачи;

2) матрица коэффициентов системы ограничений получается одна из другой

путём транспортирования;

3) неравенства в системах ограничений имеют противоположный смысл;

4) свободные члены системы ограничений одной из задач становится

коэффициентами целевой функции другой задачи, коэффициенты целевой

функции превращаются в свободные члены ограничений;

5) целевые функции в задачах имеют противоположный смысл: в первой –

максимум, во второй – минимум.

Задачи линейного программирования, обладающие пятью указанными

формальными признаками, называются симметричными. Одна из них называется

основной, а другая – двойственной.

51

В линейном программировании кроме симметричных двойственных пар

существуют не симметричные двойственные пары, которые имеют следующий

вид:

основная задача

;

2211

11212111

mnmnmm

nn

axaxaxa









(6.5)

nn

xcxcxcZ  

2211max

; (6.6)

0

j

x

,

nj ,1

;

двойственная задача

mm

ybybybL  

2211max

(6.7)

.

;

2211

11221111

nmmnnn

mm

cyayaya









(6.8)

Эти задачи отличаются от симметричной пары двумя особенностями:

1) ограничения задачи (6.5) – (6.6) выражены уравнениями вместо

неравенств;

2) в задаче (6.7) – (6.8) отсутствуют условия не отрицательности переменных

i

y

,

mi ,1

.

Общее правило построения двойственной пары.

К пяти признакам сформулированным ранее, необходимо добавить

следующие:

1) в исходной ограничения неравенства следует записывать со знаком



,

если целевая функция стремится к минимуму, и со знаком



, если целевая

функция стремится к максимуму;

2) каждому ограничению неравенства исходной задачи соответствует в

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

0

i

y

;

3) каждому условию равенства соответствует переменная

i

y

без ограничения

на знак, и наоборот: не отрицательным переменным

k

x

из основной задачи в

двойственной задаче соответствуют ограничения неравенства, а неограниченным

по знаку переменным соответствуют равенства.

52

Курсовая работа - Сведение матричной игры к задаче линейного программирования

Подождите немного. Документ загружается.