Материал: 1820

Введем некоторые обозначения: Ai* - излишек нераспределенного груза от поставщика Ai, Bj* - недостача в поставке груза потребителю Bj.

Находим незанятую клетку с минимальным тарифом (рассматриваем нефиктивных потребителей): (2,2). Помещаем туда меньшее из чисел A2*=180 и B2*=160. Спрос потребителя B2 удовлетворён (B2*=0), A2* стало равным 180-160=20.

Находим незанятую клетку с минимальным тарифом: (3,4). Помещаем туда меньшее из чисел A3*=240 и B4*=180. Спрос потребителя B4 удовлетворён (B4*=0), A3* стало равным 240180=60.

Находим незанятую клетку с минимальным тарифом: (1,1). Помещаем туда меньшее из чисел A1*=140 и B1*=80. Спрос потребителя B1 удовлетворён (B1*=0), A1* стало равным 140-80=60. Находим незанятую клетку с минимальным тарифом: (2,3). Помещаем туда меньшее из чисел A2*=20 и B3*=120. Продукция пункта A2 распределена (A2*=0), B3* стало равным 12020=100.

Находим незанятую клетку с минимальным тарифом: (3,3). Помещаем туда меньшее из чисел A3*=60 и B3*=100. Продукция пункта A3 распределена (A3*=0), B3* стало равным 100-60=40.

Находим незанятую клетку с минимальным тарифом: (1,3). Помещаем туда меньшее из чисел A1*=60 и B3*=40. Спрос потребителя B3 удовлетворён (B3*=0), A1* стало равным 60-40=20. Осталось распределить 20 единиц груза из пункта А1. Неудовлетворённым остался только спрос фиктивного потребителя – пункта В5. Помещаем туда 20, после чего вся продукция становится распределённой и спрос всех потребителей удовлетворён.

Таким образом, начальным опорным планом является

Z(X0 ) 80 6 40 9 20 3 160 4 20 7 60 8 180 5 3060.

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

Пусть Ui и Vj - потенциалы i-го склада и j-го магазина соответственно.

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=C'i,j, просматривая все занятые клетки. Получим:

U1 = 0

V1 = C'1,1 – U1 = 6 - 0 = 6

V3 = C'1,3 - U1 = 9 – 0 = 9

V5 = C'1,5 – U1 = 3 – 0 = 3

U2 = C'2,3 - V3 = 7 – 9 = -2

U3 = C'3,3 – V3 = 8 – 9 = -1

V2 = C'2,2 – U2 = 5 – (-1) = 6

V4 = C'3,4 – U3 = 5 – (-1) = 6

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

S1,2 = C'1,2 - (U1 + V2) = -1

S1,4 = C'1,4 - (U1 + V4) = 3

S2,1 = C'2,1 - (U2 + V1) = 4

S2,4 = C'2,4 - (U2 + V4) = 7

S2,5 = C'2,5 - (U2 + V5) = 2

S3,1 = C'3,1 - (U3 + V1) = 4

26

S3,2 = C'3,2 - (U3 + V2) = 7

S3,5 = C'3,5 - (U3 + V5) = 0

Имеем одну клетку с отрицательной оценкой – клетка (1,2). Строим для нее цикл так, чтобы он начинался и заканчивался в этой клетке, а остальными узлами были бы загруженные клетки

таблицы.

Перемещаем по циклу груз величиной в 40 единиц (выбирается минимальное количество груза из значений, указанных в заполненных клетках цикла, помеченных знаком "минус", так как мы не можем отнять больше единиц продукции, чем есть), прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус".

В результате перемещения по циклу получим новый план:

Целевая функция (суммарные транспортные расходы и расходы на производство по полученному плану)

Z(X1 ) 80 1 40 5 20 3 120 4 60 7 60 8 180 5 3020. Значение целевой функции уменьшилось на 40 единиц по сравнению с предыдущим этапом.

Проверим полученный план на оптимальность. Подсчитаем потенциалы. U1 = 0

V1 = C'1,1 – U1 = 6 - 0 = 6

V2 = C'1,2 - U1 = 5 – 0 = 5

V5 = C'1,5 – U1 = 3 – 0 = 3

U2 = C'2,2 – V2 = 4 – 5 = -1

V3 = C'2,3 – U2 = 7 – (-1) = 8

U3 = C'3,3 – V3 = 8 – 8 = 0

V4 = C'3,4 – U3 = 5 – 0 = 5

Для свободных клеток определим значения оценок

S1,3 = C'1,1 - (U1 + V1) = 3

S1,4 = C'1,4 - (U1 + V4) = 3

S2,1 = C'2,1 - (U2 + V1) = 3

S2,4 = C'2,4 - (U2 + V4) = 7

S2,5 = C'2,5 - (U2 + V5) = 1

S3,1 = C'3,1 - (U3 + V1) = 3

27

S3,2 = C'3,2 - (U3 + V2) = 7

S3,5 = C'3,5 - (U3 + V5) = -1

План не оптимален, так как имеется клетка с отрицательной оценкой – (3,5). Строим для нее цикл.

Целевая функция (транспортные расходы)

Z(X2 ) 80 6 60 5 100 4 80 7 40 8 180 5 20 2 3000. Значение целевой функции уменьшилось на 20 единиц по сравнению с предыдущим этапом.

Проверим полученный план на оптимальность. Подсчитаем потенциалы. U1 = 0

V1 = C'1,1 – U1 = 6 - 0 = 6

V2 = C'1,2 - U1 = 5 – 0 = 5

U2 = C'2,2 – V2 = 4 – 5 = -1

V3 = C'2,3 – U2 = 7 – (-1) = 8

U3 = C'3,3 – V3 = 8 – 8 = 0

V4 = C'3,4 – U3 = 5 – 0 = 5

V5 = C'3,5 – U3 = 2 – 0 = 2

Для свободных клеток определим значения оценок

S1,3 = C'1,1 - (U1 + V1) = 1

S1,4 = C'1,4 - (U1 + V4) = 4

S1,5 = C'1,5 - (U1 + V5) = 1

S2,1 = C'2,1 - (U2 + V1) = 3

S2,4 = C'2,4 - (U2 + V4) = 7

S2,5 = C'2,5 - (U2 + V5) = 2

S3,1 = C'3,1 - (U3 + V1) = 3

S3,2 = C'3,2 - (U3 + V2) = 7

Так как все оценки Si,j>=0, то полученный план является оптимальным, минимальные транспортные расходы равны 3000.

28

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

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

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

Задачи

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

1)

2. Для следующей транспортной задачи а) составить экономико-математическую модель; б) найти оптимальное распределение поставок и минимальные затраты, выполнив первоначальное распределение поставок методом северо-западного угла. Себестоимость продукции не учитывать.

29

3. Закончить решение транспортной задачи, начиная с заданного распределения поставок (в правом углу каждой клетки).

5.Модели целочисленного линейного программирования

5.1Практическое занятие № 10 (4 часа). Решение задач

линейного целочисленного программирования Цель занятия: научиться находить решение задач линейного целочисленного

программирования методом Гомори.

Методические указания.

Задача линейного целочисленного программирования (ЦЗЛП) формулируются следующим образом: найти такое решение (план) Х x1, x2,x3, ,xn , при котором линейная функция

n

Z cj xj

j 1

принимает максимальное или минимальное значение при ограничениях

n

aij xj , i 1,m

j 1

xj 0, i 1,n, xj – целые числа

Рассмотрим решение таких задач с использованием метода Гомори (метода отсечения). Алгоритм метода:

1)Симплексным методом решаем ЗЛП без условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для ЦЗЛП.

2)Если среди компонент оптимального решения есть нецелые, то выбираем компоненту с наибольшей целой частью. По соответствующему уравнению системы, например с номером j, полученной на последнем шаге симплексного метода, выражающим основные mпеременные

отсечение:

j jm 1 xm 1 jm 2 xm 2 jn xn 0, где символ - дробная часть числа.

3) последнее неравенство введением дополнительной неотрицательной целочисленной переменной преобразовываем в равносильное уравнение:

j jm 1 xm 1 jm 2 xm 2 jn xn xn 1 0

ивключаем его в ограничение исходной задачи.

4)Полученную расширенную задачу решаем симплексным методом. Если оптимальный план будет целочисленным, то ЦЗЛП решена. Иначе возвращаемся к пункту 2 алгоритма.

Пример.

Для приобретения оборудования по сортировке зерна фермер выделяет 34 ден ед. Оборудование должно быть размещено на площади, не превышающей 60 м2. Фермер может заказать оборудование двух видов: менее мощные машины типа А стоимостью 3 ден. ед.,

30