Контрольная работа по "Математике"

 

Оптимальный план можно  записать так:

x₄ = 270

x₅ = 280

x₂ = 30

F(X) = 4•30 = 120

Ответ: Оптимальный план: 
x₄ = 270 
x₅ = 280 
x₂ = 30 
F(X) = 4•30 = 120

Задача № 51

Используя вариант предыдущего  контрольного задания, необходимо:

• к прямой задаче планирования товарооборота, решаемой  

     симплексным методом,  составить двойственную задачу  линейного 

     программирования;

• установить сопряженные пары переменных прямой

       и   двойственной  задач;

• согласно сопряженным парам переменных из решения прямой 

            задачи получить решение двойственной задачи, в которой

            производится оценка ресурсов, затраченных  на продажу товаров.

Решение

Составим двойственную задачу к прямой задаче.

Левая часть ограничений определяет стоимость ресурсов в теневых (альтернативных) ценах, затраченных на x_j.

18y₁ + 4y₂ + 3y₃≥3

9y₁ + 2y₂ + 4y₃≥4

6y₁ + 4y₂ + 3y₃≥3

540y₁ + 340y₂ + 120y₃ → min

y₁ ≥ 0

y₂ ≥ 0

y₃ ≥ 0

Решение двойственной задачи дает оптимальную  систему оценок ресурсов.

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.

Из теоремы двойственности следует, что Y = C*A^-1.

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

 

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

 

Как видно из последнего плана симплексной  таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных .

Тогда Y = C*A^-1 =

 

Оптимальный план двойственной задачи равен:

y₁ = 0

y₂ = 0

y₃ = 1

Z(Y) = 540*0+340*0+120*1 = 120

Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.

Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.

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

18 0 + 9 30 + 6 0  = 270 < 540

4 0 + 2 30 + 4 0  = 60 < 340

3 0 + 4 30 + 3 0  = 120 = 120

1-ое ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₁ = 0.

Неиспользованный экономический  резерв ресурса 1 составляет 270 (540-270).

Этот резерв не может  быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).

2-ое ограничение выполняется  как строгое неравенство, т.е.  ресурс 2-го вида израсходован  не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₂ = 0.

Неиспользованный экономический  резерв ресурса 2 составляет 280 (340-60).

Этот резерв не может  быть использован в оптимальном  плане, но указывает на возможность  изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).

3-е ограничение прямой задачи выполняется как равенство. Это означает, что 3-ий ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₃>0).

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

Обоснование эффективности оптимального плана.

При подстановке оптимальных  двойственных оценок в систему ограничений  двойственной задачи получим:

18 0 + 4 0 + 3 1  = 3 = 3

9 0 + 2 0 + 4 1  = 4 = 4

6 0 + 4 0 + 3 1  = 3 = 3

1-ое ограничение двойственной  задачи выполняется как равенство. Это означает, что 1-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₁>0).

2-ое ограничение двойственной  задачи выполняется как равенство.  Это означает, что 2-ой ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₂>0).

3-е ограничение двойственной задачи выполняется как равенство. Это означает, что 3-ий ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₃>0).

Влияние запасов  ресурсов на оптимальное решение  прямой задачи.

Величина двойственной оценки показывает, на сколько возрастает значение целевой функции F(x) при  увеличении дефицитного ресурса  на единицу.

Анализ устойчивости оптимального плана.

Проведем анализ устойчивости оптимального плана и оценим степень  влияния изменения ресурсов на значение целевой функции.

Чувствительность  решения к изменению коэффициентов  целевой функции.

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

Пусть каждое значение параметра целевой  функции изменится на ∆ с_i. Найдем интервалы, при которых будет экономически выгодно использование ресурсов.

Допустимые диапазоны изменения  коэффициентов в целевой функции  определятся из соотношений:

2-ой параметр целевой функции может изменяться в пределах:

∆c₂^- = min [y_k/d_2k] для d_2k>0.

∆c₂⁺ = |max [y_k/d_2k]| для d_2k<0.

 

 

Таким образом, 2-параметр может быть уменьшен на 4 или увеличен на 0

Интервал изменения равен:

(c₂ - ∆c₂^-; c₂ + ∆c₂⁺)

[4-4; 4+0] = [0;4]

Если значение c₂ будет лежать в данном интервале, то оптимальный план не изменится.

Чувствительность решения  к изменению запасов сырья.

Из теоремы об оценках  известно, что колебание величины b_i приводит к увеличению или уменьшению f(X).

Оно определяется величиной y_i в случае, когда при изменении величин b_i значения переменных у_i в оптимальном плане соответствующей двойственной задачи остаются неизменными.

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

Найдем интервалы  устойчивости ресурсов.

3-ий запас может изменяться в пределах:

∆b₃^- = min [x_k/d_k3] для d_k3>0.

∆b₃⁺ = |max [x_k/d_k3]| для d_k3<0.

 

 

Таким образом, 3-ый запас  может быть уменьшен на 120 или увеличен на 120

Интервал изменения  равен:

(b₃ - ∆b₃^-; b₃ + ∆b₃⁺)

[120-120; 120+120] = [0;240]

В оптимальный план не вошла основная переменная x₁, т.е. ее не выгодно использовать. Определим максимально возможное значение в рамках полученных двойственных оценок:

1-ый запас может  изменяться в пределах:

 

0 ≤ ∆b₁ ≤ 24

[540-24; 540] = [516;540]

В оптимальный план не вошла основная переменная x₂, т.е. ее не выгодно использовать. Определим максимально возможное значение в рамках полученных двойственных оценок:

2-ой запас может изменяться в пределах:

 

0 ≤ ∆b₂ ≤ 30

[340-30; 340] = [310;340]

Ответ: Оптимальный план двойственной задачи равен:

y₁ = 0

y₂ = 0

y₃ = 1

Z(Y) = 120

Задача № 76

Поставщики товара - оптовые  коммерческие предприятия  А_1, А₂,...,А_m имеют запасы товаров соответственно в количестве а₁, а₂,..., а_m ед. и розничные торговые предприятия В₁, В₂,...,В_n.   - подали заявки на закупку товаров в объемах соответственно: b₁, b₂, b₃,...,b_n. Тарифы  перевозок единицы груза с каждого из пунктов поставки в соответствующие пункты потребления заданы в виде матрицы С=(с_ij)(i= )

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

76.  а₁=222,         b₁=125,

       а₂=188,         b₂=75,

       а₃=210,         b₃=200,

       а₄=380,         b₄=380,

                             b₅=220.

Решение

Математическая модель транспортной задачи:

F = ∑∑c_ijx_ij,    (1)

при условиях:

∑x_ij = a_i,  i = 1,2,…, m,   (2)

∑x_ij = b_j,  j = 1,2,…, n,   (3)

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

	1	2	3	4	5	Запасы
1	23	21	11	8	3	222
2	7	17	5	2	4	188
3	2	16	8	4	3	210
4	3	9	21	8	4	380
Потребности	125	75	200	380	220

Проверим необходимое  и достаточное условие разрешимости задачи.

∑a = 222 + 188 + 210 + 380 = 1000

∑b = 125 + 75 + 200 + 380 + 220 = 1000

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

 

	1	2	3	4	5	Запасы
1	23	21	11	8	3	222
2	7	17	5	2	4	188
3	2	16	8	4	3	210
4	3	9	21	8	4	380
Потребности	125	75	200	380	220

 

Этап I. Поиск  первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

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

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

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

Искомый элемент равен 2

Для этого элемента запасы равны 188, потребности 380. Поскольку минимальным является 188, то вычитаем его.

x₂₄ = min(188,380) = 188.

23	21	11	8	3	222
x	x	x	2	x	188 - 188 = 0
2	16	8	4	3	210
3	9	21	8	4	380
125	75	200	380 - 188 = 192	220	0

Искомый элемент равен 2

Для этого элемента запасы равны 210, потребности 125. Поскольку минимальным является 125, то вычитаем его.

x₃₁ = min(210,125) = 125.

x	21	11	8	3	222
x	x	x	2	x	0
2	16	8	4	3	210 - 125 = 85
x	9	21	8	4	380
125 - 125 = 0	75	200	192	220	0