реферат. реферат 1.. Дисциплина Методы оптимальных решений Реферат Двойственность в линейном программировании

• Название: Дисциплина Методы оптимальных решений Реферат Двойственность в линейном программировании
• Анкор: реферат
• Дата: 24.04.2023
• Размер: 30.35 Kb.
• Имя файла: реферат 1..docx
• Тип: Реферат; #1086315

  

Министерство науки и высшего образования Российской Федерации

ФГАОУ ВО «Уральский федеральный университет

имени первого Президента России Б. Н. Ельцина»

Институт экономики и управления

Кафедра правового регулирования экономической деятельности

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

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

Выполнил студент группы ЭУ-213608

Лебедев И.С.

 

Екатеринбург

2023

Содержание

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

Введение

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

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

Каждой задаче линейного программирования соответствует двойственная, тесно связанная с исходной, которая может быть решена непосредственно через решение исходной. Основным применением задач линейного программирования является оптимизация расходов на производство товаров, используя доступные ресурсы bi, где i = 1, 2, …, m. Цель предприятия заключается в получении максимальной стоимости продукции из ограниченных ресурсов. Модель задачи линейного программирования представляет собой двойственный симплекс линейный программирования.
F = с1х1 + с2х2 + … + сnхn max.

II) a11х1 + а12х2 + … + а1nхn ≤ b1,

a21х1 + а22х2 + … + а2nхn ≤ b2,

am1х1 + аm2х2 + … + аmnхn ≤ bm.

хj ≥ 0, j = 1, 2, …, n.
Допустим, что компания решила отказаться от производства и продать свои ресурсы. Однако возникает вопрос о цене, за которую можно продать ресурсы, устраивающую и продавца и покупателя. Покупатель заинтересован в минимальной цене, тогда как продавец стремится получить не менее стоимости, чем за реализованные готовые товары. В таком случае, двойственная модель будет описывать функцию покупателя и ограничения продавца (оценить ресурсы, необходимые для производства единицы продукции и ограничить их стоимостью). Неотрицательность переменных цены будет обеспечена тем, что цена ресурса не может быть отрицательной. Введя оценку ресурса как цену ресурса (значение ui0(i = 1, 2, …, m)), мы получим новую модель:

F = b1u1 + b2u2 + … + bmum  min.

II) a11u1 + a21u2 + … + am1um  c1,

a12u1 + a22u2 + … + am2um  c2

a1nu1 + a2nu2 + … + amnum  cn. III) ui0, i = 1, 2, …, m.

Сопоставим обе задачи: - первая – задача на максимум (zmax), вторая – на минимум (Fmin); - в первой система ограничений типа , во второй ; - в первой задаче n неизвестных и m ограничений, во второй m неизвестных и n ограничений; - коэффициенты в целевых функциях и величины в правых частях неравенств при переходе из одной задачи в другую меняются местами (в первой задаче cj – коэффициенты целевой функции, во второй cj – свободные члены; в первой задаче bi – свободные члены, во второй bi – коэффициенты целевой функции); - матрицы коэффициентов в первой и второй задаче являются транспонированными относительно друг друга (строки и столбцы поменялись местами).
Это указывает на тесную взаимосвязь между двумя задачами, которые являются двойственной парой в линейном программировании. Первая из них называется прямой или исходной задачей, а вторая - двойственной задачей (хотя математически любая из них может быть рассмотрена как исходная).
Алгоритм составления двойственной задачи:

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

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

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

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

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

Особенности:

Линейное программирование имеет две задачи - исходную и двойственную, которые могут быть симметричными или несимметричными. Обе задачи могут быть решены отдельно с помощью симплексного или графического метода. Однако, для одновременного решения используется двойственная симплекс-таблица. Чтобы составить модель двойственной задачи, необходимо привести систему ограничений к соответствующему виду, домножив неподходящие неравенства на (-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. 
   Основные теоремы теории двойственности и ее экономическое содержание
   

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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