Моделирование однокритериальных задач принятия решений в условиях определенности

Томский межвузовский центр дистанционного образования

Томский государственный университет 

систем управления и радиоэлектроники (ТУСУР)

 

 

 

 

 

 

 

Контрольная работа

 

по дисциплине «Разработка управленческих решений»

по теме «Моделирование однокритериальных задач принятия решений в условиях определенности»

 

 

 

 

 

 

 

Выполнила:

студентка ТМЦДО

гр.: з-478-б

специальности 080504

 

Леушина Екатерина Викторовна

7 сентября 2013 г.

 

 

 

 

 

 

 

 

 

 

 

                                                      г. Тюмень 2013г.

 

 

Контрольная работа №1

Моделирование однокритериальных задач принятия решений в условиях определенности.

 

Задание 1.

По содержательной постановке задачи необходимо построить математическую оптимизационную модель и графическим способом найти её решение.

 

   Вариант №8

Для приготовления комбикорма совхоз может закупить зерно 2-х сортов, отличающихся друг от друга содержанием питательных компонентов. Для обеспечения нормального питания скота в течение планируемого периода комбикорм должен содержать не менее bj единиц питательного компонента j -го типа (j=1,n). Одна тонна зерна i-ro сорта стоит Ri рублей и содержит aij единиц питательного компонента j-го типа. Складские помещения позволяют хранить не более А тонн зерна. Определить, какое минимальное количество средств должен вложить совхоз в закупку зерна, чтобы обеспечить заданную питательность комбикорма с учетом емкости складских помещений.

Сколько   зерна   каждого   сорта   необходимо   закупить,   если А=7000 тонн?

Таблица 3.3 - Исходные данные для вариантов 6-10

 

b1	b2	a11	a12	a21	a22	R1	R2
50	100	0,02	0,01	0,04	0,03	30	30

 

Решение

Составляем задачу ЗЛП

                                                  (1)

                                                    (2)

                                      (3)

                         (4)                                                                                                                         (5)

Ограничения (2) – (4) представляют выпуклое множество допустимых решений  (МДР),  вектор-градиент, составленный из  коэффициентов  целевой функции, указывает направление минимизации  Z(X). Начало вектора – точка (0; 0), конец – точка (30; 30).

 

 

 

 

Полученное решение запишем:

min: х₁ = 1250;  х₂ = 2500; Z(X) = 112500.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание 2.

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

Варианты задания 2 для выполнения контрольной работы №1

Трем деревообрабатывающим фабрикам поставляется лесоматериал из двух различных регионов. Возможности поставщиков равны а₁ и а₂ (куб.м), потребности фабрик соответственно равны b₁, b₂, b₃ (куб.м) и представлены в табл. 3.4. Известны затраты на перевозку одного кубометра леса от поставщиков к потребителям (задаются в виде матрицы затрат в рублях с элементами сij, i=l,2; j=l,2,3 - в табл. 3.5.). Найти оптимальный план перевозок лесоматериала.

Таблица 3.4 - Данные для поставщиков и потребителей

 

a1	a2	b1	b2	b3
8	12	10	2	8

 

Таблица 3.5 –  Матрица затрат на перевозку лесоматериала

 

с11	с12	с13	с21	с22	с23
40	50	20	30	30	20

 

Решение:

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

F = ∑∑c_ijx_ij,    (1)

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

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

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

С целью составления двойственной задачи переменные x_ij в условии (2) заменим на u₁, u₂, u_i,.., u_m, а переменные x_ij в условия (3) на v₁, v₂, v_j,.., v_n.

Поскольку каждая переменная x_ij входит в условия (2,3) и целевую функцию (1) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.

Требуется найти не отрицательные  числа u_i (при i  = 1,2,…,m) и v_j (при j = 1,2,..,n), обращающие в максимум целевую функцию

G = ∑a_iu_i + ∑b_jv_j

при условии

u_i + v_j ≤ c_ij, i = 1,2,..,m; j = 1,2,..,n    (4)

В систему условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть:

u_i + v_j ≤ c_ij, если x_ij = 0,

u_i + v_j = c_ij, если x_ij ≥ 0,

Числа u_i , v_j называются потенциалами. Причем число u_i называется потенциалом поставщика, а число v_j – потенциалом потребителя.

По первой теореме  двойственности в оптимальном решении  значения целевых функций прямой и двойственных задач совпадают: F = G.

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

	1	2	3	Запасы
1	40	50	20	8
2	30	30	20	12
Потребности	10	2	8

 

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

∑a = 8 + 12 = 20

∑b = 10 + 2 + 8 = 20

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

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

	1	2	3	Запасы
1	40	50	20	8
2	30	30	20	12
Потребности	10	2	8

 

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

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

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

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

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

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

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

x₁₃ = min(8,8) = 8.

x	x	20	8 - 8 = 0
30	30	x	12
10	2	8 - 8 = 0	0

 

 

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

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

x₂₁ = min(12,10) = 10.

x	x	20	0
30	30	x	12 - 10 = 2
10 - 10 = 0	2	0	0

 

 

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

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

x₂₂ = min(2,2) = 2.

x	x	20	0
30	30	x	2 - 2 = 0
0	2 - 2 = 0	0	0

 

 

	1	2	3	Запасы
1	40	50	20[8]	8
2	30[10]	30[2]	20	12
Потребности	10	2	8

 

2. Подсчитаем число  занятых клеток таблицы, их 3, а должно быть m + n - 1 = 4. Следовательно, опорный план является вырожденным.

Строим новый план.

Значение целевой функции  для этого опорного плана равно:

F(x) = 20*8 + 30*10 + 30*2  = 520

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

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

x₂₃ = min(12,8) = 8.

40	50	x	8
30	30	20	12 - 8 = 4
10	2	8 - 8 = 0	0

 

 

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

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

x₂₁ = min(4,10) = 4.

40	50	x	8
30	x	20	4 - 4 = 0
10 - 4 = 6	2	0	0

 

 

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

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

x₁₁ = min(8,6) = 6.

40	50	x	8 - 6 = 2
30	x	20	0
6 - 6 = 0	2	0	0

 

 

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

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

x₁₂ = min(2,2) = 2.

40	50	x	2 - 2 = 0
30	x	20	0
0	2 - 2 = 0	0	0

 

 

	1	2	3	Запасы
1	40[6]	50[2]	20	8
2	30[4]	30	20[8]	12
Потребности	10	2	8