Транспортная задача. Правило «Северо-западного угла». Правило «Минимально элемента». Метод потенциалов.

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

Имеется m пунктов производства, в каждом из которых сосредоточено   единиц продукции. Эту продукцию нужно доставить n потребителям, где потребность составляет n единиц. Причем Известны величины  — затраты на перевозку единицы продукции из i-гo пункта производства j-й пункт потребления. Матрица C называется матрицей времени , x- матрицей перевозок.

Мат. модель тз : целевая ф-ия,описыв. транспортные затраты

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

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

Процесс решения ТЗ:

1 построить начальное решение по одному из правил

2 вычислить потенциал поставщиков и потребителей

3 вычислить оценку

Правило «Минимально элемента».

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

Имеется m пунктов производства, в каждом из которых сосредоточено   единиц продукции. Эту продукцию нужно доставить n потребителям, где потребность составляет n единиц. Причем Известны величины  — затраты на перевозку единицы продукции из i-гo пункта производства j-й пункт потребления. Матрица C называется матрицей времени , x- матрицей перевозок.

Мат. модель тз : целевая ф-ия,описыв. транспортные затраты

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

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

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

Процесс решения ТЗ:

1 построить начальное решение по одному из правил

2 вычислить потенциал поставщиков и потребителей

3 вычислить оценку

Метод потенциалов.

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

Имеется m пунктов производства, в каждом из которых сосредоточено   единиц продукции. Эту продукцию нужно доставить n потребителям, где потребность составляет n единиц. Причем Известны величины  — затраты на перевозку единицы продукции из i-гo пункта производства j-й пункт потребления. Матрица C называется матрицей времени , x- матрицей перевозок.

Мат. модель тз : целевая ф-ия,описыв. транспортные затраты

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

Метод потенциалов.Каждому поставщику поставили в соответствие число.Числа -эти числа наз. потенциальными и для каждой клетки должны удовлетворять условию Для нахождения частного решения одному из потенциалов придается произвольное числовое значение.Обычно =0.Тогда все потенциалы определяются однозначно.Если для всех клеток выполняется условие   ,то решение является оптимальным.В рез-те перемещения груза по циклу получается новое базисное решение(наход оптим знач-ие кол-во прод-ии и как грамотно перевезти потребителю этот груз)

Процесс решения ТЗ:

1 построить начальное решение по одному из правил

2 вычислить потенциал поставщиков и потребителей

3 вычислить оценку