Главная | Обратная связь

МЕТОДИКА СОСТАВЛЕНИЯ ДВОЙСТВЕННОЙ ЗАДАЧИ

ЕН.Ф.01.02 ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ

Лабораторное занятие №5. Двойственные задачи

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

 

Направление подготовки дипломированного специалиста

080500 Менеджмент

 

Специальность 080502 Экономика и управление на предприятии

(в аграрном производстве)

 

 

Уфа - 2010

УДК 519.86

ББК 65.23

Л 12

 

Рекомендовано к изданию методической комиссией экономического факультета (протокол № 3 от_25 ноября 2010 г.)

 

Составитель: доцент Шатова В.С.

 

Рецензент: ст. преподаватель кафедры информатики и ИТ Саитова Э.С.

 

 

Ответственный за выпуск:

зав.кафедрой статистики и информационных систем в экономике

д.э.н., профессор Рафикова Н.Т.

 

г. Уфа, БГАУ, кафедра статистики и информационных систем в экономике

 

 

ОГЛАВЛЕНИЕ

 

 

Введение

1Цель и задачи………………………………………………………….. 6

2 Методика составления двойственной задачи…….……….………... 6

2.1 Алгоритм составления двойственной задачи……………….……..6

2.2 Построение двойственной задачи……………….……………...….6

3 Задания для самостоятельной работы……………….……..…………10

4 Вопросы для самоконтроля…………………………….…………… ….12

Библиографический список…………………………….…………….…12

 

 

ВВЕДЕНИЕ

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

Экономико-математические модели и содержательные экономические интерпретации исходной и двойственной задач можно представить следующим образом (таблица1).

 

Таблица 1- Содержательные интерпретации двойственных задач

 

Задача 1 (исходная)

Задача П (двойственная)

Z = c1x1 + c2x2 +…+cnxn => max при ограничениях: a11x1 + а12x2 +…+ а1nxn < b1 a21x1 + a22x2 +…+ а2nxn < b2 ……………………………… am1x1 + аm2x2 +…+ аmnxn < bm   и условии неотрицательности: x1 ≥0,x2 ≥0,… ,xn ≥0. Составить такой план выпуска продукции Х = (х1, х2, …, хn), при котором прибыль (выручка) от ее реализации будет максимальной при условии, что потребление ресурсов по каждому виду не превзойдет имеющихся запасов.

F = b1y1 + b2y2 +…+ bmym =>min при ограничениях: a11у1 + а21у2 +…+ аm1y1 ≥c1 a12y1 + а22y2 +…+ аm2y2 ≥c2 ……………………………… a1ny1 + а2ny2 +…+ аmnym ≥cn   и условии неотрицательности: y1≥0,y2 ≥0, … ,ym ≥ 0.   Найти такой набор цен (оценок) ресурсов Y = (y1, y2, …, ym), при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции.

 

Цены ресурсов y₁, y₂, …, y_m в экономической литературе называют: учетные, неявные, теневые.Смысл их состоит в том, что это условные, “ненастоящие” цены. В отличии от “внешних” цен с₁, с₂, …, с_n на продукцию, известных, как правило, до начала производства, цены ресурсов y₁, y₂, …, y_m являются внутренними, так как они определяются непосредственно в результате решения задачи, а не задаются извне. Поэтому их чаще называют оценками ресурсов.

 

 

Независимо от содержательной интерпретации экономических параметров, обе задачи обладают следующими свойствами:

1. В одной задаче ищут максимум целевой функции, в другой – минимум.

2. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений в другой.

3. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

4. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида «< », а в задачах минимизации – все неравенства вида « ≥».

5. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу:

 

 

a₁₁ а₁₂ … а_1n

 

для задачи I А = a₂₁ а₂₂ … а_2n ,

_{………………………………}

 

a_m1 а_m2 … а_mn

 

 

a₁₁ а₂₁ … а_m1

 

для задачи II А^т = a₁₂ а₂₂ … а_{m2 .}

_{………………………………}

 

a_1n а_2n … а_mn

 

6. Каждому ограничению неравенства исходной задачи соответствует в двойственной задаче условие неотрицательности переменных.

7. Каждому ограничению вида равно исходной задачи соответствует переменная без ограничения на знак в двойственной задаче.

8. Неотрицательным переменным исходной задачи соответствуют ограничения неравенства в двойственной задаче.

9. Неограниченным по знаку переменным исходной задачи соответствуют ограничения вида равно двойственной задачи.

Две задачи I и II линейного программирования, обладающие указанными свойствами, называются симметричными взаимно двойственными задачами или просто двойственными задачами.

ЦЕЛЬ И ЗАДАЧИ

Цель: Освоить методику составления двойственных задач линейного программирования.

Задачи: 1. Научиться формулировать задачу, двойственную к исходной.

2. Научиться формулировать и давать экономическую интерпретацию задачи, двойственной к задаче использования ресурсов.

3. Усвоить алгоритм составления двойственной задачи.

4. Составить и решить двойственную задачу.

5. Сформулировать краткие выводы по результатам решения задачи.

Требование к организации рабочего места (оборудование, приборы, материалы): Для выполнения задания необходимо наличие компьютера. Программное обеспечение: пакет прикладных программ линейной оптимизации SIMPLEX, пакет экономических расчетов PER, программа обработки электронных таблиц EXCEL.

МЕТОДИКА СОСТАВЛЕНИЯ ДВОЙСТВЕННОЙ ЗАДАЧИ

 

2.1 Алгоритм составления двойственной задачи.

Составление двойственной задачи можно осуществить по следующему алгоритму.

1. Привести все неравенства системы ограничений исходной задачи к одному смыслу, т.е., если исходная задача решается на максимум, то все неравенства системы ограничений привести к виду «< », если на минимум – к виду « ≥». Для этого неравенства, в которых данное требование не выполняется, умножить на -1.

2. Составить расширенную матрицу системы А₁, в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в целевой функции.

3. Найти матрицу А ^т _1, транспонированную к матрице А₁.

4. Сформулировать двойственную задачу на основании полученной матрицы А ^т₁ и условий неотрицательности и неограниченности по знаку переменных.