НАУЧНАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Двойственный симплекс-метод и доказательство теоремы двойственности
Двойственный симплекс-метод и доказательство теоремы двойственности
ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Кафедра математики
КУРСОВАЯ
на тему:
Двойственный симплекс-метод и доказательство теоремы двойственности.
Студент группы МЭК 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 + | 
