Моделирование транспортной задачи

a_i1x₁ + a_i2x₂ = b_i ,(i = 1, 2, ..., m). Условия неотрицательности определяют  полуплоскости соответственно  с граничными прямыми х = 0, х = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых  являются решением данной системы.

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

Если в системе ограничений (1.2.2) - (1.2.3) n = 3, то каждое неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого a_i1x₁ + a_i2x₂ + a_i3x₃ = b_i  ,(i = 1, 2, ..., n), а условия неотрицательности - полупространства с граничными плоскостями соответственно х_j = 0 (j = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая  называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью. Пусть в системе ограничений (1.2.2) - (1.2.3) n 3; тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью a_i1x₁ + a_i2x₂ + a_iNx_N = b_i (i = 1, 2, ..., m), а условия неотрицательности - полупространства с граничными гиперплоскостями х_j 0 (j = 1, 2, ..., n).

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

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

 

 

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

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

Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности).

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

Нахождение опорного плана. Требуется определить опорный план и путём последовательных операций найти оптимальное решение. Опорный план можно найти следующими методами: «северо-западного угла», «наименьшего элемента», двойного предпочтения и аппроксимацией Фогеля.

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

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

Алгоритм:

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

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

Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

Метод потенциалов и метод последовательного улучшения плана. Пусть - некоторый опорный план задачи T. Обозначим через совокупность векторов , отвечающих основным коммуникациям плана . Наши рассуждения будут вестись в предположении невырожденности задачи T. Поэтому состоит из m+n-1 векторов и является базисом опорного плана .

На первом этапе метода потенциалов вычисляются предварительные потенциалы

удовлетворяющие системе уравнений

                                                   для .                                 (3.1)

(Здесь - множество пар индексов векторов, составляющих базис плана .)

Переименуем векторы базиса и обозначим l-й вектор через

Учитывая, что все компоненты вектора , кроме двух, равных единице, равны нулю, можно переписать систему (3.1) в эквивалентном виде

.

Здесь

;

- стоимость единичной перевозки по коммуникации, соответствующей вектору .

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

,

То в соответствии с критерием оптимальности метода улучшения плана данный план - решение задачи. Это же заключение следует из критерия оптимальности, используемого в методе потенциалов.

Предположим, что при некоторых i,j

.

Тогда в соответствии с методом последовательного улучшения плана выбирается такая пара индексов , на которой величина

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

Согласно методу улучшения плана после разложения вводимого вектора (вектора ) по векторам старого базиса разыскивается величина

                                                     .                                              (3.2)

Здесь - коэффициент при i-м векторе базиса в разложении вектора ограничений (вводимого вектора) по векторам старого базиса; минимум берется по тем индексам i, для которых . Если , то из базиса удаляется его r-й вектор.

Базисные компоненты нового плана определяются по формуле

                                                                                   (3.3)

Для транспортной задачи коэффициенты равны нулю или . При этом в том и только в том случае, если i-й вектор базиса соответствует коммуникации, которая занимает нечетную (четную) позицию в построенном маршруте. Поэтому формула (3.2) в случае транспортной задачи может быть заменена правилом: - минимальная нечетная перевозка маршрута, связывающего пункты и . Это правило и используется в методе потенциалов. Формула (3.3) применительно к транспортной задаче превращается в правило изменения плана перевозок, употребляемое в методе потенциалов: перевозки, запланированные по нечетным (четным) коммуникациям, уменьшаются (увеличиваются) на величину , перевозка между и полагается равной , остальные перевозки сохраняют свои значения.

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

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

Общий вид решения экономических задач можно разделить на следующие этапы:

1) постановка задачи;

2) поиск оптимального решения;

3) внедрение.

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

 

 

 

 

 

 

 

 

 

 

 

2. Расчет модели

 

2.1  Постановка задачи

 

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

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

Программа должна работать на IBM совместных персональных компьютерах. Если говорить о типе процессоров им должен быть Pentium 1 и выше, а объем запоминающего устройства 16 Мб. Тип видеоадаптера- SVGA.

В качестве контрольного примера рассмотрены следующие задачи:

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

 

Таблица 1 - задача 1

Поставщик	Потребитель				Запас
	1	2	3	4
1	3	5	6	2	170
2	6	4	7	5	250
3	5	4	6	5	180
Спрос	150	230	160	60	600

 

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

Начальный план перевозок определить с помощью метода северо-западного угла.

В городе N имеется 4 склада А_i, на которых хранится ткань (в рулонах) и 5 магазинов B_j, занимающихся продажей ткани. Ниже, в таблице, приведены данные по количеству рулонов на каждом складе, запросы магазинов и стоимость перевозки одного рулона из А_i в B_j. Необходимо составить такой план перевозок, при котором запросы магазинов будут удовлетворены при минимальной суммарной стоимости перевозок.

 

Таблица 2 - Задача 2

Магазины Склад	B1 (b1=40)	B2 (b2=50)	B3 (b3=15)	B4 (b4=75)	B5(b5=40)
А1 (а1=50)	1,0	2,0	3,0	2,5	3,5
А2(а2=20)	0,4	3,0	1,0	2,0	3,0
А3(а3=75)	0,7	1,0	1,0	0,8	1,5
А4(а4=80)	1,2	2,0	2,0	1,5	2,5

 

В данном случае Уa_i=225 >Уb_j=220 => имеем дело с открытой моделью транспортной задачи.

 

 

 

 

 

 

 

2.1.1 Экономическая интерпретация задачи

 

В данном курсовом проекте была реализована программа для решений задач о размещения производства.

Для её выполнения был выбран язык программирования Delphi 7.0, Данная программа  легка в пользовании, и подойдет для выполнения похожих задач на движение.

Для пользования программой подойдет любой компьютер с ОС.

 

2.1.2 Построение математической модели и методы ее реализации

 

 

Алгоритм метода потенциалов складывается из предварительного этапа и конечного числа однотипных итераций. На предварительном этапе строится исходный опорный план задачи T и составляется матрица