ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ Кафедра математики КУРСОВАЯ на тему: Двойственный симплекс-метод и доказательство теоремы двойственности. Студент группы МЭК 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,
    
    и доставляет максимальное значение линейной функции
    Z = C1x1 + C2x2 + ... + Cnxn,
    Оценим ресурсы, необходимые для изготовления продукции. За единицу стоимости ресурсов примем единицу стоимости выпускаемой продукции. Обозначим через уi (j =1,2, ..., m) стоимость единицы i-го ресурса. Тогда стоимость всех затраченных ресурсов, идущих на изготовление единицы j-й продукции, равна . Стоимость затраченных ресурсов не может быть меньше стоимости окончательного продукта, поэтому должно выполняться неравенство ? Cj, j =1,2, ..., n. Стоимость всех имеющихся ресурсов выразится величиной . Итак, двойственную задачу можно сформулировать следующим образом.
    Найти вектор Y =(y1, y2, ..., yn), который удовлетворяет ограничениям
    a11y1 + a12y2 + ... + am1ym ? C1,
    a12y1 + a22y2 + ... + am2ym ? C2, yj ? 0 (i =1,2, ..., m)
    .......................................
    a1ny1 + a2ny2 + ... + amnym ? Cm,
    и доставляет минимальное значение линейной функции
    f = b1y1 + b2y2 + ... + bmym.
    Рассмотренные исходная и двойственная задачи могут быть экономически интерпретированы следующим образом.
    Исходная задача. Сколько и. какой продукции xj (j =1,2, ..., n) необходимо произвести, чтобы при заданных стоимостях Cj (j =1,2, ..., n) единицы продукции и размерах имеющихся ресурсов bi (i =1,2, ..., n) максимизировать выпуск продукции в стоимостном выражении.
    Д в о й с т в е н н а я з а д а ч а. ............