Оглавление
Введение 2
ЗАДАЧА 1 3
ЗАДАЧА 3 7
ЗАДАЧА 4 14
Список литературы 18
Введение
По этой работе незачет
Рецензия от преподавателя
В задаче 1 не составлена экономико-математическая модель задачи. Не указан метод решения задачи.
Задача 3 должна быть решена методом "ветвей и границ".
В задаче 4 неверно выполнена корректировка сетевого графика. число исполнителей по каждой работе на всем протяжении ее выполнения должно быть одинаковым - это условие у Вас не выполняется.
ЗАДАЧА 1
На территории города имеется три телефонных станции А, Б и В. Незадействованные емкости станций составляют на станции А - QА, Б - QБ, В - QВ номеров (таблица 1.1). Потребности новых районов застройки города в телефонах составляют: 1 - q1, 2 - q2, 3 - q3, 4 - q4 номеров (таблица 1.2).
Необходимо составить экономико-математическую модель задачи и с помощью распределительного или модифицированного метода линейного программирования найти вариант распределения емкостей телефонных станций между районами новой застройки, который обеспечивал бы минимальные затраты как на строительство, так и на эксплуатацию линейных сооружений телефонной сети. Естественно, что таким вариантом при прочих равных условиях будет такое распределение емкости, при котором общая протяженность абонентских линий будет минимальной.
Вариант 6
Q1
Q2
Q3
Q4
Незадействованные емкости станций
QА
4
5
6
4
500
QБ
3
2
1
4
1100
QВ
6
7
5
2
900
Потребности новых районов застройки
400
500
900
700
Предложение равно спросу 2500
Решение
Потребности новых районов застройки города 400 +500+900+700= 2500, в то время как емкости станций составляют 500+1100+900= 2500
Следовательно, это задача замкнутая.
Рассмотрим закрытую транспортную задачу. Ее условия запишем в распределительную таблицу, которую будем использовать для нахождения решения.
Транспортная задача как задача линейного программирования может быть решена симплексным методом, однако наличие большого числа переменных и ограничений делает вычисления громоздкими. Поэтому для решения этого класса задач разработан специальный метод, имеющий те же этапы, что и симплексный метод, а именно:
* нахождение исходного опорного решения;
* проверка этого решения на оптимальность;
* переход от одного опорного решения к другому.
Рассмотрим один из них - метод минимального тарифа (элемента). Согласно этому методу, емкости распределяются в первую очередь в те клетки, в которых находится минимальное расстояние. Далее загрузка распределяются в незанятые клетки с наименьшими расстояниями с учетом оставшихся емкостей на станциях и удовлетворения спроса потребителей. Процесс распределения продолжают до тех пор, пока все емкости не будут заняты, а потребители не будут удовлетворены.
Таблица исходной транспортной задачи имеет следующий вид.
bij
1
2
3
4
aij
400
500
900
700
1
500
4
5
6
4
400
100
2
1100
3
2
1
4
200
900
3
900
6
7
5
2
300
600
Число занятых клеток в таблице равно 6, 4+3-1=6, т. е. условие невырожденности выполнено. Получим исходное опорное решение, которое запишем в виде матрицы:
общая протяженность при исходном опорном решении составляет L(Xопт) = 400 • 4 + 100 • 4 + 200 • 2 + 900 • 1 + 300 • 7+ 600 • 2 = 6600 усл. ед.
Проверка решения на оптимальность
Найденное исходное опорное решение проверяется на оптимальность методом потенциалов.
Числа vj и ui называют потенциалами. В распределительную таблицу добавляют строку v и столбец u. Потенциалы находят из равенства ui + vj = cij, справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например, u1 = 0, тогда остальные потенциалы определяются однозначно.
bij
1
2
3
4
ui
aij
400
500
900
700
1
500
4
5
6
4
0
400
100
2
1100
3
2
1
4
-7
200
900
3
900
6
7
5
2
-2
300
600
vj
4
9
8
4
Полагаем u1 = 0, запишем это значение в последнем столбце первой строки таблицы. Рассмотрим занятую клетку первой строки, которая расположена в первом столбце (1, 1), для нее выполняется условие u1 + v1 =4. Отсюда при u1 = 0 получаем, что v1 = 4, это значение запишем в последней строке таблицы. Далее надо рассматривать ту из занятых клеток таблицы, для которых один из потенциалов известен.
Рассмотрим занятую клетку (1, 4):
u1 + v4 =4; u1=0; v4 =4
Рассмотрим занятую клетку (3, 4):
u3 + v4 =2; u3=-2; v4 =4
Рассмотрим занятую клетку (3, 2):