Дипломная работа: Построение эффективной схемы взаимоотношений с поставщиками на примере ООО «ТИТАН»
Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам
26
экономико-математического моделирования состоит в его объективности –
например, экспертные методы в своей основе субъективны. К основным
методам и моделям, которые будут рассмотрены, относятся транспортная
задача линейного программирования, корреляционный анализ и модель
сетевого планирования. Рассмотрим каждый метод подробно:
Классическая транспортная задача линейного программирования
формулируется следующим образом [27, С. 115].
Имеется m пунктов производства (поставщиков) и n пунктов потребления
(потребителей) однородного продукта. Заданы величины:
Ai- объем производства(запас) i-го поставщика i=1...m
Bj- объем потребления(спрос) j-го потребителя j=1...n
Cij- стоимость перевозки(транспортные затраты) единицы продукции от
i-го поставщика j-му потребителю.
Требуется составить такой план перевозок, при котором спрос всех
потребителей был бы выполнен и при этом общая стоимость всех перевозок
была бы минимальна.
Целевая функция транспортной задачи имеет вид (1):
(1)
при ограничениях (2):
????
????
Таким образом, транспортная задача решает распределение грузов
потребителям с использованием имеющихся на складах запасов таким образом,
чтобы совокупные транспортные расходы были бы минимальными.
27
Основным источником информации для решения транспортной задачи
является ее таблица [27, С. 16]:
Таблица 1
Таблица транспортной задачи
Склад 1
Склад 2
….
Склад i
Запасы/потребности
Х1
Х2
….
Хi
Поставщик 1
Y1
C11
C12
….
C1i
Поставщик 2
Y2
C21
C22
….
C2i
….
….
….
….
….
…..
Поставщик n
Yj
Сj1
Cj2
….
Cji
Транспортная задача, в которой суммарные запасы и суммарные
потребности совпадают, называется закрытой моделью, в противном случае
открытой моделью. Открытая модель решается приведением к закрытой
модели.
В случае, когда суммарные запасы превышают суммарные потребности,
вводится фиктивный n+1 потребитель, потребности которого равны разности
между суммарными запасами и суммарными потребностями. Когда наоборот,
суммарные потребности превышают суммарные запасы, вводится m+1
поставщик.
Стоимость перевозки груза, как до фиктивного потребителя, так и от
фиктивного поставщика принимается равной 0, так как груз в обоих случаях не
перевозится.
Можно выделить основные свойства транспортной задачи:
1) коэффициенты целевой функции неотрицательны (стоимость не может
быть отрицательной величиной)
2) коэффициенты правых частей ограничений неотрицательны (запасы и
потребности продукта)
3) коэффиценты в ограничениях принимают только два значения - 0 или
1.
28
В силу этих особенностей можно сформулировать 2 теоремы.
- Базисное решение закрытой модели транспортной задачи содержит
m+n-1 базисных компонент.
- В силу специфики содержательной постановки транспортной задачи
допустимое решение называется планом, базисное допустимое решение
называется опорным планом, оптимальное решение называется оптимальным
планом. Оптимальный план закрытой модели транспортной задачи существует
всегда.
Базисными клетками транспортной задачи являются клетки с отличными
от 0 положительными перевозками, остальные клетки свободные (см. таблицу
1). Базисные клетки образуют опорный план транспортной задачи, если
выполняются 2 условия:
1) сумма перевозок в каждой строке равна запасу Ai в данной строке.
2) сумма перевозок в каждом столбце равна соответствующему столбцу
спроса Bj.
Опорный план транспортной задачи содержит не более n+m-1 отличных
от 0 перевозок Xij.
Опорный план транспортной задачи называется вырожденным, если
число ненулевых перевозок меньше n+m-1, и невырожденным в случае если
число ненулевых перевозок равно n+m-1. Вообще опорный план представляет
собой промежуточное решение транспортной задачи – то есть обеспечивает
удовлетворение запроса потребителей имеющимися поставщиками. Однако, не
каждый опорный план является оптимальным, то есть обеспечивающим
минимальную стоимость перевозок.
Рассмотрим северо-западный угол транспортной таблицы 1. Это
незаполненная клетка, соответствующая первому поставщику и первому
29
потребителю. Метод северо-западного угла по нахождению опорного плана
получил свое название благодаря тому, что если в таблице обозначить углы
сторонами света, то левый верхний угол будет соответствовать северо-западной
стороне. Возможны три случая:
1) Если A1<B1, то X11=A1. Это означает, что первый поставщик отгрузил
весь произведенный продукт первому потребителю и его запас равен 0, поэтому
X12=X13=...=X1n=0. При этом неудовлетворенный спрос в первом пункте
потребления равен B1*=B1-A1.
2) Если A1>B1, то X11=B1, то есть спрос первого потребителя полностью
удовлетворен и поэтому X21=X31=...=Xm1=0, а остаток продукта в первом
пункте производства равен A1*=A1-B1.
3) В случае А1=В1 из рассмотрения можно исключать и поставщика, и
потребителя. Однако при этом план получается вырожденным, поэтому
считается что из рассмотрения выбывает только поставщик X12=X13=...X1n=0,
а спрос потребителя остается неудовлетворенным и равным 0.
После этого рассматриваем северо-западный угол оставшейся
незаполненной таблицы и повторяем действия из п.1-3. В результате через n+m-
1 шагов получаем опорный план транспортной задачи.
Метод потенциалов- наиболее распространенный метод решения
транспортной задачи. Для того, чтобы перейти к алгоритму метода потенциалов
введем следующие определения:
Циклом в транспортной таблице называется несколько клеток,
соединенных замкнутой ломаной линией, которая в каждой клетке совершает
поворот на 90. Знаком " + " отмечают те вершины, в которых перевозки
увеличиваются, а знаком "-" - те вершины, в которых перевозки уменьшаются.
Перемещение какого-то количества единиц груза по циклу означает увеличение
перевозок на это количество единиц в положительных вершинах и уменьшение
30
перевозок на это же количество единиц в отрицательных вершинах. При этом,
если перевозки остаются неотрицательными, план остается допустимым.
Стоимость плана при этом может меняться.
Ценой цикла называется увеличение стоимости перевозок при
перемещении единицы груза по этому циклу. Очевидно, цена цикла равна
алгебраической сумме стоимостей, стоящих в вершинах цикла, при этом
стоимости в положительных вершинах берутся со знаком " +", а стоимости в
отрицательных вершинах берутся со знаком " - ".
Идея метода потенциалов состоит в следующем. Для любой свободной
клетки транспортной таблицы всегда существует единственный цикл,
положительная вершина которого лежит в этой свободной клетке, а все
остальные - в базисных. Если цена такого цикла отрицательна, то план можно
улучшить перемещением перевозок по данному циклу. Количество единиц
груза, которое можно переместить, определяется минимальным значением
перевозок, стоящих в отрицательных вершинах цикла (если переместить
большее число единиц груза, возникнут отрицательные перевозки). Если
циклов с отрицательной ценой нет, то это означает, что дальнейшее улучшение
плана невозможно, т.е. оптимальный план найден.
Для нахождения циклов с отрицательной ценой вводится система
платежей
Qi, i=1...m, Wj, j=1...n. Определяются величины Cij*=Qi+Wj, называемые
псевдостоимостями. При этом цена цикла пересчета для каждой свободной
клетки равна Cij-Cij*, если платежи Qi и Wj определять из условий Ai+Bj=Cij
для всех базисных клеток (I,j).
Метод потенциалов состоит в следующем:
1-й шаг. Строится опорный план транспортной задачи методом северо-
западного угла с n+m-1 базисными клетками.
Источник: https://baza.diplomsite.ru/previewfile/1023