Нахождение исходного опорного решения

Транспортная задача

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

В общем виде задачу можно представить следующим об­разом: в т. пунктах производства A ₁, A ₂,..., A_m имеется од­нородный груз в количестве соответственно a ₁, a ₂ ,…, a_m. Этот груз необходимо доставить в п пунктов назначения B ₁, В ₂, …., В_п в количестве соответственно b ₁, b ₂ ,..., b_п. Сто­имость перевозки единицы груза (тариф) из пункта A_i в пункт B_j равна c_ij.

Требуется составить план перевозок, позволяющий вывез­ти все грузы и имеющий минимальную стоимость.

В зависимости от соотношения между суммарными запа­сами груза и суммарными потребностями в нем транспортные задачи могут быть закрытыми и открытыми.

З адача называется закрытой, если: открытой, если:

Рассмотрим закрытую транспорт­ную задачу.

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

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

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

 

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

 

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

1. Нахождение исходного опорного решения; 2. Проверка этого решения на оптимальность;

3. Переход от одного опорного решения к другому.

 

Приложение транспортных моделей к решению некоторых экономических задач

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

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

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

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

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

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

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

На предприятии имеются три группы станков, каждая из которых может выполнять пять операций по обработке дета­лей (операции могут выполняться в любом порядке). Макси­мальное время работы каждой группы станков соответственно равно 100, 250, 180 ч. Каждая операция должна выполняться соответственно 100, 120, 70, 110, 130 ч.

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

Производительность каждой группы станков на каждую операцию задана матрицей

Решение. Воспользуемся алгоритмом решения закрытой транспортной задачи (табл. 23.13).

Так как в задаче требуется найти максимум, а согласно алгоритму транспортной задачи находится минимум, тарифы умножим на (—1).

Находим потенциалы свободных клеток:

Клетка (1;2). -8+0-(-5)=-3.

Клетка (1;3). -13+0-(-11)=-2 и т.д.

 

Так как Δ₁₄ = 3 > 0, перераспределим грузы, получим

 

Полученное перераспределение грузов занесем в табл. 23.14.

Оценки свободных клеток составляют

 

 

Найденное решение является оптимальным, так как все оценки свободных клеток отрицательные.

Таким образом, на первой группе станков целесообразно выполнять операции 1 и 4 продолжительностью 40 и 60 ч со­ответственно, на второй группе — операции 1, 2 и 3 продолжи­тельностью 60, 120 и 70 ч соответственно, на третьей группе — операции 4 и 5 продолжительностью 50 и 130 ч соответственно. При этом максимальное число обработанных деталей составит 5 170 шт.

УПРАЖНЕНИЯ

Решить следующие транспортные задачи, заданные распреде­лительной таблицей.

5. Требуется спланировать перевозку строительного мате­риала с трех заводов к четырем строительным площадкам, используя железнодорожную сеть. В течение каждого кварта­ла на четырех площадках требуется соответственно 5, 10, 20, 15 вагонов строительных материалов. Возможности различных заводов соответственно равны 10, 15 и 25 вагонов в квартал. Условия задачи даны в табл. 23.15. Числа на пересечении строк и столбцов таблицы означают стоимость перевозки одного ва­гона (усл. ед.).

6. Решить транспортную задачу, заданную распредели­тельной табл. 23.16, причем перевозки от 2-го поставщика ко 2-му потребителю и от 3-го поставщика к 1-му потребителю временно закрыты (в таблице эти тарифы обозначены боль­шим числом М > 0).

7. В трех пунктах производства имеется одинаковая про­дукция в объеме 200, 170, 130 т. Эта продукция должна быть доставлена потребителям в количестве 50, 220, 80, 110 и 140 т. Стоимости перевозок единицы продукции от каждого постав­щика к каждому потребителю заданы матрицей

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

8. Фирма получила заказы на три вида выпускаемой ею продукции (бокалы, чашки и вазы), которые необходимо изго­товить в течение следующей недели. Размеры заказов: бока­лы — 4000 шт., чашки — 2400 шт., вазы — 1000 шт.

Участок по изготовлению имеет три станка, на каждом из которых можно делать любой из заказанных видов продукции с одинаковой производительностью. Однако единичные затра­ты по каждому виду продукции различны в зависимости от используемого станка и заданы табл. 23.17.

Кроме того, известно, что производственные мощности 2-го и 3-го станков на следующую неделю составят 3000 шт., а 1-го станка — 2000 шт.

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

 

Транспортная задача

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

В общем виде задачу можно представить следующим об­разом: в т. пунктах производства A ₁, A ₂,..., A_m имеется од­нородный груз в количестве соответственно a ₁, a ₂ ,…, a_m. Этот груз необходимо доставить в п пунктов назначения B ₁, В ₂, …., В_п в количестве соответственно b ₁, b ₂ ,..., b_п. Сто­имость перевозки единицы груза (тариф) из пункта A_i в пункт B_j равна c_ij.

Требуется составить план перевозок, позволяющий вывез­ти все грузы и имеющий минимальную стоимость.

В зависимости от соотношения между суммарными запа­сами груза и суммарными потребностями в нем транспортные задачи могут быть закрытыми и открытыми.

З адача называется закрытой, если: открытой, если:

Рассмотрим закрытую транспорт­ную задачу.

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

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

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

 

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

 

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

1. Нахождение исходного опорного решения; 2. Проверка этого решения на оптимальность;

3. Переход от одного опорного решения к другому.

 

Нахождение исходного опорного решения

Условия задачи и ее исходное опорное решение за­писываются в распределительной таблице.

Клетки, в которые поместим грузы, называются занятыми, им соответствуют ба­зисные переменные опорного решения.

Остальные клетки неза­нятые, или пустые, им соответствуют свободные переменные.

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

Метод минимального тарифа (элемента). Грузы распределяются в первую очередь в те летки, в которых находится минималь­ный тариф перевозок c_ij.

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

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

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

Пример 1. Определение эффективного варианта доставки изделий к потребителю

На складах A ₁, А ₂, А ₃ имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители В ₁, В ₂, B ₃ должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей (усл. ед.), см справа.

Проверим, является ли данная транспортная задача закрытой. Расчет справа.

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

 

Число занятых клеток в табл. 23.2 равно т + п - 1 = 3 + 3 – 1 = 5.

Это значит, что условие невырожденности выполнено. Исходное опорное решение запишем в виде матри­цы:Х₁

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