ТПР Нарыков
.docМИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение
Юго-Западный государственный университет
Факультет обучения в сокращенные сроки
Контрольная работа
по дисциплине: «Базы данных»
специальность: 230101 «Вычислительные машины, комплексы, системы и сети»
Выполнил: Нарыков А.С.
Группа: ВМ-02Ф
Проверила: Емельянова Е.Ю
Курск – 2012г
Задание 1
По словесному описанию предметной области составить задачу линейного программирования (записать целевую функцию и систему ограничительных уравнений/неравенств) и решить ее. Если задача имеет 2 свободных переменных, решать можно графическим методом, если 3 и больше – симплекс-методом.
1. Фабрика Wild West производит два типа ковбойских шляп. Производство
шляпы первого типа требует в два раза больше временных ресурсов, чем из-
готовление шляпы второго типа. Если фабрика будет производить только
шляпы второго типа, то в день она сможет изготовить 400 таких шляп.
Рынок налагает ограничения на производство шляп: не более 150 шляп пер-
вого и 200 шляп второго типа. Доход от производства шляп составляет
8 долл. на единицу первого типа и 5 долл. — второго типа.
c) Используя стоимость единицы ресурса, определите, на сколько изменится
максимальный доход фабрики, если ежедневное производство шляп пер-
вого типа не будет превышать 120 единиц.
Решение
с) Введем в условие
дополнительное ограничение
.
,
Решение не изменится, так как прямая x = 120 не влияет на крайнее положение сдвигаемой прямой на графике:
Ответ: 100 шляп первого вида и 200 второго.
Задание 2
Решение
Изобразим область ограничений.
Проводим прямую f = 0, затем сдвигаем ее как можно больше вправо-вниз (вправо – увеличение x1, так как в выражение для f эта переменная входит с положительным знаком, а вниз – уменьшение x2, так как коэффициент при x2 отрицательный).
В крайнем положении эта сдвинутая прямая пересекает область ограничений в точке x1 = 4, x2 = 0. Это и будет оптимальное решение. Максимальное значение f в этом случае будет 4∙4 – 4∙0 = 16.
Ответ: 16 при х1 = 4, х2 = 0.
Задание 3
Транспортная задача. Составить допустимый план перевозок методом северо-западного угла, минимального элемента и Фогеля. Решить транспортную задачу методом потенциалов, используя в качестве опорного любой план.
Решение
Исходные данные задачи можно записать в виде таблице (пока без поставок):
|
|
Потребители |
||||||||
|
20 |
30 |
30 |
10 |
||||||
|
Поставщики |
30 |
2 |
|
3 |
|
2 |
|
4 |
|
|
|
|
|
|
|
|
|
|
||
|
40 |
3 |
|
2 |
|
5 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
||
|
20 |
4 |
|
3 |
|
2 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
||
Заполним начальный план методом северо-западного угла. При этом заполнение будем производить начиная с левой верхней ячейки, двигаясь от одной клетки к соседней вниз или вправо, в зависимости от того, где поставка произведена не полностью, пока не достигнем конца.
|
|
Потребители |
||||||||
|
20 |
30 |
30 |
10 |
||||||
|
Поставщики |
30 |
2 |
|
3 |
|
2 |
|
4 |
|
|
|
20 |
|
10 |
|
|
|
|
||
|
40 |
3 |
|
2 |
|
5 |
|
1 |
|
|
|
|
|
|
20 |
|
20 |
|
|
||
|
20 |
4 |
|
3 |
|
2 |
|
6 |
|
|
|
|
|
|
|
|
10 |
|
10 |
||
Общие затраты при таком распределении составят
.
Метод минимального элемента состоит в том, чтобы заполнять поставками до максимально возможного значения ячейку с наименьшим тарифом, потом – следующую возможную и т.д.
|
|
Потребители |
||||||||
|
20 |
30 |
30 |
10 |
||||||
|
Поставщики |
30 |
2 |
|
3 |
|
2 |
|
4 |
|
|
|
20 |
|
|
|
10 |
|
|
||
|
40 |
3 |
|
2 |
|
5 |
|
1 |
|
|
|
|
|
|
30 |
|
|
|
10 |
||
|
20 |
4 |
|
3 |
|
2 |
|
6 |
|
|
|
|
|
|
|
|
20 |
|
|
||
Общие затраты при таком распределении составят
.
Метод Фогеля состоит в последовательном вычислении штрафов – разности между двумя наименьшими тарифами – по каждой строке и каждому столбцу. Затем заполняется ячейка с минимальным тарифом, в строке или столбце которой находится максимальный штраф.
|
|
Потребители |
штраф |
||||||||
|
20 |
30 |
30 |
10 |
|||||||
|
Поставщики |
30 |
2 |
|
3 |
|
2 |
|
4 |
|
1 |
|
|
|
|
|
|
|
|
|
|
||
|
40 |
3 |
|
2 |
|
5 |
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
10 |
|
||
|
20 |
4 |
|
3 |
|
2 |
|
6 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
||
|
штраф |
1 |
|
1 |
|
0 |
|
3 |
|
|
|
Вычеркиваем четвертого потребителя – он полностью заполнен – и в перераспределенной таблице снова ищем начальный план и так далее.
|
|
Потребители |
штраф |
||||||
|
20 |
30 |
30 |
||||||
|
Поставщики |
30 |
2 |
|
3 |
|
2 |
|
1 |
|
|
20 |
|
|
|
|
|
||
|
30 |
3 |
|
2 |
|
5 |
|
1 |
|
|
|
|
|
|
|
|
|
||
|
20 |
4 |
|
3 |
|
2 |
|
1 |
|
|
|
|
|
|
|
|
|
||
|
штраф |
1 |
|
1 |
|
0 |
|
|
|
|
|
Потребители |
штраф |
||||
|
30 |
30 |
|||||
|
Поставщики |
10 |
3 |
|
2 |
|
1 |
|
|
|
|
10 |
|
||
|
30 |
2 |
|
5 |
|
3 |
|
|
|
30 |
|
|
|
||
|
20 |
3 |
|
2 |
|
1 |
|
|
|
|
|
20 |
|
||
|
штраф |
1 |
|
0 |
|
|
|
То есть начальный план, полученный методом Фогеля, будет
|
|
Потребители |
||||||||
|
20 |
30 |
30 |
10 |
||||||
|
Поставщики |
30 |
2 |
|
3 |
|
2 |
|
4 |
|
|
|
20 |
|
|
|
10 |
|
|
||
|
40 |
3 |
|
2 |
|
5 |
|
1 |
|
|
|
|
|
|
30 |
|
|
|
10 |
||
|
20 |
4 |
|
3 |
|
2 |
|
6 |
|
|
|
|
|
|
|
|
20 |
|
|
||
Это распределение совпадает с полученным методом минимального элемента.
Решим задачу, используя метод потенциалов, начав с опорного плана, полученного методом северо-западного угла.
Произведем начальную оценку оптимальности плана.
|
2 |
|
3 |
|
2 |
|
4 |
|
0 |
|
|
20 |
|
10 |
|
|
|
|
|
|
3 |
|
2 |
|
5 |
|
1 |
|
1 |
|
|
|
|
20 |
|
20 |
|
|
|
|
4 |
|
3 |
|
2 |
|
6 |
|
4 |
|
|
|
|
|
|
10 |
|
10 |
|
|
-2 |
|
-3 |
|
-6 |
|
-10 |
|
|
|
0 |
|
0 |
|
-4 |
|
-6 |
|
0 |
|
|
20 |
|
10 |
|
|
|
|
|
|
4 |
|
0 |
|
0 |
|
-8 |
|
1 |
|
|
|
|
20 |
|
20 |
|
|
|
|
6 |
|
4 |
|
0 |
|
0 |
|
4 |
|
|
|
|
|
|
10 |
|
10 |
|
|
-2 |
|
-3 |
|
-6 |
|
-10 |
|
|
Есть отрицательные значения, поэтому план не оптимальный. Заполняем поставкой ячейку с минимальным значением.
|
0 |
|
0 |
|
-4 |
|
-6 |
|
0 |
|
|
20 |
|
10 |
|
|
|
|
|
|
4 |
|
0 |
|
0 |
|
-8 |
|
1 |
|
|
|
|
20 |
-10 |
20 |
+10 |
|
|
|
6 |
|
4 |
|
0 |
|
0 |
|
4 |
|
|
|
|
|
+10 |
10 |
-10 |
10 |
|
|
-2 |
|
-3 |
|
-6 |
|
-10 |
|
|