Методические указания и контрольные задания для студентов экономических специальностей бнту

5 6 4 9 0 Исследование этого плана на оптимальность аналогично предыдущему. Вычисленные значения потенциалов записаны справа и снизу таблицы, а оцен­ки sij свободных клеток поместим в левых нижних углах этих клеток. Посколь­ку среди оценок нет отрицательных, то найденный план является оптимальным. Выписываем матрицу Х* (без последнего столбца): Минимальные суммарные затраты по оптимальному плану составляют: Zmin = 203+102+253+156+154+159 = 430 ден. ед. Из таблицы 2 видно, что избыточная продукция в количестве 10 тыс. изд. остается на третьей фабрике. ^ КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ Задание 5. Определить оптимальный план перевозок с целью минимизации общих затрат на транспортировку с заданными векторами и и матрицей стоимостей С. Варианты С 1 2 3 4 5 6 7 8 9 10 ^ VI. Задача о максимальном потоке в сети Рассмотрим сеть G(V, U), где V множество вершин, а U множество дуг их соединяющих, (i, j)  U поставлено в соответствие неотрицательное число dij (dij  0), называемое пропускной способностью этой дуги (если дуга (i, j) – неориентированная, то полагаем dij = dji). Выделим в сети две вершины. Одну из них назовем источником и обозначим s, а другую – стоком и обозначим t . Каждой дуге (i, j) сети поставим в соответствие неотрицательное число xij , которое назовем потоком на дуге (i, j). Потоком из источника s в сток t в сети G (V,U) называется множество неотрицательных чисел , удовлетво­ряющих ограничениям: , (19) , (20) (21) (22) Неотрицательная величина v называется величиной потока в сети. Огра­ничения (1), (2) означают, что суммарная величина v потока, выходящего из источника s, равна суммарной величине v потока, входящего в сток t. Огра­ничения (3) выражают тот факт, что в каждую вершину (кроме источника и стока) приходит столько потока, сколько из нее уходит. Если для дуги (i, j) имеем xij = dij, то дуга (i, j) называется насыщенной потоком. Итак, задача нахождения максимального потока является задачей линейного программирования с целевой функцией и ограничениями (19) – (22). В силу своей специфики для ее решения существует более эффективный алгоритм, чем симплекс-метод. Разобьем множество вершин v сети G(V,U) на два непересекающихся подмножества R и Разрезом сети G(V,U) называется множество всех дуг (i, j), таких, что-либо i  R, j , либо j R , i . Т.е. разрез - это множество всех дуг, концевые вершины которых при­надлежат разным множествам: R и . При этом положим s R, t . Тогда мы получим разрез, отделяющий источник s от стока t. Если удалить все дуги некоторого разреза, отделяющего источник s от стока t, то на сети не останется пути ведущего из s в t. Пропускной способностью разреза (R, ) называется величина , Разрез, отделяющий источник от стока и обладающий минимальной пропускной способностью, называется минимальным разрезом. Теорема (о максимальном потоке и минимальном разрезе). В любой сети величина максимального потока из источника s в сток t равна пропускной способности минимального разреза. Пусть на сети имеется некоторый поток, который не является максимальным. Покажем, как найти путь, увеличивающий этот поток.

Похожие:

	Задания и методические указания к контрольной работе №2 по высшей... Методические указания предназначены для студентов 1 курса заочного отделения экономических специальностей бнту. Они могут быть также...		Задания и методические указания к контрольной работе №2 по высшей... Методические указания предназначены для студентов 1 курса заочного отделения экономических специальностей бнту. Они могут быть также...
	Немецкий язык методические указания и контрольные задания для студентов... Немецкий язык : методические указания и контрольные задания для студентов 2 курса железнодорожных специальностей заочной формы обучения...		Методические указания по выполнению контрольной работы 31 Общие указания 31 Производственные технологии : программа, методические указания и контрольные задания для студентов специальностей 1-25 01 07 – Экономика...
	Методические указания и контрольные задания для студентов специальности,... Методические указания и контрольные задания по дисциплине Стандартизация норм точности для студентов специальности: 1- 38. 02. 01...		Методические указания для самостоятельной работы студентов экономических... Методические указания к изучению дисциплины “Логистика” составлены на основе требований Государственного общеобразовательного стандарта...
	Методические указания и контрольные задания для студентов специальностей... Статистика: методические указания и контрольные задания для студентов специальностей 1-26 02 02 «Менеджмент» и 1-26 02 03 «Маркетинг»...		Методические указания и контрольные задания по дисциплине Методические указания и контрольные задания по дисциплине "Электротехника и электроника" для студентов спец. 37 01 06 "Техническая...
	- ...		Методические указания и тематика контрольных работ для студентов экономических специальностей Методические указания предназначены для студентов экономических специальностей заочной формы обучения. Они составлены в соответствии...