Решение - Симплекс метод и двойственная задача - файл n1.docx

приобрести
Решение - Симплекс метод и двойственная задача
скачать (142.5 kb.)
Доступные файлы (1):

n1.docx

143kb.

09.09.2012 02:30

скачать

n1.docx

Решить задачу линейного программирования симплекс методом, затем найти решение двойственной задачи.

Решение.

Решим задачу на максимум.

Математическая модель данной задачи имеет вид:

при ограничениях

Преобразуем задачу к каноническому виду. Введем три (по количеству ограничений) дополнительных неотрицательных переменных

и добавим по одному из них к левым частям неравенств, преобразуя их в равенства. Получаем задачу:

при ограничениях

Каждая из переменных

входит только в одно из уравнений системы. Возьмем эти переменные в качестве базисных, а переменные

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

3

4

1

0

0

0

0

2

4

-5

1

0

0

14

3,5

0

9

5

1

0

1

0

27

5,4

0

0

1

1

0

0

1

5

5

-3

-4

-1

0

0

0

0

В столбце БП записаны базисные переменные, включаемые в план; в С_б– прибыль единицы продукции, которая вводится в план, т.е. коэффициенты при базисных переменных в целевой функции; в столбце В – свободные величины; в правом крайнем столбце будем записывать промежуточные симплексные отношения; в остальных – коэффициенты при неизвестных уравнений. В верхней части этих столбцов отражаются коэффициенты при неизвестных целевой функции.

В нижней строке (целевой) записываются получаемые расчетным путем показатели: в столбце В – суммарная прибыль планового выпуска, в остальных столбцах – прибыль единицы продукции с отрицательным знаком.

Запишем начальный опорный план:

. Этот план не является оптимальным, так как в индексной строке есть отрицательные элементы.

Чтобы получить новый опорный план, выполним симплексные преобразования таблицы 1. Введем в базис переменную

, которой соответствует наибольшая по модулю отрицательная индексная оценка, т.е. в качестве разрешающего в предстоящем симплексном преобразовании надо взять 2-й столбец. Чтобы определить переменную, выводимую из базиса, составим симплексные отношения (элементы столбца В делим на соответствующие элементы разрешающего столбца) и выберем наименьшее из них:

Следовательно, из базиса надо исключить переменную

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

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

.

Аналогично определяются элементы индексной строки и столбца свободных членов.

В результате приходим к таблице 2:

Таблица 2

3

4

1

0

0

0

4

1/2

1

-5/4

1/4

0

0

7/2

-

0

13/2

0

29/4

-5/4

1

0

19/2

38/29

0

-1/2

0

9/4

-1/4

0

1

3/2

2/3

-1

0

-6

1

0

0

14

Выпишем опорный план:

. Однако этот план не является оптимальным, так как в индексной строке есть отрицательные элементы.

Чтобы получить новый опорный план, выполним симплексные преобразования таблицы 2.

Введем в базис переменную

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

Следовательно, из базиса надо исключить переменную

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

, относительно которого выполнятся симплексные преобразования.

Получим таблицу 3.


	3	4	1	0	0	0
4	2/9	1	0	1/9	0	5/9	13/3	39/2
0	73/9	0	0	-4/9	1	-29/9	14/3	42/73
1	-2/9	0	1	-1/9	0	4/9	2/3	-
	-7/3	0	0	1/3	0	8/3	29

Выпишем опорный план:

.

Однако этот план не является оптимальным, так как в индексной строке есть отрицательные элементы.

Чтобы получить новый опорный план, выполним симплексные преобразования таблицы 3.

Введем в базис переменную

, которой соответствует отрицательная индексная оценка, т.е. в качестве разрешающего в предстоящем симплексном преобразовании надо взять 1-й столбец. Cоставим симплексные отношения и выберем наименьшее из них:

Следовательно, из базиса надо исключить переменную

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

, относительно которого выполнятся симплексные преобразования.

Получим таблицу 4.


	3	4	1	0	0	0
4	0	1	0	9/73	-2/73	47/73	307/73
3	1	0	0	-4/73	9/73		42/73
1	0	0	1	-9/73	2/73	26/73	58/73
	0	0	0	15/73	21/73	127/73	2215/73

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

Ответ:

Составим математическую модель двойственной задачи.

Напишем матрицу исходной задачи:

и транспонируем ее. В результате получим матрицу двойственной задачи:

При этой матрице напишем модель задачи, двойственной к исходной задаче:

;

.

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

Запишем каноническую форму математической модели двойственной задачи, введя дополнительные (базисные) переменные

;

.

Соответствие между переменными двойственных задач примет вид (СП – свободные переменные, БП – базисные переменные):

В данном случае:

Следовательно, оптимальный план двойственной задачи имеет вид

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