91145

Линейная транспортная задача

Лекция

Информатика, кибернетика и программирование

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

Русский

2015-07-13

1012 KB

0 чел.

PAGE  19

 Лекция 3

Линейная транспортная задача.

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

Наиболее часто подобную задачу можно представить матрицей

Если потребитель j  получает единицу продукции (по прямой дороге) со склада i, то возникают издержки Сij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы  k С i j.

Далее, предполагается, что

                                                

где ai есть количество продукции, находящееся на складе i, и bj – потребность потребителя j.

Замечание.  

1. Если сумма  запасов  в  пунктах  отправления  превышает  сумму  поданных  заявок  то количество продукции, равное  остается на складах. В этом случае мы введем "фиктивного" потребителя n +1  с потребностью  и положим транспортные расходы pi,n+1 равными 0 для всех i.

2. Если сумма  поданных  заявок  превышает  наличные  запасы то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным  балансом,  если  ввести  фиктивный пункт отправления m + 1 с  запасом   и стоимость перевозок из  фиктивного  пункта  отправления  во  все  пункты  назначения  принять  равным  нулю.   

Математическая модель транспортной задачи.

где xij количество продукции, поставляемое со склада i потребителю j, а С i j  издержки (стоимость перевозок со склада i потребителю j).

Алгоритм решения транспортной задачи состоит из четырех этапов:

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

Этап 2. Проверка полученного распределения ресурсов на оптимальность. Т.е. общая стоимость перевозки минимальна.

Этап 3. Если полученное распределение ресурсов не является оптимальным, то ресурсы перераспределяются, снижая стоимость транспортировки.

Этап 4. Повторная проверка оптимальности полученного распределения ресурсов.

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

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

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

Метод  северо-западного угла

Условия  транспортной  задачи  заданы транспортной  таблицей.

Будем  заполнять  таблицу  перевозками  постепенно  начиная  с  левой  верхней ячейки ("северо-западного угла" таблицы). Будем  рассуждать  при  этом  следующим  образом. Пункт  В1   подал  заявку    на  18 единиц груза. Удовлетворим эту заявку за счёт запаса 48, имеющегося  в  пункте  А1 , и  запишем  перевозку  18 в  клетке (1,1). После  этого  заявка  пункта  В1  удовлетворена, а  в  пункте  А1  осталось  ещё  30  единиц  груза. Удовлетворим  за  счёт  них  заявку  пункта  В2 (27  единиц), запишем  27  в  клетке (1,2); оставшиеся  3  единицы  пункта  А1  назначим  пункту  В3. В составе  заявки  пункта  В3  остались  неудовлетворёнными  39  единиц.  Из  них  30  покроем  за  счёт  пункта А2, чем  его  запас  будет  исчерпан, и   ещё  9  возьмём  из  пункта  А3. Из  оставшихся  18  единиц  пункта  А3  12  выделим  пункту В4;  оставшиеся  6  единиц  назначим  пункту  В5,  что  вместе  со  всеми  20  единицами  пункта  А4  покроет  его  заявку.  На  этом  распределение  запасов  закончено;  каждый  пункт  назначения   получил  груз,  согласно  своей  заявки. Это  выражается  в  том, что  сумма  перевозок  в  каждой  строке  равна   соответствующему   запасу, а  в  столбце - заявке. Таким  образом, нами  сразу  же  составлен  план  перевозок,  удовлетворяющий  балансовым  условиям. Полученное  решение  является  опорным  решением  транспортной  задачи.

Опорное решение

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

Затраты на реализацию этого плана составят

10*18+8*27+5*3+8*30+10*9+8*12+7*6+8*20=1039

Другой способ - способ построения опорного плана это метод минимальной стоимости.

Метод минимальной стоимости

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

Для разнообразия возьмем другую транспортную матрицу

Шаги алгоритма

1 шаг

2 шаг

3 шаг (Табл. 4)

Оптимизация плана

Для оптимизации этого плана перевозок можно использовать метод потенциалов. С этой целью построим граф перевозок по полученной матрице и определим потенциалы пунктов производства U и пунктов потребления V. Зададим связи между вершинами графа перевозок в соответствии с матрицей табл.4.

Зададимся начальным значением одного из потенциалов производителя (произвольно), а остальные пересчитаем относительно выбранной величины. Пусть U1=100. (А1=100)

Тогда потенциалы V2 V3 V4 будут U плюс стоимость перевозки

U2 и U3 определится как V4 минус стоимость соответствующих перевозок

И соответственно V1 V5 определятся как

Для несуществующих связей (они показаны на графе штриховой линией) рассчитаем соотношение V-UC.

Разумеется, что для существующих в графе связей это соотношение равно нулю

Скажем для существующей связиV2 U1 это

184-100-84 =0

План перевозок оптимален, когда для несуществующих связей выполняется условие V-UC<=0.

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

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

Окончательная матрица оптимальных перевозок выглядит так

Затраты на его реализацию составляют

28*72+37*56+30*46+39*1+43*54+47*41+45*3=9891

По сравнению с первым допустимым планом (11320) затраты уменьшились примерно на 13%

Задача о назначениях

Для задачи о назначениях

Наиболее часто задача о назначениях решается Венгерским методом

Пример

Т.е. Работу А можно выполнить любым из 4–х  инструментов. Первым стоимостью 68 уе, вторым 72 уе третьим 75 уе и четвертым 83 уе.

Алгоритм реализации Венгерского метода

1 этап:

1 Формализация проблемы в виде транспортной таблицы

2 В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки

3 Повторить ту же процедуру для столбцов

Задачей является распределение всех подлежащих назначению единиц в клетки с нулевой стоимостью. Оптимальное значение целевой функции в этом случае равно нулю.

2 этап:

1 Найти строку, содержащую только одно нулевое значение, в его клетку помещается один элемент (0 обводится квадратиком). Если такие строки отсутствуют, допустимо начать с любой строки.

2 Зачеркнуть оставшиеся нулевые значения данного столбца

3 Повторять пп.1-2, пока продолжение указанной процедуры окажется невозможным

Если окажется, что имеется несколько нулей, которым не соответствуют назначения, и которые остались незачеркнутыми, необходимо:

4 Найти столбец, содержащий только одно нулевое значение, в его клетку помещается один элемент.

5 Зачеркнуть оставшиеся нули в данной строке

6 Повторять пп.4-5, пока продолжение указанной процедуры окажется невозможным

Если выяснится, что таблица содержит неучтенные нули - повторить пп. 1-6

Если решение является допустимым, оно оптимально. Если нет - перейти к этапу 3.

3 этап: (Если решение является недопустимым)

1 Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице

2 Найти наименьший из элементов, через которые не проходит ни одна прямая

3 Вычесть его из всех элементов, через которые не проходят прямые

4 Прибавить его ко всем элементам, лежащим на пересечении прямых

5 Элементы, через которые проходит только одна прямая, оставить неизменными

В результате в таблице появится как минимум одно новое нулевое значение. Вернуться к этапу 2 и повторить решение заново.

Нелинейное программирование

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

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

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

  •  квадратичное программирование,
  •  целочисленное программирование,
  •  стохастическое программирование,
  •  динамическое программирование и др.

В задачах квадратичного программирования целевая функция – квадратична, а ограничения – линейны.

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

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

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

Классификация методов нелинейного программирования

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

Однако для решения задачи поиска экстремума классическим методом необходимо задание исходной целевой функции и ее производных n-го порядка что возможно лишь для очень узкого класса задач. Все это приводит к необходимости разрабатывать итерационные процедуры решения задач оптимизации. Это методы: Метод золотого сечения, Метод чисел Фибоначчи, Метод деления пополам, Метод дихотомии и т.п.

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

  •  методы прямого поиска, т.е. методы, в которых при поиске экстремума целевой функции используются только ее значения. Это в частности Метод Гаусса, Метод Хука — Дживса;
  •  градиентные методы первого порядка, в которых при поиске экстремума функции используются значения ее первых производных. Это в частности Метод наискорейшего спуска, Метод покоординатного спуска, Метод сопряжённых градиентов;
  •  градиентные методы второго порядка, в которых при поиске экстремума функции наряду с первыми производными используются и вторые производные. Это в частности Метод Ньютона, Метод Ньютона-Рафсона

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

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

Классический подход к решению задачи поиска экстремума функции одной переменной

Точки минимума и максимума обычно называются точками экстремума

Оптимальность при отсутствии ограничений для случая одной независимой переменной

Для функции одной переменной условия оптимальности формулируются следующим образом.

Необходимое условие локальной оптимальности. Пусть f(x) дифференцируема в точке . Если - точка локального оптимума (экстремума), то

(1.2)

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

Достаточное условие локальной оптимальности. 

Пусть f(x)  k раз, k> 1, дифференцируема в точке  ,причем  

Тогда, если k - четное число, то - точка локального минимума (максимума) при (при ). Если k - нечетное число, то - точка перегиба.

Используя необходимое и достаточное условия оптимальности, находятся точки локальных экстремумов

Пример.

Определить точки локальных и глобальных экстремумов функции f(x) = (1-x)3 и

Решение.

Находим первую производную f(x) :

Вычисляем корни уравнения f '(x) = 0:

Получили одну стационарную точку.,

Определяем характер стационарной точки.

Находим вторую производную f(x) :

Вычисляем значение f"(x)  в точке :

Поскольку характер стационарной точки не определен, то находим третью производную f(x) :

Поскольку порядок k первой необращающейся в нуль в точке x=1 производной есть нечетное число (k=3). то точка х=1 является точкой перегиба ().

Ответ: функция f(x) = (1-x)3  экстремумов не имеет.

График функции

Пример 2. Определить точки локальных и глобальных экстремумов функции .

Решение.

Находим первую производную f(x):

Вычисляем корни уравнения f ’(x) = 0:

Получили одну стационарную точку , .

Определяем характер стационарной точки.

Находим вторую производную f(x):

.

Вычисляем значение f "(х) в точке

.

Поскольку характер стационарной точки не определен, то находим третью производную f (x):

Вычисляем значение f"'(x) в точке :

.

Поскольку характер стационарной точки не определен, то находим четвертую производную f (x):

.

Поскольку порядок k первой необращающейся в нуль в точке х=1 производной есть четное число ( k=4) и то точка x=1 является точкой локального минимума ().

Ответ: функция   имеет в точке х=1 минимум.

График функции

Отметим, что Если требуется заменить задачу минимизации функции f(x1, …, xn) задачей максимизации, то достаточно вместо отыскания максимума этой функции найти минимум функции -f(x1, …, xn). Экстремальные значения этих функций достигаются при одних и тех же значениях переменных Рассмотрим это на примере функции одной переменной (Рис. 2.1). Если х* - точка минимума функции y = f(x), то для функции y =- f(x) она является точкой максимума, так как графики функций f(x) и - f(x), симметричны относительно оси абсцисс. Итак, минимум функции f(x) и максимум функции - f(x) достигаются при одном и том же значении переменной. Минимальное же значение функции f(x), равно максимальному значению функции - f(x), взятому с противоположным знаком, т.е. min f(x) =-max(f(x)).

Классический метод безусловной оптимизации функции многих переменных

Для функции f(x) многих переменных точка х представляет собой вектор, f'(x) - вектор первых производных (градиент) функции f(x), f " (x) - симметричную матрицу вторых частных производных (матрицу Гессе - гессиан) функции f(x).

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

Необходимое условие локальной оптимальности. Пусть f(x) дифференцируема в точке . Если - точка локального экстремума, то

. (1.3)

Как и ранее, точки, являющиеся решениями системы уравнений (1.3), называются стационарными. Характер стационарной точки  связан со знакоопределенностью матрицы Гессе .

Достаточное условие локальной оптимальности. Пусть F(x) дважды дифференцируема в точке , причем F'(x*)=0. т.е. x* - стационарная точка. Тогда, если матрица F"(x*) является положительно (отрицательно) определенной, то x* - точка локального минимума (максимума); если матрица F"(x*) является неопределенной, то x* - седловая точка.

Если матрица F"(x*) является неотрицательно (неположительно) определенной, то для определения характера стационарной точки x* требуется исследование производных более высокого порядка.

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

Пример. Определить точки локальных экстремумов функции

.

Решение.

Находим первые частные производные F(x):

.

Решаем систему уравнений

Разрешаем уравнение (2) относительно

Подставляя полученное выражение в уравнение (1). Находим .

Соответственно

.

Таким образом, получили две стационарные точки (N = 2):

.

Находим вторые частные производные F(x):

Составляем матрицу Гессе

.

Дальнейшее рассмотрение будем вести для одной стационарной точки – Х2

Находим :

Вычисляем угловые миноры :

M1=|10|>0,

Поскольку все углы миноры ненулеые, то характер  определяется с помощью F”(x).

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

Ответ: функция  имеет в точке x=(5/3,8/3) локальный минимум.

+++++++++++++++++++++

Тел 89050159143


 

А также другие работы, которые могут Вас заинтересовать

38660. Реорганизация беспроводного сегмента сети ТНУ для обеспечения максимальной надежности, удобства использования и обслуживания 11.94 MB
  Локальные компьютерные сети получили своё развитие в 70х годах ХХ века и продолжают развиваться. Общеобразовательные сети на примере локальной вычислительной сети Таврического Национального Университета обязаны иметь надежный и стабильный доступ к глобальной сети для обеспечения полноценного высококвалифицированного образования. Наличие беспроводного доступа к локальным ресурсам и глобальной сети является конкурентоспособным преимуществом ВУЗа позволяя равномерно распределить доступ к сети между учащимися тем самым уменьшить загруженность...
38661. Избранные комбинаторные задачи 1.46 MB
  Сколькими способами они могут занять очередь Решение Метод перебора: ДАК ДКА АДК АКД КДА КАД. Дерево возможных вариантов: Ответ: 6 способами. Правило суммы: Если объект А может быть выбран n способами а объект В m способами то выбор объектов А или В может быть осуществлён m n способами. Правило произведения: Если объект А может быть выбран n способами и при каждом способе выбора объекта А объект В может быть выбран m способами то выбор объектов А и В можно произвести m ∙ n способами.
38662. Управление кредитным портфелем ОАО «Автовазбанк» (ОАО Банк АВБ) 1.08 MB
  Методы управления кредитным портфелем банка. Формирование кредитного портфеля является одним из основополагающих моментов в деятельности банка позволяющим более четко выработать тактику и стратегию развития коммерческого банка его возможности кредитования клиентов и развития деловой активности на рынке. Кредитный портфель служит главным источником доходов банка и одновременно – главным источником риска при размещении активов. От структуры и качества кредитного портфеля в значительной степени зависит...
38663. Анализ себестоимости продукции в СХПК «Элита» и резервы ее снижения 1.49 MB
  Экономическая сущность себестоимости продукции предприятия.1 Понятие виды состав и значение себестоимости продукции.3 Методы учета затрат и калькулирования себестоимости продукции. Анализ себестоимости продукции в СХПК Элита и резервы ее снижения.
38664. Эколого-фаунистическая характеристика пресноводных моллюсков разнотипных водоемов Волгоградской области 8.81 MB
  Малакологические данные используются также в целях стратиграфии – раковины моллюсков относительно неплохо сохраняются в отложениях и во многих случаях являются руководящими ископаемыми. Все эти обстоятельства обусловливают большой интерес к пресноводным моллюскам специалистов разных областей знания.
38665. Комплекс автоматизированных задач по управлению персоналом и их реализация на ПЭВМ для ОАО «Московское Речное Пароходство» 2.48 MB
  3 Анализ существующей системы управления. Управление персоналом должно все меньше основываться на административных методах и все в большей степени ориентироваться на осознанную кадровую политику базирующуюся на системе интересов государственного служащего и органов государственного управления. Поэтому необходимы новейшие научные знания и эффективные технологии в области управления человеческими ресурсами методы формирования и управления трудовым коллективом освоение инновационных технологий работы с кадрами. Нужны новые подходы к таким...
38666. Возведение одноэтажного административно-хозяйственного здания для Центра Детского Творчества в г.Уфа 1.43 MB
  Выбор методов производства работ основных машин и механизмов 2.4 Определение номенклатуры и подсчет объемов работ Бахолдина Н.2 Ведомость номенклатуры и подсчета объемов работ 2.5 Выбор методов производства работ и механизмов 2.
38668. ДИСКУРС ОБ АВТОРСТВЕ В ПОСТСОВЕТСКОЙ КИНОКРИТИКЕ НА ПРИМЕРЕ ДЭВИДА ЛИНЧА 910.5 KB
  вторский кинематограф остается на сегодняшний день закрытым для многих, чьи потребности уже вышли за рамки развлекательного кино отчасти из-за непонимания сложившегося в мире киноязыка, отчасти из-за бессилия кинокритики в доступной и объективной форме интерпретировать произведения. К авторскому кинематографу сформировалось отношение как к чему-то субъективному и непознаваемому по своей природе.