4.2.3 Двойственные задачи ЗЛП

Август 8, 2022

Главная
Математика
4.2.3 Двойственные задачи ЗЛП

Содержание

2. Каждой задаче линейного программирования соответствует задача двойственная / сопряженная по отношению к исходной задаче b i
3. С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не менее той
4. Формулировка двойственной задачи: Найти такой набор оценок ресурсов, при которых общие затраты а ресурсы будут минимальными
5. Свойства взаимно двойственных задач: 1. В одной задаче ищут максимум целевой функции, а в другой минимум.
6. 5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче. 6.
7. Пример решения задачи. Составить двойственную задачу для заданной. Дана целевая функция f(x) = -x1 + 2x2
9. Скачать презентацию

Слайд 2

Каждой задаче линейного программирования соответствует задача двойственная / сопряженная по отношению

к исходной задаче
b i — запас ресурса S i, aij — число единиц потребляемого ресурса Si при производстве единицы продукции Pj
y1, y2, y3 -цены на ресурсы
Затраты на закупку этих ресурсов должны быть минимальными, т. е.:

Z(y) = b1 y1 + b2y2+b3y3→ min

Слайд 3

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

выручка была не менее той суммы, которую предприятие могло получить при переработке ресурсов в готовую продукцию.
На изготовление продукции Р1 расходуется а11 ресурса S1, а21 ресурса S2, а31 ресурса S3. Следовательно:
Цены на ресурсы величины не могут быть отрицательными, значит

a11 y1 + a12 y2 +a31y3 ≥ c1

a12 y1 + a22 y2 +a32y3 ≥ c2

Y1 , y2 ,y3 ≥ 0

Слайд 4

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

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

Слайд 5

Свойства взаимно двойственных задач:
1. В одной задаче ищут максимум целевой функции,

а в другой минимум.
2. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений в другой.
3. Каждая из задач задана в стандартной форме, причем в задаче на максимум все неравенства вида «≤ », а в задаче на минимум — все неравенства вида «≥».
4. Матрица коэффициентов при переменных в системах ограничений являются транспортированными друг к другу

Слайд 6

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

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

Слайд 7

Пример решения задачи.
Составить двойственную задачу для заданной.
Дана целевая функция f(x) =

-x1 + 2x2 →max
И система ограничений:
2x1 — x2 ≥ 1
-x1 + 4x2 ≤ 24
х1 — x2 ≤ 3
х1 + x2 ≥ 5
х1, x2 ≥ 0
Приведем систему неравенств к правильному виду (чтобы все знаки неравенств соответствовали задаче на максимум):
- 2x1 + x2 ≤ - 1
-x1 + 4x2 ≤ 24
х1 — x2 ≤ 3
- х1 - x2 ≤ - 5
х1, x2 ≥ 0

4.2.3 Двойственные задачи ЗЛП

Содержание

Каждой задаче линейного программирования соответствует задача двойственная / сопряженная по отношению

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

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

Свойства взаимно двойственных задач:1. В одной задаче ищут максимум целевой функции,

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

Пример решения задачи.Составить двойственную задачу для заданной.Дана целевая функция f(x) =

Похожие презентации

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

Свойства взаимно двойственных задач:
1. В одной задаче ищут максимум целевой функции,

Пример решения задачи.
Составить двойственную задачу для заданной.
Дана целевая функция f(x) =