Применение методов линейного программирования для оптимизации стоимости перевозок (стр. 5 из 5)

1,5

А₄(а₄=80)

U₄=-0,3

1,2

2,0

1,5

2,5

Стоимость 3-его плана:

D₃=1•35+2•15+0,4•5+1•15+0,8•40+1•35+1,5•35+2,5•40=301,5.

Имеем:u₁+v₆-c₁₆=0,3>0,u₃+v₅-c₃₅=0,3>0. => По критерию оптимальности, третий план не оптимален. Далее max(0,3;0,3)=0,3. => Поместим перевозку в клетку А₃В₅,сместив 40=min(40,40) по циклу, указанному в таблице штрихом. Получим новую таблицу. Чтобы 4-ый план был невырожденным, оставим в клетке А₄В₅ нулевую перевозку. Найдем потенциалы: u₁+v₁=1,u₁+v₂=2,u₂+v₁=0,4,u₃+v₂=1, u₄+v₅=2,5, u₂+v₃=1, u₄+v₄=1,5, u₃+v₅=1,5 , u₄+v₆=0. Положим u₁=0,тогда v₁=1,u₂=-0,6,v₂=2,v₄=1,5, u₃=-1,u₄=0, v₃=1,6, v₅=2,5, v₆=0. Составим таблицу 3. :

Таблица 3. - Проведение итераций

ЦехаСклад	B₁(b₁=40)v₁=1	B₂(b₂=50)v₂=2	B₃(b₃=15)v₃=1,6	B₄(b₄=75)v₄=1,5	B₅(b₅=40)v₅=2,5	B₆(b₆=5)v₆=0

А₁(а₁=50)

U₁=0

1,0

2,0

3,0

2,5

3,5

А₂(а₂=20)

U₂=-0,6

0,4

3,0

1,0

2,0

3,0

А₃(а₃=75)

U₃=-1

0,7

1,0

0,8

1,5

А₄(а₄=80)

U₄=0

1,2

2,0

1,5

2,5

Стоимость 4-ого плана:

D₄=1•35+2•15+0,4•5+1•15+1•35+1,5•40+1,5•75=289,5.

Для всех клеток последней таблицы выполнены условия оптимальности:

1) u_i+v_j-с_ij=0 для клеток, занятых перевозками;

2) u_i+v_j-с_ij≤0 для свободных клеток.

Несодержательные ответы:

Прямой ЗЛП:

35 15 0 0 0 0

5 0 15 0 0 0

X = 0 35 0 0 40 0

0 0 0 75 0 5

min=289,5.

Двойственной ЗЛП:

U₁=0 ; U₂=-0,6 ; U₃=-1 ; U₄=0 ; V₁=1 ; V₂=2 ; V₃=1,6 ; V₄=1,5 ; V₅=2,5 ; V₆=0.

max=289,5.

Так как min=max, то по критерию оптимальности найдены оптимальные решения прямой и двойственной ЗЛП. Содержательный ответ: Оптимально перевозить так:

Из А₁вB₁– 35 сборочных агрегатов;

Из А₁вB₂– 15 сборочных агрегатов;

Из А₂вB₁– 5 сборочных агрегатов;

Из А₂вB₃– 15 сборочных агрегатов;

Из А₃вB₂– 35 сборочных агрегатов;

Из А₃вB₅– 40 сборочных агрегатов;

Из А₄вB₄– 75 сборочных агрегатов.

При этом стоимость минимальна и составит D_min=289,5. 5 сборочных агрегатов необходимо оставить на складе А₄ для их последующей перевозки в другие Цеха.

Список использованной литературы

1. Е.Г. Гольштейн, Д.Б. Юдин «Задачи линейного программирования транспортного типа», Москва, 2007.

2. И.Л. Акулич, В.Ф. Стрельчонок «Математические методы и компьютерные технологии решения оптимизационных задач», Рига, 2006.

3. Астафуров В.Г., Колодникова Н. - Компьютерное учебное пособие, раздел “Анализ на чувствительность с помощью двойственной задачи”, Томск-2004.

4. Алесинская Т.В. - Задачи по исследованию операций с решениями. Москва, 2008.

5. Смородинский С.С., Батин Н.В. - Оптимизация решений на основе методов и моделей математического программирования: Учебное пособие. Воронеж, 2009