Транспортная задача линейного программирования

1,0

2,0

3,0

2,5

3,5

0

А₂(а₂=20)

U₂=-0,6

0,4

3,0

1,0

2,0

3,0

0

А₃(а₃=75)

U₃=-1

0,7

1,0

1,0

0,8

1,5

0

А₄(а₄=80)

U₄=0

1,2

2,0

2,0

1,5

2,5

0

Стоимость 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 рулонов полотна необходимо оставить на складе А₄ для их последующей перевозки в другие магазины.

8.Выводы.

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

Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов c_ij имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие:

- оптимальное закрепление за станками операций по обработке деталей. В них c_ij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения c_ij берутся с отрицательным знаком;

- оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью c_ij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;

- задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции;

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

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

Таким образом, важность решения данной задачи для экономики несомненна. Приятно осознавать, что у истоков создания теории линейного программирования и решения, в том числе и транспортной задачи, стоял русский ученый - Леонид Витальевич Канторович.

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

1. Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшая математика. Математическое программирование ”, Минск, Вышейшая школа, 2001г.

2. Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г.

3. В.И. Ермаков “Общий курс высшей математики для экономистов”, Москва, Инфра-М, 2000г.