Реферат: Пособие и методические указания к выполнению курсовой работы

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ (МИИТ)

Институт экономики и финансов


Кафедра «Экономика строительного производства»


М.В. КОКИН


Экономико-математические методы в железнодорожном строительстве.

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


Пособие и методические указания к выполнению
курсовой работы


Москва – 2005


ПРЕДИСЛОВИЕ

Пособие и методические указания предназначены для выполнения курсовой работы студентами специальностей «Строительство железных дорог. Путь и путевое хозяйство», «Мосты, тоннели и метрополитены», «Промышленное и гражданское строительство» и «Управление, планирование на предприятии (строительство)», изучающих курс «Экономика строительства».

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

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

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

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

Основоположниками экономико-математических методов у нас в стране являлись А.Л. Лурье, Л.В. Канторович, Ф.И. Карпелевич – за рубежом И.Л. Бирман, Дж. Данциг, Фогель и др.


^ ОБЩИЕ ПОЛОЖЕНИЯ

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

Цель – это то, во имя чего осуществляется исследуемый (моделируемый) производственный процесс.

Конечная цель работы строительных организаций – ввод в эксплуатацию построенных объектов или сооружений.

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

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

Математическая интерпретация критерия оптимальности представляется в виде функции многих переменных – носит название целевой функции имеет вид:

(1)

где Сj – коэффициенты искомых переменных Хjр, представляют собой величину критерия оптимальности в расчете на единицу соответствующей переменной.

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

(2)



(3)

где aj - потребность в материально-технических ресурсах (приведенные затраты) на единицу искомой переменной величины;

xjn – искомая переменная величина;

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

Условие xj ≥ 0 имеет экономический смысл искомых переменных, которые не могут принимать отрицательных значений. Это условие предусмотрено при решении задач линейного программирования.

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

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

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

Программирование – это распределение ограниченных ресурсов наилучшим способом для достижения поставленных целей.

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

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

^ МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ
В строительстве распространенной является ситуация, при которой имеется ряд строек и несколько предприятий – поставщиков (карьеров, заводов, комбинатов), обеспечивающих эти стройки однородными материалами (балластными материалами, песком, щебнем, кирпичом и т. д.).

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

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

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

Решение транспортной задачи производится в матричной системе.

Допустим, что имеется ряд строек (Вn), несколько поставщиков (Аm), а затраты по транспортировке материалов от каждого поставщика к каждому потребителю (стройке) – (Сnm). Потребности в материалах по каждой стройке известны (bn) и известна мощность (возможность) каждого поставщика (dm).

Тогда матрица, целевая функция и система ограничений примут следующий вид:
Матрица
Карьеры-поставщики

Стройки–получатели

n


Мощность поставщиков di

В1

В2

В3

A1


X11

C11


X12


C12


X13

C13

d1










A2


X21

С21


X22

C22


X23

C23

d2










A3 m

X31

Xm1

C31

X32

Xm2

C32

X33

Xmn

C33

d3

dm







Cmn

Потребность строек

bj

b1


b2


b3

bn





Целевая функция примет вид:



или более обще



где неизвестные Х11, Х12…Хmn искомые величины поставок и

первый номер – индекс отправителя (строки)

а второй – номер получателя (столбца).

Т.е. Х11 означает размер перевозок от первого отправителя, первому получателю.

Х12 – от первого отправителя ко второму получателю и т. д.

С11, С12…Сmn – издержки по транспортировке или приведенные затраты.

^ Система ограничений.

а) по ресурсам (по объему производства)



б) по потребности строек (получателя)




в)


т.е. отрицательных значений Хij быть не может.

m – число предприятий по производству;

di – объем производства предприятий;

n – стройки, потребляющие материалы;

bj – потребность в материалах каждой стройки.

Транспортная задача может быть закрытой и открытой.

Закрытой является, если объем производства и потребления равны между собой, т.е.



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




Для решения открытой задачи вводится дополнительный фиктивный потребитель, потребность которого равна разности



Т.е. вводится в неравенство дополнительные Хi, n+1, равные поставкам от каждого поставщика фиктивному потребителю и неравенство превращается в уравнение



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

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

Значение Сij для фиктивного пункта производства принимается равным нулю.

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

Решение задачи начинается с составления допустимого опорного плана. Допустимое базисное решение (матрица) – опорный план составляется без фиктивного потребителя и должен удовлетворять всем ограничениям.


^ СОСТАВЛЕНИЕ ОПОРНОГО ПЛАНА


Существует ряд способов составления опорного плана (базиса).

Диагональный метод (способ северо-западного угла).

Метод наименьшей стоимости (способ наименьшего значения показателя оптимальности).

Способ двойного предпочтения.

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


1.Диагональный метод.


^ Пункты производства

Пункты потребления

Объем производства

а

б

в

А




2,0




1,8




4,3

20

12

8




Б




3,1




4,2




0,8

17




5

12

В




1,6




2,0




3,5

9







9

^ Объем потребления

12

13

21





Назначение корреспонденции Хij начинают с клетки находящейся слева вверху. Записываем минимальную величину из двух величин поставщика или потребителя.

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

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

^ Заметим, что после записи каждого значения Хij т.е. после заполнения одной из клеток матрицы, исключается из рассмотрения либо строка, либо столбец. Число строк равно числу поставщиков (отправителей), а число столбцов – числу потребителей (получателей). Следовательно, записью каждого очередного максимально возможного значения Хij исключается из рассмотрения, либо поставщик, либо потребитель. Если число корреспонденции равно m+n-1 при числе поставок (m) и числе потребителей (n), то такой вариант плана называется (“базисным”)

F(Xij)=2*12+1,8*8+4,2*5+0,8*12+3,5*9=100,5


2. Метод наименьшей стоимости.

Поставки начинают с клетки с минимальной стоимостью Сij, и все дальнейшие поставки назначают по мере увеличения Cij.

Если на какой-то стадии расчетов оказываются два или несколько клеток с одинаковыми Сij, то поставки назначают в любой из этих клеток в любой последовательности.

Число корреспонденции при этом должно быть равно m+n-1 и соблюдаться ограничения.

В учебных целях в клетках матрицы в кружках показаны цифры порядка ее заполнения корреспонденциями (поставками).


^ Пункты производства

Пункты потребления

Объем производства

а

б

в

А

4

2,0

3

1,8

5

4,3

20

3

13

4

Б




3,1




4,2

1

0,8

17







17

В

2

1,6




2,0




3,5

9

9







^ Объем потребления

12

13

21





В данной матрице опорный план дает следующее значение функции:

F(Xij)=2,0*3+1,8*13+4,3*4+0,8*17+1,6*9=74,6


3. Метод двойного предпочтения.


Последовательность построения опорного плана (базисного решения) заключается в следующем:

Находится минимальное значение Сij в каждом столбце и отмечается «галкой» V значком.

Затем находится Сij минимальное в каждой строке и отмечается также «галкой» V значком.

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

За тем в оставшиеся части матрицы записываем максимально возможные поставки в клетки, отмеченные одним значком (V), и далее во все остальные квадраты, руководствуясь минимальным значением Сij.




^ Пункты производства

Пункты потребления

Объем производства

а

б

в

А




2,0

VV

1,8




4,3

20

3

13

4

Б




3,1




4,2

VV

0,8

17







17

В

VV

1,6




2,0




3,5

9

9







^ Объем потребления

12

13

21






Значение опорного плана F(Xij) получилось следующее:

F(Xij)=2,0*3+1,8*13+4,3*4+0,8*17+1,6*9=74,6


Выражденность матрицы в процессе

составления опорного плана.


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

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

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

Цифры в кружках показывают последовательность заполнения клеток матрицы. Заметим, что давая поставку в клетку А-е (пятая поставка - 20) исключается одновременно и строка и столбец. Эта клетка показывает на выражденность матрицы.



Поставщики

Пункты потребления

^ Объем производства

г

д

е

ж

и

А




6,0




8,5

V

5,5




7,2




6,2

20

0




20 5







Б

20

9,5




7,0




6,5

VV

17

4,3




5,2

37

7







1




В




7,4




5,5




7,0




5,6

VV

21

5,0

24

3 6










3

К


V

5,2

VV

27

4,5

V

13

5,1




7,0




10

40




2

4








^ Объем потребления

23

27

33

17

21





Число занятых клеток оказалось 7 – матрица является выражденной, так как должно быть:

m+n-1=4+5-1=8

Ликвидация вырожденной матрицы достигается за счет введения «фиктивных» корреспонденций с величиной поставки равной нулю, чтобы в итоге число занятых квадратов было бы равно m+n-1.

Нулевая поставка вводится в одну из следующих двух клеток матрицы:

а) В клетку расположенную на пересечении строки, содержащей корреспонденцию включенную в матрицу последней (строка ^ Б), со столбцом в котором появился признак выражденности (столбец е ) клетка Б-е либо,

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

Предпочтение отдается той не заполненной клетке из этих двух (Б-е и А-г), в которой значение стоимости (С) минимально, т.е. используется для назначения нулевой поставки клетка А-г. Ноль (0) считается целочисленным числом.

Далее во всех последующих расчетах «фиктивный» потребитель (клетка заполненная нулем) считается как заполненная целочисленным положительным числом.


Заключение.


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

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

Для определения оптимального решения в матрице существует ряд методов проверки полученных решений.

В данном пособии рассматриваются наиболее простые решения, получившие наибольшее распространение – это распределительный метод и метод потенциалов.


^ РАСПРЕДЕЛИТЕЛЬНЫЙ МЕТОД РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ.

Заключается в последовательном анализе целесообразности изменения намеченных в исходном плане корреспонденций с учетом соблюдения заданных ограничений. В табл. 1 приведено построение опорного плана диагональным способом.

При этом целевая функция примет вид:

F(Xij)=2*40+1*10+4*60+6*15+6*55=750

Построение допустимого плана диагональным способом приведено в табл. 1.


Таблица 1.

^ Пункты производства

Пункты потребления

Объем производства

а

б

в

А

40

2

10



1




5

50










Б




3

60


4




3

60











В




4

15

6

55

6

70









^ Объем потребления

40

85

55





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

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

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

Таблица 2.

^ Пункты производства

Пункты потребления

Объем производства

а

б

в

А

_

2

+

1




5

50

39

11




Б




3




4




3

60

1

+

_59




В




4




6




6

70




15

55

Объем потребления

40

85

55




В матрице (табл. 2) свободных клеток четыре Б-а, В-а, А-в и Б-в.

Начнем с клетки Б-а, и дадим в нее поставку равную единице, тогда в клетках А-а и Б-б поставки уменьшаются на единицу, в клетке А-б, увеличатся на единицу.


Б-а +3

А-а -2

А-б +1 А-а -2 +1 А-б

Б-б -4

-----

-2


Б-а +3 -4 Б-б


Таким образом, давая поставку равную единице в клетку Б-а происходит уменьшение функции на 2, т. е. F(Xij)=748. Показатель можно получить и путем алгебраической суммы характеристик в вершинах цепи. Если в алгебраической сумме получились отрицательные значения, то план не оптимален. Исследуем алгебраически все свободные клетки, перемещая в них поставку равную единице по закону многоугольника цепей. Построение цепей приведено в табл. 1, а именно:

Б-а +3-2+1-4= -2

В-а +4-2+1-6= -3

А-в +5-6+6-1= +4

Б-в +3-6+6-4= -1


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

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


Таблица 3.

^ Пункты производства

Пункты потребления

Объем производства

а

б

в

А

25

2

25



1




5

50










Б




3

60



4





3

60











В

15

4




6

55

6

70










^ Объем потребления

40

85

55




Целевая функция уменьшается и составит на величину

F(Xij)=2*25+1*25+4*60+4*15+6*55=705

(Алгебраическая сумма –3*15= -45)

План поставок допустимый, он лучше прежнего.

Путем построения цепей в матрице табл. 3, выясним, оптимален ли план.

Цепи плана приведены в табл. 3.

Б-а +3-2+1-4= -2

А-в +5-2+4-6= +1

В-б +6-4+2-1= +3

Б-в +3-6+4-2+1-4= -4

Как видно из построения цепей план не оптимален. Назначим поставку (25) в квадрат ^ Б-в. улучшенный план представлен в табл. 4.

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

Таблица 4.

^ Пункты производства

Пункты потребления

Объем производства

а

б

в

А



2

50



1




5

50









Б




3

35




4

25




3

60










В

40

4




6

30

6

70










^ Объем потребления

40

85

55





План не оптимален. В показателях - характеристик клеток, имеется отрицательная величина, клетка В-б.

А-а +2-1+4-3+6-4= +4

А-в +5-3+4-3=+5

Б-а +3-3+6-4=+2

В-б +6-4+3-6= -1

Но целевая функция уменьшена на 100.

F(Xij)=1*50+4*35+3*25+4*40+30*6=605

Поставку даем в клетку В-б.

Строим цепи плана таблица 4.

Поставка составляет величину 30. Новый план представлен в таблице 5.

Таблица 5.

^ Пункты производства

Пункты потребления

Объем производства

а

б

в

А



2

50




1




5

50









Б




3




5




4

55




3

60










В

40

4

30

6




6

70










^ Объем потребления

40

85

55




Целевая функция уменьшилась на (30).

F(Xij)=1*50+4*5+3*55+4*40+6*30=575

Строим цепи

А-а +2-1+6-4=+3

А-в +5-3+4-1=+5

Б-а +3-4+6-4=+1

В-в +6-3+4-6=+1

Построение цепей для всех клеток не дает отрицательных характеристик. Это свидетельствует об оптимальности плана.

Таким образом, при распределительном методе, решение задачи на оптимум состоит из следующих этапов:

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

II этап. Каждой клетке, которой соответствует вершина контура, присваивается знак (минус, плюс). Знаки чередуются.

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

^ ЭКОНОМИЧЕСКАЯ ИНТЕРПРИТАЦИЯ МЕТОДА

ПОТЕНЦИАЛОВ.

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

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

Решение транспортной задачи методом потенциалов (моди).

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

Обозначим потенциалы строк через Ui, потенциалы столбцов через Vi, и показатели стоимости в занятых квадратах через Cij.

Допустимый план считается оптимальным, если каждому поставщику и каждому потребителю соответствуют условия Хij>0 и CijVj-Ui для всех ij

из равенства следует, что потенциал строки Ui=Vj-Cij потенциал столбца Vj= Cij+Ui или Vj=Ui+Cij (условия 1).

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

В примере табл. 1 опорный план составлен диагональным методом.

Таблица 1.

^ Пункты производства

Пункты потребления

Объем пр-ва

Потенц. строк

Ui

а

б

в

А

_

2

+

1




5

50

8

40

10




Б




3




4




3

60

5




60




В

+


4

_

6




6

70

5




15

55

Объем потребления

40

85

55







Потенц. столб. Vj

10

9

9








В матрице (табл. 1), произвольно, назначен потенциал столбца а равным 10. Далее производится расчет потенциалов в соответствии с условиями 1.

После определения потенциалов в строках и столбцах проверяются соблюдения условий (1) для всех остальных свободных клеток.


Порядок безразличен.

Клетка

С

V

U

Формула

Нарушен.

Б-а

3

10

5

310-5

2

В-а

4

10

3

410-3

3

А-в

5

9

8

59-8

-

Б-в

3

9

5

39-5

1


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

В табл. 2 проведены дальнейшие расчеты по определению оптимального варианта перевозок.

Таблица 2.

^ Пункты производства

Пункты потребления

Объем

пр-ва


Потенц. Строк

Ui

а

б

в

А

_

2

+

1




5

50

8

25

25




Б




3

_

4

+

3

60

5




60




В

+

4




6

_

6

70

6

15




55

Объем потребления

40

85

55







Потенц. столб. Vj

10

9

12








Проверяются соблюдения условия (2).

Клетка

С

V

U

Формула

Нарушен.

Б-а

3

10

5

310-5

2

В-а

6

9

6

69-6

-

А-в

5

12

8

512-8

-

Б-в

3

12

5

312-5

4


Наибольшее нарушение в клетке ^ Б-б.

Направляем поставку в клетку Б-в.

Перераспределение поставок приведено в табл. 3.

Таблица 3.

^ Пункты производства

Пункты потребления

Объем

пр-ва


Потенц. строк

Ui

а

б

в

А




2




1




5

50

12




50




Б




3




4




3

60

9




35

25

В




4




6




6

70

6

40




30

Объем потребления

40

85

55







Потенц. столб. Vj

10

13

12








Проверяются соблюдения условия (1).

Клетка

С

V

U

Формула

Нарушен.

А-а

2

10

12

210-12

-

Б-а

3

10

9

310-9

-

В-б

6

13

6

613-6

1

А-в

5

12

12

312-12

-

Нарушение в клетке ^ В-б.

Направляем поставку в клетку В-б.

Перераспределение поставок приведено в табл. 4.

Таблица 4.

^ Пункты производства

Пункты потребления

Объем

пр-ва


Потенц. строк

Ui

а

б

в

А




2




1




5

50

11




50




Б




3




4




3

60

8




5

55

В




4




6




6

70

6

40

30




Объем потребления

40

85

55







Потенц. столб. Vj

10

12

11








Проверяем соблюдения условия (2).


Клетка

С

V

U

Формула

Нарушен.

А-а

2

10

11

210-11

-

Б-а

3

10

8

310-8

-

А-в

5

11

11

511-11

-

В-в

6

11

6

611-6

-


Получен оптимальный вариант, ибо все неравенства удовлетворяют условию CijVj-Ui .

Целевая функция примет вид

F(Xij)=1*50+4*5+3*55+4*40+6*30=575


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

Количество итераций может быть сведено к одной, если принять построение опорного плана методом «наименьших стоимостей».

Замечается, что при всех методах решения задачи на оптимизацию, ответ будет одинаковым.


Исходные данные для выполнения курсовой работы.


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

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

Задача о размещении карьеров является транспортной задачей линейного программирования и решается в матричной форме.

Номер схемы полигона железнодорожной сети, пункты возможного расположения карьеров и участки железнодорожного пути, для которых необходим балласт, технико-экономические показатели каждого карьера (di, Эi, Кi) потребность в балл