Полная версия

Главная arrow Математика, химия, физика arrow Математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

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

Понятие двойственности

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

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

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

Найти вектор X = (* , х2, ..., xn), который удовлетворяет ограничениям

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

Оценим ресурсы, необходимые для изготовления продукции. За единицу стоимости ресурсов примем единицу стоимости выпускаемой продукции. Обозначим у. (i = 1, 2, ..., т) стоимость единицы /-го ресурса. Тогда стоимость всех затраченных ресурсов,

т

идущих на изготовление единицы j-й продукции, равна ^ауУ1

/=1

Стоимость затраченных ресурсов не может быть меньше стоимости окончательного продукта, поэтому должно

т

выполняться неравенство ^ауУ1 - C J = С 2,..., п. Стоимость всех

г=1

т

имеющихся ресурсов выразится величиной . Итак, двойст-

г=1

венную задачу можно сформулировать следующим образом.

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

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

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

Исходная задача. Сколько и какой продукции х. (J = 1, 2,..., п) необходимо произвести, чтобы при заданных стоимостях С., (/' = = 1,2,..., п) единицы продукции и размерах имеющихся ресурсов Ь. (/ =1,2,..., т) максимизировать выпуск продукции в стоимостном выражении.

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

b. и величинах стоимости единицы продукции С минимизировать общую стоимость затрат?

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

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>