Линейная алгебра и математическое программирование (стр. 2 из 4)

Координаты точек: A(0,0) , B(0,3), C(3,

), D(3,1), E(2,0)

В соответствии с коэффициентами целевой функцией

z = 4 x₁ + x₂

max

построим вектор

( 4, 1) и прямую 4х₁ + х₂ = 0.

Перемещаем прямую по направлению вектора.

Точкой выхода из области допустимых решений является точка С(3, ).

В точке С(3,

) и будет оптимальное решение (максимальное), то есть при х₁ = 3; х₂ = значение целевой функции будет максимальным

Zmax= 4 * 3 +

= 14 .

Проверка:

В соответствии с одной из теорем теории линейного программирования линейная функция z = 4 x₁ + x₂ достигает максимального значения в вершинах многогранника, т.е. в точках A(0,0) , B(0,3), C(3,

), D(3,1), E(2,0).

Вычислим значения z = 4 x₁ + x₂ в этих точках:

· z (A(0,0)) = 4*0 + 0 = 0

· z (B(0,3)) = 4*0 + 3 = 3

· z (D(3,1)) = 4*3 + 1 = 13

· z (E(2,0)) = 4*2 + 0 = 8

· z (C(3,

)) = 4*3 + = 14 . , что и подтверждаем максимальность значения целевой функции.

Задачи 31–40. На трех базах А₁, А₂, А₃ имеется однородный груз в количестве а₁, а₂, а₃ единиц. Этот груз нужно перевезти в пять пунктов В1, В2, В3, В4, В5 в количестве b1, b2, b3, b4, b5 единиц соответственно. Затраты на перевозку груза между пунктами поставок и потребления заданы матрицей тарифов С:

.

Спланировать перевозки так, чтобы их общая стоимость была минимальной.

40.

Решение:

Вычислим y =

= 350 + 400 + 250 = 1000,

к =

= 175 + 225 + 240 + 160 + 200 = 1000, так как к = y , то решаемая транспортная задача является закрытой.

Обозначим через

количество груза, перевозимого из пункта в пункт .

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

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

при ограничениях

,

,

X ij ≥ 0 , i =

j = , m = 5.

Оптимальным решением задачи является матрица Xopt = ( Xij )3x5, удовлетворяющая системе ограничений и доставляющая минимум целевой функции.

Условия задачи и ее исходное решение будем записывать в распределительную таблицу. Клетки, в которые поместим грузы, называются занятыми, остальные клетки – незанятыми, или пустыми. В верхнем правом углу каждой клетки будем записывать тарифы. Существует несколько способов нахождения исходного решения.

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

Процесс распределения продолжается до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены. При распределении грузов может оказаться, что количество занятых клеток меньше, чем m + n -1 = 5 + 3 – 1 = .

В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми.

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

Найдем исходное решение по методу минимального тарифа. Для этого составим следующую распределительную таблицу:

bi ai		1	2	3	4	5
		175	225	240	160	200
1	350	5175	15175	18	16	8
2	400	6	1040	15	6160	4200
3	250	25	2010	10240	15	18

Число занятых клеток в таблице, приведенной выше, равно m + n – 1 = 5 + 3 – 1 = 7, то есть условие невырожденности выполнено. Получили исходное решение, которое запишем в виде матрицы

Х₁ =

Стоимость перевозки при исходном решении составляет

f₁ = 175 * 5 + 175 * 15 + 40 * 10 + 160 * 6 + 200 * 4 + 10 * 20 + 240 * 10 = 8260.

Проверим найденное решение транспортной задачи на оптимальность Найденное исходное решение проверяется на оптимальность методом потенциалов по следующему критерию: если решение транспортной задачи является оптимальным, то ему соответствует система m+n ( 5 + 3 = 8 ) действительных чисел

и

, удовлетворяющих условиям

для занятых клеток и

– для свободных клеток.

Числа

и

называются потенциалами. В распределительную таблицу добавляют столбец

и строку

.

Потенциалы

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

Обозначим

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

Проверим найденное решение на оптимальность, добавив в распределительную таблицу, приведенную ниже, столбец

и строку .

Полагая

, запишем это значение в последнем столбце
таблицы.

bi ai		1	2	3	4	5
		175	225	240	160	200	𝛼i
1	350	5 175	15175	18	16	8	0
2	400	6	1040	15	6160	4200	-5
3	250	25	2010	10240	15	18	0
𝛽i	5	15	10	11	9

Для клетки (1,1) :

1 + 1 = 5, 1 = 0, 1 = 5