Контрольная работа по «Методы оптимальных решений»

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение
высшего образования

«Челябинский государственный университет»

(ФГБОУ ВО «ЧелГУ»)

ФАКУЛЬТЕТ ЗАОЧНОГО И ДИСТАНЦИОННОГО ОБУЧЕНИЯ

КОНТРОЛЬНАЯ РАБОТА

по дисциплине «Методы оптимальных решений»

вариант 8

Направление 38.03.01 «Экономика»

Челябинск

2017

Содержание

1 Общая постановка транспортной задачи. Открытая и закрытая транспортная задача        3

2 Теория расписаний        6

Задача № 1        9

Задача № 2        12

Список используемой литературы        15

1 Общая постановка транспортной задачи. Открытая и закрытая транспортная задача

Транспортная задача возникает при формализации множества различных прикладных задач. Здесь будет рассмотрена одна из наиболее простых прикладных задач. Пусть в m пунктах (складах) у поставщиков имеется однородный груз в количестве a1, a2,…,am  единиц соответственно. Имеющийся груз необходимо доставить n потребителям, чьи потребности в грузе соответственно равны b1, b2,…,bn. Известны стоимости cij перевозки одной единицы груза от i –го поставщика j –му потребителю. Требуется составить план перевозок, при котором у поставщиков будет вывезен весь груз, а потребителям доставлено ровно столько, сколько нужно. При этом требуется, чтобы суммарная стоимость перевозок была минимальной.

Обозначим xij – количество единиц груза, перевозимого от i –го поставщика j –му потребителю, i =1,…,m, j =1,…,n. Естественно предположить, что xij ≥0 (Груз везут от поставщиков потребителям, а не наоборот).  Обозначим

                        [pic 1]

Матрицу перевозок. Тогда транспортная задача формализуется следующим образом

∑i∑j xijcij →min

x11 +…+ x1n = a1 ,

xm1 +…+ xmn = am ,

x11 +…+ xm1 = b1 ,

x1n +…+ xmn = bn ,

xij ≥0 .

Для того, чтобы транспортная задача имела решение (оптимальный план) необходимо и достаточно выполнения равенства

a1 +…+ am = b1 +…+ bn

Транспортная задача называется закрытой, если выполняется равенство, в противном случае она называется открытой [1, с. 137].

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

a1 +…+ am > b1 +…+ bn         .

Тогда нужно ввести фиктивного n + 1 потребителя с потребностью

bn+1 = a1 +…+ am – (b1 +…+ bn).

...