Автор работы: Пользователь скрыл имя, 11 Марта 2014 в 22:52, контрольная работа
Задача № 1
Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решить задачу на максимум, и почему?
Условие задачи:
Имеется два вида корма I и II, содержащие питательные вещества (витамины) , и . Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице.
Питательное вещество (витамин) Необходимый минимум питательных веществ Число единиц питательных
Веществ
в 1 кг корма
I II
9 3 1
8 1 2
12 1 6
Стоимость 1 кг корма I и II соответственно равна 4 и 6 ед.
Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание питательных веществ каждого вида было бы не менее установленного предела.
Задача № 2
Для изготовления двух видов продукции используют три вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице 24.
Таблица 24 – Исходные данные к задаче
Тип сырья Нормы расхода сырья на одно изделие, ед. Запасы сырья, ед.
А Б
I 1 2 11
II 2 1 5
III 1 3 14
Прибыль изделия, ден. ед. 4 2 Х
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
1 Условные обозначения, применяемые при моделировании 3
2 Задача № 1 9
3 Задача № 2 12
4 Задача № 3 17
Список используемой литературы 28
x |
x |
x |
4 |
0 |
6 |
x |
x |
x |
0 |
7 |
11 |
5 |
10 |
3200 - 500 = 2700 |
450 |
550 |
500 - 500 = 0 |
1700 |
0 |
Искомый элемент равен 7
Для этого элемента запасы равны 2700, потребности 450. Поскольку минимальным является 450, то вычитаем его.
x31 = min(2700,450) = 450.
x |
x |
x |
4 |
0 |
6 |
x |
x |
x |
0 |
7 |
11 |
5 |
10 |
2700 - 450 = 2250 |
450 - 450 = 0 |
550 |
0 |
1700 |
0 |
Искомый элемент равен 10
Для этого элемента запасы равны 2250, потребности 1700. Поскольку минимальным является 1700, то вычитаем его.
x34 = min(2250,1700) = 1700.
x |
x |
x |
4 |
0 |
6 |
x |
x |
x |
0 |
7 |
11 |
5 |
10 |
2250 - 1700 = 550 |
0 |
550 |
0 |
1700 - 1700 = 0 |
0 |
Искомый элемент равен 11
Для этого элемента запасы равны 550, потребности 550. Поскольку минимальным является 550, то вычитаем его.
x32 = min(550,550) = 550.
x |
x |
x |
4 |
0 |
6 |
x |
x |
x |
0 |
7 |
11 |
5 |
10 |
550 - 550 = 0 |
0 |
550 - 550 = 0 |
0 |
0 |
0 |
1 |
2 |
3 |
4 |
Запасы | |
1 |
15 |
7 |
11 |
4[1000] |
1000 |
2 |
6[550] |
4 |
12 |
8 |
550 |
3 |
7[450] |
11[550] |
5[500] |
10[1700] |
3200 |
Потребности |
1000 |
550 |
500 |
2700 |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых
Значение целевой функции для этого опорного плана равно:
F(x) = 4*1000 + 6*550 + 7*450 + 11*550 + 5*500 + 10*1700 = 36000
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v4 = 4; 0 + v4 = 4; v4 = 4
u3 + v4 = 10; 4 + u3 = 10; u3 = 6
u3 + v1 = 7; 6 + v1 = 7; v1 = 1
u2 + v1 = 6; 1 + u2 = 6; u2 = 5
u3 + v2 = 11; 6 + v2 = 11; v2 = 5
u3 + v3 = 5; 6 + v3 = 5; v3 = -1
v1=1 |
v2=5 |
v3=-1 |
v4=4 | |
u1=0 |
15 |
7 |
11 |
4[1000] |
u2=5 |
6[550] |
4 |
12 |
8 |
u3=6 |
7[450] |
11[550] |
5[500] |
10[1700] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
(2;2): 5 + 5 > 4; ∆22 = 5 + 5 - 4 = 6
(2;4): 5 + 4 > 8; ∆24 = 5 + 4 - 8 = 1
max(6,1) = 6
Выбираем максимальную оценку свободной клетки (2;2): 4
Для этого в перспективную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
4 |
Запасы | |
1 |
15 |
7 |
11 |
4[1000] |
1000 |
2 |
6[550][-] |
4[+] |
12 |
8 |
550 |
3 |
7[450][+] |
11[550][-] |
5[500] |
10[1700] |
3200 |
Потребности |
1000 |
550 |
500 |
2700 |
Цикл приведен в таблице (2,2; 2,1; 3,1; 3,2; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 550. Прибавляем 550 к объемам грузов, стоящих в плюсовых клетках и вычитаем 550 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
Запасы | |
1 |
15 |
7 |
11 |
4[1000] |
1000 |
2 |
6 |
4[550] |
12 |
8 |
550 |
3 |
7[1000] |
11[0] |
5[500] |
10[1700] |
3200 |
Потребности |
1000 |
550 |
500 |
2700 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v4 = 4; 0 + v4 = 4; v4 = 4
u3 + v4 = 10; 4 + u3 = 10; u3 = 6
u3 + v1 = 7; 6 + v1 = 7; v1 = 1
u3 + v2 = 11; 6 + v2 = 11; v2 = 5
u2 + v2 = 4; 5 + u2 = 4; u2 = -1
u3 + v3 = 5; 6 + v3 = 5; v3 = -1
v1=1 |
v2=5 |
v3=-1 |
v4=4 | |
u1=0 |
15 |
7 |
11 |
4[1000] |
u2=-1 |
6 |
4[550] |
12 |
8 |
u3=6 |
7[1000] |
11[0] |
5[500] |
10[1700] |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.
Минимальные затраты составят:
F(x) = 4*1000 + 4*550 + 7*1000 + 5*500 + 10*1700 = 32700
Анализ оптимального плана.
Из 1-го склада необходимо весь груз направить в 4-й магазин
Из 2-го склада необходимо весь груз направить в 2-й магазин
Из 3-го склада необходимо груз направить в 1-й магазин (1000), в 3-й магазин (500), в 4-й магазин (1700)
Список используемой литературы
Информация о работе Контрольная работа по предмету "Экономико-математическое моделирование"