Двойственная задача Записать двойственную задачу и дать ее экономический смысл

Двойственная задача
Записать двойственную задачу и дать ее экономический смысл.
Найти оптимальное решение двойственной задачи.
Определить целесообразность производства продукции 3, для которой на единицу продукции требуется 4 кг. сырья и 0,4 часа времени изготовления. Рыночная цена составляет 120 ден. ед. за единицу продукции.

Фирма выпускает два вида изделий A и B. Каждое изделие проходит обработку на двух технологических линиях. Известна таблица технологических коэффициентов tij – времени обработки (в минутах) каждого изделия на каждой технологической линии.
(табл. 4.2). Кроме этого, известны рыночная цена каждого изделия c1 и c2 и общее время работы каждой линии T1 и T2.

Изделие А
Изделие В
Время работы линии
Линия 1 t11 t12 T1
Линия 2 t21 t22 T2
Цена одного изделия c1 c2

Изделие А
Изделие В
Время работы линии
Линия 1 60 30 — N1 60(30 – N1)
Линия 2 30 – N2 60 60(30 – N2)
Цена одного изделия 50 – N1 50 – N2

N1 = 2
N2 = 4

Решение:

Изделие А
Изделие В
Время работы линии
Линия 1 60 28 1680
Линия 2 26 60 1560
Цена одного изделия 48 46

Обозначим:
план выпуска изделия А;
план выпуска изделия В.
Тогда затраты линии 1 и линии 2, необходимые для производства плана будут равны соответственно:
60×1+28×2
26×1+60×2
План будет допустимым, если затраты для линии 1 и линии 2 не превосходят общего времени работы каждой из линий, т.е. выполняются неравенства:
60×1+28×2 ≤ 1680
26×1+60×2 ≤ 1560
Целевой функцией служит выручка от реализации допустимого плана Z=48×1+46×2 при ограничениях
60×1+28×2 ≤ 1680
26×1+60×2 ≤ 1560
x1, x2 ≥ 0

Математическая модель в стандартной форме:
Z=48×1+46×2 → max
60×1+28×2 ≤ 1680
26×1+60×2 ≤ 1560
x1, x2 ≥ 0
Для канонической формы эти ограничения нужно преобразовать в равенства. Для этого введём две дополнительные переменные
остаток от производства на линии 1 (остаток времени обработки)
остаток от производства на линии 2 (остаток времени обработки).
Математическая модель в канонической форме:
Z=48×1+46×2 +0s1+0s2→ max
60×1+28×2 +s1= 1680 (1)
26×1+60×2 +s2=1560
x1, x2 , s1 , s2 ≥ 0

Найдём все базисные решения.
Полученные ограничения образуют систему двух уравнений с четырьмя неизвестными. Среди бесконечного множества решений этой системы базисные решения получаются следующим образом. Две переменных приравняем к 0. Эти переменные назовём свободными. Значения остальных переменных получаем из решения системы. Эти переменные назовём базисными. Базисное решение называется допустимым, если оно неотрицательно.
1) Пусть свободные переменные. Подставляя значения (1), получаем систему уравнений
s1= 1680
s2=1560
Следовательно, базисное решение имеет вид

Базисное решение означает, что изделия А и изделия В не производятся. Это базисное решение является допустимым. Выручка от реализации этого плана составит
Z=48×1+46×2 +0s1+0s2=0
2) Пусть свободные переменные. Подставляя значения в систему получаем систему
28×2 = 1680
60×2 +s2=1560
Следовательно, базисное решение имеет вид

Читайте также:  Привести формулу к линейному виду Y= АХ + В3 Определить параметры А и В

Это базисное решение означает, что изделие А не производится, изделие В производится в количестве 60 ед., время изготовления продукции на линии 1 используется полностью, для производства на линии 2 не хватает 2040 минут работы. Это базисное решение не является допустимым.
3) Пусть свободные переменные. Подставляя значения в (1) получаем систему
28×2 +s1= 1680
60×2 =1560
для базисных переменных и . Следовательно, базисное решение имеет вид
.
Это базисное решение означает, что изделие А не производится, изделие В производится в количестве 26 единиц, время изготовления продукции линии 1 используется не полностью и его остаток составляет 952 минут, а на линии 2 используется полностью. Это базисное решение является допустимым. Выручка от реализации этого плана составит
Z=48×1+46×2 +0s1+0s2=46*26=1196 ден.ед.
4) Пусть свободные переменные. Подставляя значения в (1) получаем систему
60×1 = 1680
26×1+s2=1560
для базисных переменных . Следовательно, базисное решение имеет вид

Базисное решение означает, что изделия А производится в количестве 28 ед., изделие В не производится, время изготовления продукции линии 1 используется полностью, а время изготовления линии 2 не полностью используется, его остаток составляет 832 минут. Это базисное решение является допустимым. Выручка от реализации этого плана составит
Z=48×1+46×2 +0s1+0s2=48*28=1344 ден.ед.
5) Пусть свободные переменные. Подставляя значения в (1) получаем систему
60×1+s1= 1680
26×1 =1560
для базисных переменных . Следовательно, базисное решение имеет вид
.
Это базисное решение означает, что изделия А производится 60 ед., изделие В не производится, не хватает времени обработки 192 минут для первой линии, а время обработки второй линии используется полностью. Это базисное решение не является допустимым.
6) Пусть свободные переменные. Тогда базисные переменные и найдём из системы уравнений
60×1+28×2 = 1680
26×1+60×2 =1560
Отсюда следует, что базисное решение имеет вид

Это решение означает, что изделия А производятся в количестве 19,89 ед., изделия В производятся в количестве 17,38 ед., время обработки на каждой из линий используется полностью. Это базисное решение является допустимым. Выручка от реализации составит
Z=48×1+46×2 +0s1+0s2=48*19,89+46*17,38 =1754,2 ден.ед.

Определим оптимальное базисное решение.
Из теории линейного программирования следует, что оптимальное решение можно найти среди допустимых базисных решений. Отсюда следует, что для определения оптимального решения нужно вычислить значения целевой функции на всех допустимых базисных решениях. Оптимальным будет базисное решение, на котором значение целевой функции наибольшее.
В таблице 1.1 приведены все допустимые базисные решения и соответствующие им значения выручки .
двойственный задача равновесный спрос полезность товар
Таблица 1.1
№ Базисные переменные Небазисные переменные
1 s1=1680 s2=1560 0
2 x2=26 s1=952 1196
3 x1=28 x2=832 1344
4 x1=19.89 x2=17.38 1754,2

Читайте также:  Из генеральной совокупности с дискретным изменением признака произведена выборка объема

Максимальное значение выручки достигается на четвёртом базисном решении в этой таблице

Следовательно, изделие А производится в количестве 19,89 ед., изделие В производится в количестве 17,38 ед., время обработки на каждой из линий используется полностью ().

Графическое решение задачи
Рассмотрим задачу в стандартной форме: найти переменные , которые обеспечивают максимальное значение функции
Z=48×1+46×2
при ограничениях
60×1+28×2 ≤ 1680
26×1+60×2 ≤ 1560
x1, x2 ≥ 0
На горизонтальной оси прямоугольной системы координат будем откладывать план выпуска продукции , а на вертикальной – план выпуска второй продукции .
Рассмотрим первое ограничение 60×1+28×2 ≤ 1680. Множество точек, удовлетворяющих равенству 60×1+28×2 = 1680, образует прямую на плоскости. Построим эту прямую по её точкам пересечения с осями координат. Для определения координат точки А пересечения с осью в уравнение подставим . Из него следует x1=28, т.е А(28,0). Для определения координат точки В пересечения с осью в уравнение подставим . Из него следует , т.е. . Неравенству 60×1+28×2 ≤ 1680 удовлетворяют все точки одной из полуплоскостей, которые образовала построенная прямая. Для её определения достаточно проверить справедливость неравенства для одной точки. Для начала координат неравенство выполняется. Следовательно, все точки полуплоскости, содержащей начало координат, будут графическим изображением этого неравенства.
Аналогично построим прямую 26×1+60×2 = 1560 по её точкам пересечения с осями координат: С(60,0), D(0, 26). Все точки полуплоскости, содержащей начало координат будут графическим изображением неравенства 26×1+60×2 ≤ 1560.
Учитывая ограничения на знак , множество точек четырёхугольника является множеством всех допустимых решений. Все угловые точки (крайние точки) четырёхугольника соответствуют допустимым базисным решениям:
угловая точка соответствует базисному решению

угловая точка А(28,0) соответствует базисному решению

угловая точка М(19.89; 17.38) соответствует базисному решению

угловая точка D(0, 26) соответствует базисному решению
.
В

С
А
М
D
О

Теперь графически найдём точку четырёхугольника , которая определит оптимальное решение.
Из теорем математического анализа следует, что оптимальное решение следует искать только среди точек границы четырёхугольника . Для её определения в начале координат построим вектор , координаты которого являются рыночными ценами. Прямая 48×1+46×2=0 проходит через начало координат перпендикулярно вектору . Она определяет все планы, в которых выручка равна 0. Вектор указывает направление возрастания выручки. Если прямую нулевой выручки (розовая линия) перемещать параллельно в направлении вектора , то значение выручки будет увеличиваться. Так как среди внутренних точек четырёхугольника оптимального решения не может быть, то прямую нужно переместить до границы четырёхугольника , т.е. до точки .
В

С
А
М
D
О

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

является оптимальным решением.
Максимальная выручка будет равна
Z*=1754,2.

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...