Кемеровский колледж статистики, экономики  и  информационных технологий – филиал государственного образовательного учреждения высшего профессионального образования «Московский государственный университет экономики, статистики и информатики» (МЭСИ) 
 
 
 
 

Курсовой проект

 по  Математическим  Методам

пояснительная записка

КП.230105.ММ.00.00.ПЗ 
 
 
 
 
 
 
 
 
 
 
 
 

Кемерово 2009

    

 Данный курсовой проект выполнил Виданов Константин Викторович. На тему:  «Двойственный симплекс метод» 230105, город Кемерово 2009 год.

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

Содержание 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

 

                                                                Введение 

    Использование идей двойственности в сочетании с общей идеей симплекс-метода позволило разработать еще один метод решения задач ЛП - двойственный симплекс-метод. Впервые этот метод был предложен Лемке в 1954г. Решение задачи ЛП двойственным симплекс-методом сводится к отысканию оптимального плана прямой задачи последовательным переходом от одного базиса к другому.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

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

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

    Найти вектор Х =(x₁, x₂, …, x_n), который удовлетворяет ограничениям

     a₁₁x₁ + a₁₂x₂ + … + a_1nx_n £ b_1,

    a₂₁x₁ + a₂₂x₂ + … + a_2nx_n £ b_2,                       x_j ³ 0 (j =1,2, ..., n)

    …………………………………

    a_m1x₁ + a_m2x₂ + … + a_mnx_n £ b_m,

 

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

    Z = C₁x₁ + C₂x₂ + … + C_nx_n,

    Оценим  ресурсы, необходимые для изготовления продукции. За единицу стоимости  ресурсов примем единицу стоимости  выпускаемой продукции. Обозначим через у_i (j =1,2, ..., m) стоимость единицы i-го ресурса. Тогда стоимость всех затраченных ресурсов, идущих на изготовление единицы j-й продукции, равна . Стоимость затраченных ресурсов не может быть меньше стоимости окончательного продукта, поэтому должно выполняться неравенство ³ C_j, j =1,2, ..., n. Стоимость всех имеющихся ресурсов выразится величиной . Итак, двойственную задачу  можно сформулировать следующим образом.

    Найти вектор Y =(y₁, y₂, …, y_n), который удовлетворяет ограничениям

     a₁₁y₁ + a₁₂y₂ + … + a_m1y_m £ C_1,

    a₁₂y₁ + a₂₂y₂ + … + a_m2y_m £ C_2,                       y_j ³ 0 (i =1,2, ..., m)

    …………………………………

    a_1ny₁ + a_2ny₂ + … + a_mny_m £ C_m,

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

    f  = b₁y₁ + b₂y₂ + … + b_my_m.

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

    Исходная  задача. Сколько и. какой продукции x_j  (j =1,2, ..., n) необходимо произвести, чтобы при заданных стоимостях C_j  (j =1,2, ..., n) единицы продукции и размерах имеющихся ресурсов b_i  (i =1,2, ..., n) максимизировать выпуск продукции в стоимостном выражении.

     Двойственная  задача. Какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов b_i и величинах стоимости единицы продукции C_i минимизировать общую стоимость затрат?

    Переменные  у_i называются оценками или учетными, неявными ценами.

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

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

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

    Исходная  задача. Найти матрицу-столбец X = (x₁, x₂, …, x_n), которая удовлетворяет ограничениям

    (1.1)                        AX = A₀, Х ³ 0

    и минимизирует линейную функцию Z = СХ.

    Двойственная  задача. Найти матрицу-строку Y = (y₁, y₂, …, y_m), которая удовлетворяет ограничениям

    (1.2)                         YA £ С

    и максимизирует линейную функцию  f = YA₀

    В обеих задачах C = (c₁, c₂, …, c_n) - матрица-строка, A₀ = (b₁, b₂, …, b_m) — матрица-столбец, А = (a_ij) — матрица коэффициентов системы ограничений. Связь между оптимальными планами пары двойственных задач устанавливает следующая теорема.

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

    min Z = max f.

    Если  линейная функция  одной из задач  не ограничена, то другая не имеет решения.

     Доказательство. Предположим, что исходная задача обладает оптимальным планом, который получен симплексным методом. Не нарушая общности, можно считать, что окончательный базис состоит из т первых векторов A₁, A₂, ..., A_m. Тогда последняя симплексная таблица имеет вид табл. 1.1.

    Таблица 1.1

 

    Пусть D — матрица, составленная из компонент векторов окончательного базиса A₁, A₂, ..., A_m; тогда табл. 1.1 состоит из коэффициентов разложения векторов A₁, A₂, ..., A_n исходной системы по векторам базиса, т. е. каждому вектору A_j в этой таблице соответствует такой вектор X_j что

    (1.3)                   A_j = DX_j (j= 1,2, ,.., n).

     Для оптимального плана получаем

    (1.4)                   A₀ = DX*,

    где X* = (x*₁, x*₂, …, x*_m).

Обозначим через  матрицу, составленную из коэффициентов разложения векторов А_j (j = 1, 2, ..., n), записанных в табл. 1.1. Тогда, учитывая соотношения (1.3) и (1.4), получаем:

    (1.5)                      A = D ,  D^-1A = ,

    (1.6)                    A₀=DX*;  D^-1A₀ = X*,

(1.7)                        min Z= C*X*,

    (1.8)                        = C* —C £ 0,

    где С* = (C*₁, C*₂, …, C*_m), С = (C₁, C₂, …, C_m, C_m+1, …, C_n), a = (C*X₁ – C₁; С*Х₂  - С₂, ..., C*X_n – C_n) = (Z₁ – С₁; Z₂  - C₂; ..., Z_n — C_n) — вектор, компоненты которого неположительны, так как они совпадают с Z_j — C_j £ 0, соответствующими оптимальному плану.

    Оптимальный план исходной задачи имеет вид X* = D^-1 А₀, поэтому оптимальный план двойственной задачи ищем в виде

    (1.9)                           Y* = C*D^-1.

    Покажем, что Y* действительно план двойственной задачи. Для этого ограничения (1.2) запишем в виде неравенства YA — С £ 0, в левую часть которого подставим Y*. Тогда на основании (1.9), (1.5) и (1.8) получим

    Y* А – С = С* D^-1А – С = С* - С £ 0,

    откуда  находим Y*A £ С.