Прикладная математика

Задача линейного программирования, Теория систем массового обслуживания

Задача 1. Задача линейного программирования

По предписанию врача пациенту необходимо перейти на диету и за сезон употребить питательные вещества, содержащиеся в фруктах и ягодах, в количествах, указанных в таблице 15.

Таблица 15

Данные по питательным веществам Вещества Содержание питательных веществ Нормы потреб¬ления. г. Фрукты Ягоды A 3 1 18 B 1 2 20 C 2 5 40 D 0 2 14 E 7 4 32 Цена, руб./кг. 30 40 Определите, какое количество фруктов и ягод необходимо ку¬пить за сезон, чтобы выполнить предписание врача с минимальными расходами.

Присвоим обозначения: x1 – количество потребленных фруктов; x2 – количество потребленных ягод.

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

Определим минимальное значение целевой функции F(X) = 30x1 + 40x2 при следующих условиях-ограничений.

3x1 + x2≥18

x1 + 2x2≥20

2x1 + 5x2≥40

2x2≥14

2x1 + 4x2≥32

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≥) вводим базисную переменную x3 со знаком минус. В 2-м неравенстве смысла (≥) вводим базисную переменную x4 со знаком минус. В 3-м неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус. В 4-м неравенстве смысла (≥) вводим базисную переменную x6 со знаком минус. В 5-м неравенстве смысла (≥) вводим базисную переменную x7 со знаком минус.

3x1 + 1x2-1x3 + 0x4 + 0x5 + 0x6 + 0x7 = 18

1x1 + 2x2 + 0x3-1x4 + 0x5 + 0x6 + 0x7 = 20

2x1 + 5x2 + 0x3 + 0x4-1x5 + 0x6 + 0x7 = 40

0x1 + 2x2 + 0x3 + 0x4 + 0x5-1x6 + 0x7 = 14

2x1 + 4x2 + 0x3 + 0x4 + 0x5 + 0x6-1x7 = 32

Умножим все строки на (-1) и будем искать первоначальный опорный план.

-3x1-1x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 = -18

-1x1-2x2 + 0x3 + 1x4 + 0x5 + 0x6 + 0x7 = -20

-2x1-5x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 = -40

0x1-2x2 + 0x3 + 0x4 + 0x5 + 1x6 + 0x7 = -14

-2x1-4x2 + 0x3 + 0x4 + 0x5 + 0x6 + 1x7 = -32

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

-3 -1 1 0 0 0 0 -1 -2 0 1 0 0 0 -2 -5 0 0 1 0 0 0 -2 0 0 0 1 0 -2 -4 0 0 0 0 1 Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

Смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки ресурсов, остающихся при принятии данного оптимального плана.

Решим систему уравнений относительно базисных переменных: x3, x4, x5, x6, x7

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,-18,-20,-40,-14,-32)

Базисное решение называется допустимым, если оно неотрицательно.

Базис B x1 x2 x3 x4 x5 x6 x7 x3 -18 -3 -1 1 0 0 0 0 x4 -20 -1 -2 0 1 0 0 0 x5 -40 -2 -5 0 0 1 0 0 x6 -14 0 -2 0 0 0 1 0 x7 -32 -2 -4 0 0 0 0 1 F(X0) 0 30 40 0 0 0 0 0

1. Проверка критерия оптимальности.

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

2. Определение новой свободной переменной.

Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

Ведущей будет 3-ая строка, а переменную x5 следует вывести из базиса.

3. Определение новой базисной переменной.

Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x2 необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-5).

Базис B x1 x2 x3 x4 x5 x6 x7 x3 -18 -3 -1 1 0 0 0 0 x4 -20 -1 -2 0 1 0 0 0 x5 -40 -2 -5 0 0 1 0 0 x6 -14 0 -2 0 0 0 1 0 x7 -32 -2 -4 0 0 0 0 1 F(X0) 0 30 40 0 0 0 0 0 θ 30:(-2) = -15 40:(-5) = -8 - - - - -

4. Пересчет симплекс-таблицы.

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис B x1 x2 x3 x4 x5 x6 x7 x3 -10 -13/5 0 1 0 -1/5 0 0 x4 -4 -1/5 0 0 1 -2/5 0 0 x2 8 2/5 1 0 0 -1/5 0 0 x6 2 4/5 0 0 0 -2/5 1 0 x7 0 -2/5 0 0 0 -4/5 0 1 F(X0) -320 14 0 0 0 8 0 0

Представим расчет каждого элемента в виде таблицы:

B x1 x2 x3 x4 x5 x6 x7 -18-(-40•(-1)):(-5) -3-(-2•(-1)):(-5) -1-(-5•(-1)):(-5) 1-(0•(-1)):(-5) 0-(0•(-1)):(-5) 0-(1•(-1)):(-5) 0-(0•(-1)):(-5) 0-(0•(-1)):(-5) -20-(-40•(-2))•(-5) -1-(-2•(-2)):(-5) -2-(-5•(-2)):(-5) 0-(0•(-2)):(-5) 1-(0•(-2)):(-5) 0-(1•(-2)):(-5) 0-(0•(-2)):(-5) 0-(0•(-2)):(-5) -40:(-5) -2:(-5) -5:(-5) 0:(-5) 0:(-5) 1:(-5) 0:(-5) 0:(-5) -14-(-40•(-2)):(-5) 0-(-2•(-2)):(-5) -2-(-5•(-2)):(-5) 0-(0•(-2)):(-5) 0-(0•(-2)):(-5) 0-(1•(-2)):(-5) 1-(0•(-2)):(-5) 0-(0•(-2)):(-5) -32-(-40•(-4)):(-5) -2-(-2•(-4)):(-5) -4-(-5•(-4)):(-5) 0-(0•(-4)):(-5) 0-(0•(-4)):(-5) 0-(1•(-4)):(-5) 0-(0•(-4)):(-5) 1-(0•(-4)):(-5) 0-(-40•40):(-5) 30-(-2•40):(-5) 40-(-5•40):(-5) 0-(0•40):(-5) 0-(0•40):(-5) 0-(1•40):(-5) 0-(0•40):(-5) 0-(0•40):(-5)

1. Проверка критерия оптимальности.

План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

2. Определение новой свободной переменной.

Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

Ведущей будет 1-ая строка, а переменную x3 следует вывести из базиса.

3. Определение новой базисной переменной.

Минимальное значение θ соответствует 5-му столбцу, т.е. переменную x5 необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1/5).

Базис B x1 x2 x3 x4 x5 x6 x7 x3 -10 -23/5 0 1 0 -1/5 0 0 x4 -4 -1/5 0 0 1 -2/5 0 0 x2 8 2/5 1 0 0 -1/5 0 0 x6 2 4/5 0 0 0 -2/5 1 0 x7 0 -2/5 0 0 0 -4/5 0 1 F(X0) -320 14 0 0 0 8 0 0 θ 14:(-23/5) = -55/13 - - - 8:(-1/5)=-40 - -

4. Пересчет симплекс-таблицы.

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса. Базис B x1 x2 x3 x4 x5 x6 x7 x5 50 13 0 -5 0 1 0 0 x4 16 5 0 -2 1 0 0 0 x2 18 3 1 -1 0 0 0 0 x6 22 6 0 -2 0 0 1 0 x7 40 10 0 -4 0 0 0 1 F(X1) -720 -90 0 40 0 0 0 0

Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5 x 6 x 7 -10:(-1/5) -23/5:(-1/5) 0:(-1/5) 1:(-1/5) 0:(-1/5) -1/5:(-1/5) 0:(-1/5) 0:(-1/5) -4-(-10•(-2/5)):(-1/5) -1/5-(-23/5•(-2/5)):(-1/5) 0-(0•(-2/5)):(-1/5) 0-(1•(-2/5)):(-1/5) 1-(0•(-2/5)):(-1/5) -2/5-(-1/5•(-2/5)):(-1/5) 0-(0•(-2/5)):(-1/5) 0-(0•(-2/5)):(-1/5) 8-(-10•(-1/5)):(-1/5) 2/5-(-23/5•(-1/5)):(-1/5) 1-(0•(-1/5)):(-1/5) 0-(1•(-1/5)):(-1/5) 0-(0•(-1/5)):(-1/5) -1/5-(-1/5•(-1/5)):(-1/5) 0-(0•(-1/5)):(-1/5) 0-(0•(-1/5)):(-1/5) 2-(-10•(-2/5)):(-1/5) 4/5-(-23/5•(-2/5)):(-1/5) 0-(0•(-2/5)):(-1/5) 0-(1•(-2/5)):(-1/5) 0-(0•(-2/5)):(-1/5) -2/5-(-1/5 • (-2/5)):(-1/5) 1-(0•(-2/5)):(-1/5) 0-(0•(-2/5)):(-1/5) 0-(-10•(-4/5)):(-1/5) -2/5-(-23/5•(-4/5)):(-1/5) 0-(0•(-4/5)):(-1/5) 0-(1•(-4/5)):(-1/5) 0-(0•(-4/5)):(-1/5) -4/5-(-1/5•(-4/5)):(-1/5) 0-(0•(-4/5)):(-1/5) 1-(0•(-4/5)):(-1/5) -320-(-10•8):(-1/5) 14-(-23/5•8):(-1/5) 0-(0•8):(-1/5) 0-(1•8):(-1/5) 0-(0•8):(-1/5) 8-(-1/5•8):(-1/5) 0-(0•8):(-1/5) 0-(0•8):(-1/5)

В базисном столбце все элементы положительные.

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai1

и из них выберем наименьшее:

min (50:13, 16:5, 18:3, 22:6, 40:10) = 31/5

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.

Базис B x1 x2 x3 x4 x5 x6 x7 min x5 50 13 0 -5 0 1 0 0 311/13 x4 16 5 0 -2 1 0 0 0 31/5 x2 18 3 1 -1 0 0 0 0 6 x6 22 6 0 -2 0 0 1 0 32/3 x7 40 10 0 -4 0 0 0 1 4 F(X1) -720 -90 0 40 0 0 0 0 0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x4 в план 1 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=5

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x1 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (5), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B x1 x2 x3 x4 x5 x6 x7 50-(16•13):5 13-(5•13):5 0-(0•13):5 -5-(-2•13):5 0-(1•13):5 1-(0•13):5 0-(0•13):5 0-(0•13):5 16:5 5:5 0:5 -2:5 1:5 0:5 0:5 0:5 18-(16•3):5 3-(5•3):5 1-(0•3):5 -1-(-2•3):5 0-(1•3):5 0-(0•3):5 0-(0•3):5 0-(0•3):5 22-(16•6):5 6-(5•6):5 0-(0•6):5 -2-(-2•6):5 0-(1•6):5 0-(0•6):5 1-(0•6):5 0-(0•6):5 40-(16•10):5 10-(5•10):5 0-(0•10):5 -4-(-2•10):5 0-(1•10):5 0-(0•10):5 0-(0•10):5 1-(0•10):5 -720-(16•(-90)):5 -90-(5•(-90)):5 0-(0•(-90)):5 40-(-2•(-90)):5 0-(1•(-90)):5 0-(0•(-90)):5 0-(0•(-90)):5 0-(0•(-90)):5

Получаем новую симплекс-таблицу:

Базис B x1 x2 x3 x4 x5 x6 x7 x5 42/5 0 0 1/5 -13/5 1 0 0 x1 16/5 1 0 -2/5 1/5 0 0 0 x2 42/5 0 1 1/5 -3/5 0 0 0 x6 14/5 0 0 2/5 -6/5 0 1 0 x7 8 0 0 0 -2 0 0 1 F(X1) -432 0 0 4 18 0 0 0

1. Проверка критерия оптимальности.

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

Окончательный вариант симплекс-таблицы:

Базис B x1 x2 x3 x4 x5 x6 x7 x5 42/5 0 0 1/5 -13/5 1 0 0 x1 16/5 1 0 -2/5 1/5 0 0 0 x2 42/5 0 1 1/5 -3/5 0 0 0 x6 14/5 0 0 2/5 -6/5 0 1 0 x7 8 0 0 0 -2 0 0 1 F(X2) -432 0 0 4 18 0 0 0 Оптимальный план можно записать так:

x1 = 31/5

x2 = 82/5

F(X) = 30•31/5 + 40•82/5 = 432

Значит, оптимальным режимом для получения необходимого количества питательных веществ будет потребление в день 31/5 фруктов и 82/5 ягод.

Задача 2. Теория систем массового обслуживания

Дан граф состояний системы массового обслуживания. Найти предельные вероятности всех состояний системы.

Пронумеруем вершины графа

Составим матрицу переходов из состояния i в состояние j

Каждый шаг равносилен переводу вектора вероятностей В в В•А. следовательно стабильной система станет при условии

или что тоже

То есть задача сводится к нахождению собственного вектора матрица .

1) Найдем собственные числа из характеристического уравнения:

λ1 = 1 2)Для каждого λ найдем его собственный вектор: λ1 = 1

( -λE)X = 0, тогда имеем ОСЛУ, решим ее методом Гаусса:

'

'

'

Домножим полученный вектор на величину обратную сумме его элементов, чтобы сумма элементов вектора вероятности составляла 1

ΣХ=3+9/4+3+1=37/4

Вектор вероятности будет иметь вид

Требуется построить сетевой график, определить все полные пути и критический путь, критические работы, все числовые характеристики и резервы времени работ, провести анализ и оптимизацию комплекса работ.

Перечень работ по строительству площадок Содержание работы Обозна¬чение. а, Предшест¬вующие ра¬боты Котф. пе¬ресчета ресурсов.

с г l b, Продолжи¬тельность работы. 1, Разработка проек тов доку¬ментации 3 - С,=0,1 14 строительство контейнер¬ных площадок - с:=0,2 16 Подпор кадров для работы на контейнерных площадках а;, а. с^О.З 2 Заявка па оборудование а4 3;, с4=0.4 л

э Строительство склада пере¬валки а< а с< 0.5 3 строительство площадок при ж/д станции а* а^ с6Ч).6 7 Изготовление необходимою количества контейнеров а7 а; с7=0.7 5 Завоз контейнеров ^8 а4 с?=0,8 5 Строительство склада для контейнеров а<) ас-, а7 С9=0,9 у Строительство участка ж/л от контейнерной площадки до склада а ю а2 а* с И1= 1.0 •л монтаж оборудования ап а9 а ю си=1.1 4

Для энергосистемы известны мощности источников И1...И4 и нагрузок Н1...Н4, а также стоимости передачи мощности от каждого источника к каждому потребителю в условных единицах. Спроектировать для данной энергосистемы электрическую сеть наименьшей стоимости.

Для энергосистемы известны мощности источников И1...И4 и нагрузок Н1...Н4, а также стоимости передачи мощности от каждого источника к каждому потребителю в условных единицах. Спроектировать для данной энергосистемы электрическую сеть наименьшей стоимости. Мощность источника, МВт'Мощность нагрузки, МВт Стоимость передачи 'Н1'Н2'Н3'Н4 И1'20'И1'30'И1'1'3'4'5 И2'30'И2'20'И2'5'2'10'3 И3'50'И3'55'И3'3'2'1'4 И4'20'И4'15'И4'6'4'2'6 1'3'4'5'20 5'2'10'3'30 3'2'1'4'50 6'4'2'6'20 30'20'55'15'

Решение: Проверим необходимое и достаточное условие разрешимости задачи. Σ a = 20 + 30+ 50 + 20 = 120 Σ b = 30 + 20 + 55 + 15 = 120 Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой. Занесем исходные данные в распределительную таблицу. '1'2'3'4'Запасы 1'1'3'4'5'20 2'5'2'10'3'30 3'3'2'1'4'50 4'6'4'2'6'20 Потребности'30'20'55'15' 1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. Искомый элемент равен 1. Для этого элемента запасы равны 50, потребности 55. Поскольку минимальным является 50, то вычитаем его. 1'3'4'5'20 5'2'10'3'30 ×'×'1'×'0 6'4'2'6'20 30'20'5'15'

Искомый элемент равен 1. Для этого элемента запасы равны 20, потребности 30. Поскольку минимальным является 20, то вычитаем его. 1'×'×'×'0 5'2'10'3'30 ×'×'1'×'0 6'4'2'6'20 10'20'5'15'

Искомый элемент равен 2. Для этого элемента запасы равны 30, потребности 20. Поскольку минимальным является 20, то вычитаем его. 1'×'×'×'0 5'2'10'3'10 ×'×'1'×'0 6'×'2'6'20 10'0'5'15'

Искомый элемент равен 2. Для этого элемента запасы равны 20, потребности 5. Поскольку минимальным является 5, то вычитаем его. 1'×'×'×'0 5'2'×'3'10 ×'×'1'×'0 6'×'2'6'15 10'0'0'15'

Искомый элемент равен 3. Для этого элемента запасы равны 10, потребности 15. Поскольку минимальным является 10, то вычитаем его. 1'×'×'×'0 ×'×'×'3'0 ×'×'1'×'0 6'×'2'6'15 10'0'0'5' Искомый элемент равен 6. Для этого элемента запасы равны 15, потребности 10. Поскольку минимальным является 10, то вычитаем его. 1'×'×'×'0 ×'×'×'3'0 ×'×'1'×'0 6'×'2'6'5 0'0'0'5'

Искомый элемент равен 6. Для этого элемента запасы равны 5, потребности 5. Поскольку минимальным является 3, то вычитаем его. 1'×'×'×'0 ×'×'×'3'0 ×'×'1'×'0 6'×'2'6'0 0'0'0'0' '1'2'3'4'Запасы 1'1'20 3'4'5'20 2'5'2'20 10'3'10 30 3'3'2'1'50 4'50 4'6'10 4'2'5 6'5 20 Потребности'30'20'55'15'

В результате получен первый опорный план, который является допустимым, так как все потоки из источников выведены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

4. Проверим оптимальность опорного плана. Найдем потенциалы ui и vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 1; 0 + v1 = 1; v1 = 1 u4 + v1 = 6; 1 + u4 = 6; u4 = 5 u4 + v3 = 2; 5 + v3 = 2; v3 = -3 u4 + v4 = 6; 5 + v4 = 6; v4 = 1 u3 + v3 = 1; -3 + u3 = 1; u3 = 4 u2 + v4 = 3; 1 + u2 = 3; u2 = 2

u2 + v2 = 2; 2 + v2 = 2; v2 = 0 'v1=1'v2=0'v3=-3'v4=1 u1=0'1'20 3'4'5 u2=2'5'2'20 10'3'10 'u3=4'3'2'1'50 4 u4=5'6'10 4'2'5 6'5 'Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+vj > cij (3;1): 4 + 1 > 3; ∆31 = 4 + 1 - 3 = 2 (3;2): 4 + 0 > 2; ∆32 = 4 + 0 - 2 = 2

(3;4): 4 + 1 > 4; ∆34 = 4 + 1 - 4 = 1

(4;2): 5 + 0 > 4; ∆42 = 5 + 0 - 4 = 1 max(2,2,2,1) = 2

Выбираем максимальную оценку свободной клетки (3;2): 2. Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице. '1'2'3'4'Запасы 1'1'20 3'4'5'20 2'5'2'20 - 10'3'10 + 30 3'3'2'+ 1'50 - 4'50 4'6'10 4'2'5 + 6'5 - 20 Потребности'30'20'55'15'

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4,4) = 5. Прибавляем 5 к объемам потоков, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. '1'2'3'4'Запасы 1'1'20 3'4'5'20 2'5'2'15 10'3'15 30 3'3'2'5 1'45 4'50 4'6'10 4'2'10 6'20 Потребности'30'20'55'15'

4. Проверим оптимальность опорного плана. Найдем потенциалы ui и vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 1; 0 + v1 = 1; v1 = 1 u4 + v1 = 6; 1 + u4 = 6; u4 = 5 u4 + v3 = 2; 5 + v3 = 2; v3 = -3 u3 + v3 = 1; -3 + u3 = 1; u3 = 4 u3 + v2 = 2; 4 + v2 = 2; v2 = -2

u2 + v2 = 2; -2 + u2 = 2; u2 = 4

u2 + v4 = 3; 4 + v4 = 3; v4 = -1 'v1=1'v2=-2'v3=-3'v4=-1 u1=0'1'20 3'4'5 u2=4'5'2'15 10'3'15 'u3=4'3'2'5 1'45 4 u4=5'6'10 4'2'10 6 Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+vj > cij (3;1): 4 + 1 > 3; ∆31 = 4 + 1 - 3 = 2 max(2) = 2 Выбираем максимальную оценку свободной клетки (3;1): 3. Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице. '1'2'3'4'Запасы 1'1'20 3'4'5'20 2'5'2'15 10'3'15 30 3'3'+ 2'5 1'45 - 4'50 4'6'10 - 4'2'10 + 6'20 Потребности'30'20'55'15'

Из потоков хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 1) = 10. Прибавляем 10 к объемам потоков, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. '1'2'3'4'Запасы 1'1'20 3'4'5'20 2'5'2'15 10'3'15 30 3'3'10 2'5 1'35 4'50 4'6'4'2'20 6'20 Потребности'30'20'55'15'

4. Проверим оптимальность опорного плана. Найдем потенциалы ui и vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 1; 0 + v1 = 1; v1 = 1 u3 + v1 = 3; 1 + u3 = 3; u3 = 2 u3 + v2 = 2; 2 + v2 = 2; v2 = 0 u3 + v3 = 1; 2 + v3 = 1; v3 = -1 u2 + v2 = 2; 0 + u2 = 2; u2 = 2 u4 + v3 = 2; -1 + u4 = 2; u4 = 3 u2 + v4 = 3; 2 + v4 = 3; v4 = 1 'v1=1'v2=0'v3=-1'v4=1 u1=0'1'20 3'4'5 u2=2'5'2'15 10'3'15 'u3=2'3'10 2'5 1'35 4 u4=3'6'4'2'20 6 Опорный план является оптимальным. Минимальные затраты составят: F(x) = 1*20 + 2*15 + 3*15 + 3*10 + 2*5 + 1*35 + 2*20 = 210


Способ заказа и контакты