Решение экономических ЛЗП, сводящихся к транспортной задаче

 

Содержание 

     1. Введение  …………………………………………………………………..3

     2. Постановка задачи  и анализ  исходных  данных ……………………….4

     3. Алгоритм …………………………………………………………………  14

     4. Расчётная  часть …………………………………………………….…… 15

     5. Программный  продукт ……………………………………………….…  50

     6. Заключение ………………………………………………………….….... 56 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     1. Введение 

     Математика  необходима  в повседневной  жизни, следовательно определённые  математические  навыки  нужны  каждому  человеку. Нам  приходится  в  жизни  считать (например, деньги), постоянно используем (часто не  замечая) знания о величинах, характеризующих протяженности, площади, объемы, промежутки  времени, скорости  и многое   другое. Важным частным случаем задачи линейного программирования является так называемая транспортная задача.

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

1. оптимальное закрепление за станками операций по обработке деталей. В них С_ij является таким экономическим показателям, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы  обработать максимальное количество деталей. Так как транспортная задача требует нахождения  минимума, то значения   берутся с отрицательным знаком;
2. оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью . Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;
3. задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции;
4. увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность.

 
 
 
 
 
 
 
 
 
 
 
 

2.Постановка задачи и анализ исходных данных 

        Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления А₁ А₂, ..., А_т в п пунктов назначения В₁, В₂,..., В_п. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. При решении транспортной задачи, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через c_ij тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через а_i — запасы груза в i-м пункте отправления, через bj — потребности в грузе в j-м пункте назначения, а через x_ij — количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции                                                                                          (1)

       

при условиях                                                                                                      (2)

        (3)

                                                                                                                             (4)

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

Всякое  неотрицательное решение систем линейных уравнений (2) и (3), определяемое матрицей , называется планом транспортной задачи.

План , при котором функция (1) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

    Обычно  исходные данные транспортной задачи записывают в виде табл.1.

           Таблица 2.1

   Очевидно, общее наличие груза у поставщиков  равно 

а общая  потребность в грузе в пунктах  назначения равна единице.

Если  общая потребность в грузе  в пунктах назначения равна запасу груза в пунктах отправления, т. е.

(5)

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

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

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

       

вводится  фиктивный  (n + 1)-й пункт назначения с потребностью

       

и соответствующие  тарифы считаются равными нулю: . Полученная задача является транспортной задачей, для которой выполняется равенство (5).

   Аналогично, при

       

водится фиктивный (m+1)-й пункт отправления с запасом груза

       

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

       Число переменных Х_ij в транспортной задаче с т пунктами отправления и п пунктами назначения равно пт, а число уравнений в системах (2) и (3) равно

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

       Если в опорном  плане число отличных от нуля компонент  равно в точности п + т — 1, то план является невырожденным, а если меньше — то вырожденным.

       Для определения  опорного плана существует несколько  методов. Три из них — метод северо-западного угла, метод минимального элемента и метод аппроксимации Фогеля — рассматриваются ниже.

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

       Для определения  оптимального плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждая неизвестная входит лишь в два уравнения систем (2) и (3) и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы. Два из них — метод   потенциалов   и   метод  дифференциальных   рент — рассмотрены ниже. 

       Определение опорного плана транспортной задачи.

       Как и при решении задачи линейного программирования симплексным методом, определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана. Этот план, как уже отмечалось выше, находят методом северо-западного угла, методом минимального элемента или методом аппроксимации Фогеля. Сущность этих методов состоит в том, что опорный план находят последовательно за п + т — 1 шагов, на каждом из которых в таблице условий задачи заполняют одну клетку, которую называют занятой. Заполнение одной из клеток обеспечивает полностью либо удовлетворение потребности в грузе одного из пунктов назначения (того, в столбце которого находится заполненная клетка), либо вывоз груза из одного из пунктов отправления (из того, в строке которого находится заполняемая клетка).

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