ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Кафедра математики

КУРСОВАЯ

на тему:

Двойственный симплекс-метод и доказательство теоремы двойственности.

Студент группы МЭК 1-1 - А.С.

Кормаков

Научный руководитель -

Солодовников А.С.

МОСКВА – 2001

Содержание

1. Двойственность в линейном программировании 3

2. Несимметричные двойственные задачи. Теорема двойственности. 4

3. Симметричные двойственные задачи 9

4. Виды математических моделей двойственных задач 11

5. Двойственный симплексный метод 12
6. Список используемой литературы 14

1. Двойственность в линейном программировании

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

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

В качестве примера рассмотрим задачу использования ресурсов.
Предприятие имеет т видов ресурсов в количестве bi (i = 1, 2, ..., m) единиц, из которых производится n видов продукций. Для производства 1 ед. i- й продукции расходуется aij ед. t-гo ресурса, а ее стоимость составляет Cj ед. Составить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Обозначим через xj (j =1,2, ..., n) количество ед. j-й продукций, Тогда исходную задачу сформулируем так.

Найти вектор Х =(x1, x2, …, xn), который удовлетворяет ограничениям

a11x1 + a12x2 + … + a1nxn ( b1, a21x1 + a22x2 + … + a2nxn ( b2, xj ( 0 (j =1,2,
..., n)

………………………………… am1x1 + am2x2 + … + amnxn ( bm,

и доставляет максимальное значение линейной функции