Контрольная работа

ПЕРВОЕ ВЫСШЕЕ ТЕХНИЧЕСКОЕ УЧЕБНОЕ ЗАВЕДЕНИЕ РОССИИ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

«НАЦИОНАЛЬНЫЙ МИНЕРАЛЬНО-СЫРЬЕВОЙ УНИВЕРСИТЕТ «ГОРНЫЙ»

____________________________________________________________________________

Факультет экономический

Кафедра информационных систем и вычислительной техники

Контрольная работа

По дисциплине: «Современные информационные технологии в учебной и научной деятельности»

Специальность: 230202.65ск – Информационные технологии в образовании

Студент: Зайцев С.Е.

Шифр: 0405031004

Преподаватель: Бригаднов И.А.

Санкт-Петербург

Транспортная задача.

Цель работы: построить план перевозок деталей со всех складов в полном объеме во все магазины, полностью удовлетворив спрос, так, чтобы суммарные транспортные расходы были минимальны.

Условие:

Имеется 5 склада и 5 магазина. Таблица стоимости перевозки детали со склада a_iв магазин b_j:

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

Ограничения:

где x_ij – кол-во деталей, отправляемых со склада iв магазин j, a_i – объем деталей на складе, b_j – спрос магазина.Это значит, что со складов все детали должны быть вывезены и потребность магазинов должна быть удовлетворена.

Целевая функция:

,

где c_ij – стоимость доставки детали со склада iв магазин j.

Потенциал Q(1)=0.

Порядок выполнения работы:

Оптимальный план строится с помощью метода потенциалов. Данный метод является итерационным. Каждая итерация состоит из следующих действий:

Здесь значение целевой функции равно 158.

1. Вычисляются потенциалы Q (для каждой строки)и P (для каждого столбца)по формулам:

Q(i) = C(i,j) – P(j)

P(j) = C(i,j) – Q(i)

(По условию, потенциал Q(1) = 0).

1. Вычисляются невязкидля каждой ячейки по формуле:

G(i,j) = C(i,j) – Q(i) – P(i)

Если в таблице не существует отрицательных невязок – текущий план оптимален (выход из итерационного процесса).

Данный план неоптимален.

1. Если в п.3 текущий план признан неоптимальным, необходимо построить новый. Для этого:
1. Определяются координаты ячейки с наименьшей невязкой (перевозка, вводимая в базис).

1. Из всех перевозок удаляются те, которые не образуют цикл.

1. Перевозки, входящие в цикл, в таблице помечаются знаками "+" и "–" так, чтобы у соседних ячеек таблицы знаки чередовались.

1. Из перевозок со знаком "-" находится перевозка с наименьшим количеством деталей.

1. В клетках со знаком "+" добавляется количество деталей найденной выше перевозки. В клетках со знаком "-" это количество вычитается. Затем для модифицированного плана выполняется новая итерация, т.е. переход на п.1.

В данном задании для нахождения оптимального плана пришлось выполнить 4итераций. Были получены следующие значения целевой функции:

	Номер итерации
Целевая функция

Этот план удовлетворяет ограничениям (суммы по столбцам и строкам не изменились, т.е. со складов все детали вывозятся и потребность магазинов удовлетворяется). При этом целевая функция (суммарные транспортные расходы) минимальна (ее значение равно 130).