рефераты конспекты курсовые дипломные лекции шпоры

Раздел Науковедение
/
Решение транспортной задачи методом потенциалов

Реферат Курсовая Конспект

Выберите учебное заведение

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

Решение транспортной задачи методом потенциалов - раздел Науковедение, Дисциплин ОСНОВЫ СИСТЕМНОГО АНАЛИЗА Для Решения Транспортной Задачи Используют Метод Потенциалов...

Для решения транспортной задачи используют метод потенциалов (модифицированный распределительный метод).

Потенциалами называются числа u_í и v_j, удовлетворяющие следующим условиям оптимальности плана перевозок.

1) Для всех занятых клеток (x_ij > 0) должно выполняться равенство

v_j – u_i = c_ij.

2) Для всех свободных клеток (x_ij = 0) справедливо соотношение v_j – u_i≤ c_ij.

Здесь u_i – потенциал i-й строки,

v_j – потенциал j-го столбца.

Для определения потенциалов составляют систему m+n–1 линейно независимых уравнений с количеством неизвестных m + n. Так как уравнений на одно меньше, чем неизвестных, то система неопределенна и имеет бесконечное множество решений. Поэтому одно неизвестное определяют произвольно. Обычно полагают u₁ = 0. Тогда можно определить все остальные значения потенциалов.

Характеристикой или оценкой свободной клетки (i, j) называют величину w_ij, которая определяется по формуле:

w_ij = c_ij – (v_j – u_i).

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

w_ij = 0, если (i, j) – занятая клетка;

w_ij ≥ 0, если (i, j) – свободная клетка,

то план перевозок является оптимальным.

Если хотя бы одна свободная клетка имеет отрицательную оценку (при условии, что все базисные оценки равны нулю), то рассматриваемый опорный план не является оптимальным. Он может быть улучшен путем введения клетки с наибольшей по абсолютной величине отрицательной оценкой в состав базисных клеток. Такая клетка называется перспективной и обозначается (i, j)^*.

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

w_ij ≤ 0.

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

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Дисциплин ОСНОВЫ СИСТЕМНОГО АНАЛИЗА

ЛУГАНСКИЙ НАЦИОНАЛЬНЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ... Кафедра физико математических дисциплин...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Решение транспортной задачи методом потенциалов

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ
Контрольную работу необходимо выполнить в отдельной ученической тетради, на внешней обложке которой необходимо указать изучаемую дисциплину, номер академгруппы, фамилию и инициалы с

Решаемой графическим методом
Пусть дана задача линейного программирования (ЗЛП) с целевой функцией z = c1x1 + c2x2 и ограничениям

Симплексным методом
Решение ЗЛП графическим методом является наглядным и удобным в случае двух переменных. Для случая большего числа переменных графический метод становится невозможным. В этом случае применяют аналити

Алгоритм симплекс-метода
Пусть рассматриваемая ЗЛП решается на нахождение максимума целевой функции. Алгоритм симплекс-метода состоит в выполнении следующих шагов. 1. Составить первую симп

Решение.
Составим математическую модель задачи. Обозначим x1, x2, x3 соответственно количество изделий видов А, В, С.

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

Формализация распределительной задачи
Транспортной (распределительной) задачей называется задача определения оптимального плана перевозок груза из заданных пунктов отправления в заданные пункты п

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

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

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