Автор работы: Пользователь скрыл имя, 12 Января 2015 в 15:44, контрольная работа
1. Задачу решите графическим методом.
2. Задание 2
Задачу решите симплексным методом.
Задание 3
Составьте оптимальный план перевозки грузов от поставщиков с грузами 160, 60, 180 т к потребителям с запросами 80, 60, 60 и 200 т. Стоимости перевозок единицы груза от каждого поставщика к каждому потребителю даны матрицей
Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (- , 9 : 1/2 , 12 : 2 ) = 6
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
min |
x2 |
8 |
0 |
1 |
0 |
1 |
2 |
0 |
- |
x3 |
9 |
1/2 |
0 |
1 |
1 |
21/2 |
0 |
18 |
x6 |
12 |
2 |
0 |
0 |
0 |
1 |
1 |
6 |
F(X3) |
-32 |
2 |
0 |
0 |
-3 |
-10 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x6 в план 3 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 3, получена в результате деления всех элементов строки x6 плана 2 на разрешающий элемент РЭ=2
На месте разрешающего элемента в плане 3 получаем 1.
В остальных клетках столбца x1 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.
Получаем новую симплекс-таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x2 |
8 |
0 |
1 |
0 |
1 |
2 |
0 |
x3 |
6 |
0 |
0 |
1 |
1 |
9/4 |
-1/4 |
x1 |
6 |
1 |
0 |
0 |
0 |
1/2 |
1/2 |
F(X3) |
-44 |
0 |
0 |
0 |
-3 |
-11 |
-1 |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Оптимальный план можно записать так:
x2 = 8 x3 = 6 x1 = 6 F(X) = 5•8 -8•6 -6•6 = -44
Задание 3
Составьте оптимальный план перевозки грузов от поставщиков с грузами 160, 60, 180 т к потребителям с запросами 80, 60, 60 и 200 т. Стоимости перевозок единицы груза от каждого поставщика к каждому потребителю даны матрицей
Решение
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 160 + 60 + 180 = 400
∑b = 80 + 60 + 60 + 200 = 400
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.
1 |
2 |
3 |
4 |
Запасы | |
1 |
8 |
6 |
9 |
2 |
160 |
2 |
7 |
16 |
12 |
12 |
60 |
3 |
6 |
15 |
8 |
3 |
180 |
Потребности |
80 |
60 |
60 |
200 |
Этап I. Поиск первого опорного плана.
1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
План начинается заполняться с верхнего левого угла.
Искомый элемент равен 8
Для этого элемента запасы равны 160, потребности 80. Поскольку минимальным является 80, то вычитаем его.
x11 = min(160,80) = 80.
8 |
6 |
9 |
2 |
160 - 80 = 80 |
x |
16 |
12 |
12 |
60 |
x |
15 |
8 |
3 |
180 |
80 - 80 = 0 |
60 |
60 |
200 |
0 |
Искомый элемент равен 6
Для этого элемента запасы равны 80, потребности 60. Поскольку минимальным является 60, то вычитаем его.
x12 = min(80,60) = 60.
8 |
6 |
9 |
2 |
80 - 60 = 20 |
x |
x |
12 |
12 |
60 |
x |
x |
8 |
3 |
180 |
0 |
60 - 60 = 0 |
60 |
200 |
0 |
Искомый элемент равен 9
Для этого элемента запасы равны 20, потребности 60. Поскольку минимальным является 20, то вычитаем его.
x13 = min(20,60) = 20.
8 |
6 |
9 |
x |
20 - 20 = 0 |
x |
x |
12 |
12 |
60 |
x |
x |
8 |
3 |
180 |
0 |
0 |
60 - 20 = 40 |
200 |
0 |
Искомый элемент равен 12
Для этого элемента запасы равны 60, потребности 40. Поскольку минимальным является 40, то вычитаем его.
x23 = min(60,40) = 40.
8 |
6 |
9 |
x |
0 |
x |
x |
12 |
12 |
60 - 40 = 20 |
x |
x |
x |
3 |
180 |
0 |
0 |
40 - 40 = 0 |
200 |
0 |
Искомый элемент равен 12
Для этого элемента запасы равны 20, потребности 200. Поскольку минимальным является 20, то вычитаем его.
x24 = min(20,200) = 20.
8 |
6 |
9 |
x |
0 |
x |
x |
12 |
12 |
20 - 20 = 0 |
x |
x |
x |
3 |
180 |
0 |
0 |
0 |
200 - 20 = 180 |
0 |
Искомый элемент равен 3
Для этого элемента запасы равны 180, потребности 180. Поскольку минимальным является 180, то вычитаем его.
x34 = min(180,180) = 180.
8 |
6 |
9 |
x |
0 |
x |
x |
12 |
12 |
0 |
x |
x |
x |
3 |
180 - 180 = 0 |
0 |
0 |
0 |
180 - 180 = 0 |
0 |
1 |
2 |
3 |
4 |
Запасы | |
1 |
8[80] |
6[60] |
9[20] |
2 |
160 |
2 |
7 |
16 |
12[40] |
12[20] |
60 |
3 |
6 |
15 |
8 |
3[180] |
180 |
Потребности |
80 |
60 |
60 |
200 |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых
Значение целевой функции для этого опорного плана равно:
F(x) = 8*80 + 6*60 + 9*20 + 12*40 + 12*20 + 3*180 = 2440
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 8; 0 + v1 = 8; v1 = 8
u1 + v2 = 6; 0 + v2 = 6; v2 = 6
u1 + v3 = 9; 0 + v3 = 9; v3 = 9
u2 + v3 = 12; 9 + u2 = 12; u2 = 3
u2 + v4 = 12; 3 + v4 = 12; v4 = 9
u3 + v4 = 3; 9 + u3 = 3; u3 = -6
v1=8 |
v2=6 |
v3=9 |
v4=9 | |
u1=0 |
8[80] |
6[60] |
9[20] |
2 |
u2=3 |
7 |
16 |
12[40] |
12[20] |
u3=-6 |
6 |
15 |
8 |
3[180] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;4): 0 + 9 > 2; ∆14 = 0 + 9 - 2 = 7
(2;1): 3 + 8 > 7; ∆21 = 3 + 8 - 7 = 4
max(7,4) = 7
Выбираем максимальную оценку свободной клетки (1;4): 2
Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
4 |
Запасы | |
1 |
8[80] |
6[60] |
9[20][-] |
2[+] |
160 |
2 |
7 |
16 |
12[40][+] |
12[20][-] |
60 |
3 |
6 |
15 |
8 |
3[180] |
180 |
Потребности |
80 |
60 |
60 |
200 |
Информация о работе Контрольная работа по дисциплине «Методы оптимальных решений»