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

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

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

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

КУРСОВАЯ

на тему:

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

Студент группы МЭК 1-1 - А.С. Кормаков

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

МОСКВА – 2001

Содержание

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

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

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

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

5. Двойственный симплексный метод........................................................... 12

6. Список используемой литературы............................................................ 14

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

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

Связь исходной и двойственной задач состоит в том, что коэффици­енты 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_1n x_n £ b_1,

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

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

a_m1 x₁ + a_m2 x₂ + … + a_mn x_n £ b_m,

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

Z = C₁ x₁ + C₂ x₂ + … + C_n x_n ,

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

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

a₁₁ y₁ + a₁₂ y₂ + … + a_m1 y_m £ C_1,

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

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

a_1n y₁ + a_2n y₂ + … + a_mn y_m £ C_m,

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

f = b₁ y₁ + b₂ y₂ + … + b_m y_m .

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

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

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

Переменн

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать