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

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

n1.docx

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





Решение.

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

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



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





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



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



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





















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




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

Ответ:

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

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



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



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

;



.

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

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

;



.

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



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



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

Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации