Реферат (Методы оптимальных решений). Реферат(Методы оптимальных решений). Реферат Двойственность в линейном программировании. Выполнил студент группы зэг19 Липатников А. И

• Название: Реферат Двойственность в линейном программировании. Выполнил студент группы зэг19 Липатников А. И
• Анкор: Реферат (Методы оптимальных решений
• Дата: 14.01.2022
• Размер: 43.69 Kb.
• Имя файла: Реферат(Методы оптимальных решений).docx
• Тип: Реферат; #330798

  

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ  

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ  

«Российский государственный геологоразведочный университет

имени  СЕРГО  ОРДЖОНИКИДЗЕ» (МГРИ-РГГРУ)

    

Кафедра производственного и финансового менеджмента.

Дисциплина «Методы оптимальных решений»

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

Выполнил студент группы ЗЭГ-19

Липатников А.И.

Принял:  

 Кандидат экономических наук  

Забайкин.Ю.В

 

Москва

2020

Содержание

1	Введение	3
2	Постановка и модель двойственной задачи	4
3	Методы решения	8
4	Теоремы теории двойственности и ее экономическое содержание	11
5	Заключение	14
6	Список литературы	15

Введение

Двойственность в линейном программировании - принцип, заключающийся в том, что для каждой задачи линейного программирования можно сформулировать двойственную задачу.

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

Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП.

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

Различают симметричные, несимметричные и смешанные двойственные задачи.

1. 
   Постановка и модель двойственной задачи
   

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

Напомним, что в основе задачи линейного программирования рассматривается предприятие, имеющее ресурсы b_i, где i = 1, 2, …, m. Оно тратит их на изготовление готовой продукции и эту продукцию реализует. При этом ставится цель – получить максимум продукции в стоимостном выражении не перерасходуя ресурсы. Модель задачи выглядит следующим образом: двойственный симплекс линейный программирование
I) Ζ = с₁х₁ + с₂х₂ + … + с_nх_n max.

II) a₁₁х₁ + а₁₂х₂ + … + а_1nх_n ≤ b₁,

a₂₁х₁ + а₂₂х₂ + … + а_2nх_n ≤ b₂,

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

a_m1х₁ + а_m2х₂ + … + а_mnх_n ≤ b_m.

III) х_j ≥ 0, j = 1, 2, …, n.
Предположим, что некоторое предприятие решило не тратить ресурсы на изготовление продукции, а продать эти ресурсы. Тогда возникает вопрос: по какой цене продавать ресурсы? Цена должна устраивать как продавца, так и покупателя. Интерес покупающей стороны заключается в том, чтобы заплатить за ресурсы как можно меньше, а интерес продающей стороны – в том, чтобы получить за ресурсы не меньше того, что она получила бы за реализованный готовый товар.

Тогда, в так называемой двойственной модели, целевая функция будет описывать интерес покупающей стороны, система ограничений – интерес продающей стороны(необходимо оценить ресурсы, которые пошли бы на изготовление единицы продукции и стоимость этих ресурсов ограничить ценой реализованной единицы продукции). Третье условие (неотрицательность переменных величин) будет выполняться в силу того, что цена единицы ресурса не может быть отрицательной. Введя в качестве цены единицы ресурса величину u_i0(i = 1, 2, …, m), ее еще называют оценкой ресурса (или двойственной оценкой), получим следующую модель:
I) F = b₁u₁ + b₂u₂ + … + b_mu_m  min.

II) a₁₁u₁ + a₂₁u₂ + … + a_m1u_m  c₁,

a₁₂u₁ + a₂₂u₂ + … + a_m2u_m  c₂,

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

a_1nu₁ + a_2nu₂ + … + a_mnu_m  c_n.

III) u_i0, i = 1, 2, …, m.
Сопоставим обе задачи:

- первая – задача на максимум (zmax), вторая – на минимум (Fmin);

- в первой система ограничений типа , во второй ;

- в первой задаче n неизвестных и m ограничений, во второй m неизвестных и n ограничений;

- коэффициенты в целевых функциях и величины в правых частях неравенств при переходе из одной задачи в другую меняются местами (в первой задаче c_j – коэффициенты целевой функции, во второй c_j – свободные члены; в первой задаче b_i – свободные члены, во второй b_i – коэффициенты целевой функции);

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

Таким образом, видно, что обе задачи тесно связаны между собой. Они образуют пару задач, называемую в линейном программировании двойственной парой. Первую из них обычно называют прямой (или исходной) задачей, а вторую – двойственной задачей (с чисто математической точки зрения за исходную может быть принята любая из задач двойственной пары).

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

1) тип экстремума целевой функции меняется;

2) каждому ограничению исходной задачи ставится в соответствие переменная двойственной задачи;

3) свободные члены исходной задачи становятся коэффициентами при переменных в целевой функции двойственной задачи;

4) каждый столбец коэффициентов в системе ограничений формирует ограничение двойственной задачи, при этом тип неравенства меняется; коэффициенты при переменных в целевой функции исходной задачи становятся свободными членами в соответствующих неравенствах двойственной задачи.

Рассмотрим конкретный пример построения двойственной модели:

исходная задача:
I) Z = 6x₁ + 4x₂ max.

II)2x₁ +4x₂ ≤ 8,

2x₁ +x₂ ≤ 6.

III)x₁ ≥ 0, x₂ ≥ 0.
двойственная задача:
I) F = 8u₁ + 6u₂  min.

II) 2u₁ + 2u₂ ≥ 6,

4u₁ + u₂ ≥ 4.

III) u₁ ≥ 0, u₂ ≥ 0.
Следует отметить, что:

- математические модели пары двойственных задач могут быть симметричными и несимметричными. В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной – в виде неравенств, причем в последней переменные могут быть и отрицательными. В симметричных задачах система ограничений как исходной, так и двойственной задачи задается неравенствами, причем на двойственные переменные налагается условие неотрицательности. Чаще рассматриваются симметричные взаимодвойственные задачи;

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

2. 
   Методы решения
   

Каждая из задач двойственной пары может решаться отдельно. При этом используется как симплексный метод, так и графический (в случае если задача содержит две переменные). Одновременное решение задач реализуется с использованием, так называемой, двойственной симплекс-таблицы.

Подготовленные для записи в симплекс таблицу модели будут выглядеть следующим образом:

исходная задача (введем y_i  0):
I) Ζ = с₁х₁ + с₂х₂ + … + с_nх_n max.

II) y₁ = -a₁₁х₁ - а₁₂х₂ - … - а_1nх_n + b₁,

y₂ = -a₂₁х₁ - а₂₂х₂ - … - а_2nх_n + b₂,

…………………………………..

y_m = -a_m1х₁ - а_m2х₂ - … - а_mnх_n + b_m.

III) х_j ≥ 0, j = 1, 2, …, n.
двойственная задача (введем v_j  0):
I) F = b₁u₁ + b₂u₂ + … + b_mu_m  min.

II) v₁ = a₁₁u₁ + a₂₁u₂ + … + a_m1u_m - c₁,

v₂ = a₁₂u₁ + a₂₂u₂ + … + a_m2u_m - c₂,

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

v_n = a_1nu₁ + a_2nu₂ + … + a_mnu_m - c_n.

III) u_i0, i = 1, 2, …, m.
Обе модели записываются в двойственную симплекс-таблицу следующим образом (таблица 4):
Таблица 4 – Двойственная симплексная таблица

		v1	v2	…	vn	F
		-x1	-x2	…	-xn	Свободные члены
u1	y1	a11	a12	…	a1n	b1
u2	y2	a21	a22	…	a2n	b2
…	…	…	…	…	…	…
um	ym	am1	am2	…	amn	bm
Свободные члены	Z	-c1	-c2	…	-cn	0

Замечания:

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

- прежде чем составлять модель двойственной задачи, необходимо у исходной модели «выровнять» знаки, т.е. если целевая функция стремится к max, то все знаки в системе ограничений должны быть ≤, а если к min, то ≥. Система приводится в соответствие путем домножения обеих частей «неподходящего» неравенства на (-1). Например, чтобы записать модель, двойственную к приведенной модели

I) Z = 4x₁ + 2x₂ + 3x₃  min.

II) -4x₁ - 3x₂ +x₃ ≤ -4,

5x₁ + x₂+2x₃ ≥ 6.

III) x₁ ≥ 0, x₂ ≥ 0,x₃ ≥ 0,

необходимо исходную переписать в виде:

I) Z = 4x₁ + 2x₂ + 3x₃  min.

II) 4x₁ + 3x₂ - x₃ ≥ 4,

5x₁ + x₂+2x₃ ≥ 6.

III) x₁ ≥ 0, x₂ ≥ 0,x₃ ≥ 0.
Тогда двойственная задача будет выглядеть так:
I) F = 4u₁+6u₂  max.

II) 4u₁ + 5u₂ ≤ 4,

3u₁ + u₂ ≤ 2,

-u₁ + 2u₂ ≤ 3.

III) u₁ ≥ 0; u₂ ≥ 0;
- в центр двойственной симплекс-таблицы (таблицы 4) всегда ставится задача на max, вне зависимости от того какова целевая функция исходной задачи.

3. 
   Основные теоремы теории двойственности и ее экономическое содержание
   

В качестве основной теоремы двойственности выделяют следующую формулировку: если одна из взаимно двойственных задач имеет оптимальное решение, то и другая также имеет оптимальное решение, при этом соответствующие им оптимальные значения целевых функций равны (т.е. max z = min F).

Кроме этого варианта возможны следующие взаимоисключающие случаи:

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

- обе из рассматриваемых задач имеют пустые допустимые множества (т.е. обе не имеют решения).

С экономической стороны решение прямой задачи дает оптимальный план выпуска продукции, а решение двойственной задачи – оптимальную систему условных (или двойственных) оценок применяемых ресурсов.

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

Центральный вопрос, который рассматривается в теории двойственности, – это вопрос о ценности ресурса. Но ценности его не рыночной, а исключительно с внутренней точки зрения данного предприятия, с точки зрения эффективного использования этого ресурса в сложившейся структуре производства, определяемой технологической матрицей и удельными прибылями. При этом оценка ценности производится только в процессе использования ресурса в одном цикле производства. Это является элементом условности. Однако из всего этого вытекает основополагающая оценка ценности ресурса – сколько прибыли может принести вовлечение в производство еще одной единицы данного ресурса.

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

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

- в оптимальном плане, обеспечивающем максимум выпуска конечного продукта при изменяющихся ресурсах, суммарные затраты ресурсов на единицу конечной продукции минимальны (иначе за счет более экономичного их использования можно было бы увеличить выпуск и тем самым улучшить оптимальный план, что противоречит понятию оптимального плана как наилучшего с точки зрения принятого критерия);

- абсолютные значения оценок можно трактовать как некоторые расчетные «цены» ресурсов и потребностей, выраженные в тех же единицах, что и критерий, а знак «+» или «–» при этих «ценах» показывает, ведет ли увеличение данного фактора к возрастанию или уменьшению значения критерия;

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

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

Таким образом, двойственные оценки являются важнейшим результатом, вытекающим из теории двойственности, которая широко применяется на практике.

Заключение

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

Правила получения двойственной задачи из задачи исходной.

1. Если в исходной задаче ищется максимум целевой функции, то в двойственной ей - минимум.

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

3. В исходной ЗЛП все функциональные ограничения - неравенства вида «≤», а в задаче, двойственной ей, - неравенства вида «≥».

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

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

6. Условие неотрицательности переменных сохраняется в обеих задачах.

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

1. Белолипецкий В. М. Математическое моделирование в задачах. / В.М. Белолипецкий, Ю.И. Шокин. – М. : Финансы и статистика, 2002.- 774 с.

2. Красс М. С. Основы математики и ее приложения в экономическом образовании: Учебник. - 5-е изд., испр. и доп. / М.С. Красс, Б.П. Чупрынов. – М. : Дело, 2006. – 720 с.

3. Солодовников А. С. Математика в экономике. / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов. – М. : Изд–во МГУ, 1999. – 591 с.

4. Черемных Ю. Н. Математические методы в экономике. 2 - изд. / Ю.Н. Черемных. – М. : Дело и сервис, 2001. – 657 с.