Метод линейного программирования

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Оглавление

Введение

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

2. Венгерский метод решения

3. Алгоритм

4. Пример

Список литературы

Введение

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

Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:

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

задача о смесях (планирование состава продукции);

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

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

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

В общем виде математическая модель задачи записывается следующим образом:

Целевая функция:

линейное программирование функция

Ограничения:

Требование неотрицательности:

,

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

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

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

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

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

Классическая постановка транспортной задачи общего вида такова.

Имеется m пунктов отправления («поставщиков») и n пунктов потребления («потребителей») некоторого одинакового товара. Для каждого пункта определены:

ai- объемы производства i -го поставщика, i = 1, …, m;

bj - спрос j-го потребителя, j= 1,…,n;

сij - стоимость перевозки одной единицы продукции из пункта Ai- i-го поставщика, в пункт Вj - j-го потребителя.

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

Под планом перевозок понимают объем перевозок, т.е. количество товара, которое необходимо перевезти от i-го поставщика к j-му потребителю. Для построения математической модели задачи необходимо ввести m·n штук переменных хij, i= 1,…, n, j= 1, …, m, каждая переменная хij обозначает объем перевозок из пункта Ai в пункт Вj. Набор переменных X = {xij} и будет планом, который необходимо найти, исходя из постановки задачи.

Ограничения задачи примут вид:

(1)

Либо:

(2)

Это условия для решения открытых транспортных задач.

Очевидно, что для разрешимости задачи (1) необходимо, чтобы суммарный спрос не превышал объема производства у поставщиков:

А для разрешимости задачи (2) необходимо обратное условие:

Если эти неравенства выполняются строго, то задача называется «открытой» или «несбалансированной», если же

то задача называется «закрытой» транспортной задачей, и будет иметь вид (3):

(3)

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

Для построения начального решения транспортной задачи применяются следующие методы:

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

метод наименьшей стоимости (метод минимального элемента);

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

Венгерский метод решения

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

Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины 0/2 (0-суммарная невязка подготовительного этапа).

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

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

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

Алгоритм

Алгоритм основан на двух идеях:

если из всех элементов некой строки или столбца вычесть одно и то же число y {\displaystyle y} y, общая стоимость уменьшится на y {\displaystyle y} y, а оптимальное решение не изменится;

если есть решение нулевой стоимости, оно оптимально.

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

Венгерский метод обоснован тремя теоремами. Первая из них - теорема Кенинга.

Теорема Кенинга

Если элементы матрицы С разделить на два класса, то минимальное число линий, содержащие все такие элементы равно максимальному числу элементов с этим свойством, которые не лежат на одной прямой.

Эта теорема обосновывает, что в контексте решения после выполнения третьего шага алгоритма, матрица остается эквивалентной.

Теорема

Если набор Х минимизирует функцию

,

по всем то функционал

, где

так же минимизируется Х.

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

Теорема

Если все и можно отыскать набор такой, что , = 0, то это решение оптимально.

Эта теорема обосновывает оптимальность полученного решения.

Если описывать алгоритм наиболее понятным образом, то он выглядит так:

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

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

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

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

Пример

Венгерский метод.

Имеется три поставщика и четыре потребителя. Поставщики имеют запасы А=(11, 11, 8), а потребители - потребность В=(5, 9, 9, 7). () Затраты по перевозкам выражаются следующей матрицей С:

Решение:

Шаг 1. Преобразуем матрицу стоимостей, вычитая из элементов каждой строки минимальный элемент этой строки

В первой строке минимальный элемент -3, во второй - 2, в третьей -1

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

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

Шаг 2. Попробуем распределить перевозки:

Перевозки по нулевым клеткам распределить не выходит. Например, ноль в первой строке и четвертом столбце должен одновременно «перевозить» 7 и 11 единиц товара.

Шаг 3Вычеркиваем вторую и третью строки и четвертый столбец (так все нули окажутся зачеркнутыми). Минимальный из оставшихся элементов - 2.

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

Шаг 2. Снова пробуем распределить перевозки:

В этот раз сделать это удается:

Сопоставим исходную матрицу стоимостей с объемом перевозок и найдем их общую стоимость:

F = 2*5+4*6+3*3+5*4+1*5+3*7=89

План перевозок:

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

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

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

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

X=

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

S=8·3+5·1+3·7+2·5+4·6+1·8=92

Проверяем полученный опорный план на оптимальность. Вычислим потенциалы ui + vj = ci, принимая u1=0

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых?ij= ui - vj- cij> 0, например ?32 = -4 + 8 - 3 = 1 > 0. Это максимальное положительное значение.

Выделим цикл и расставим чередующиеся «+» и «-».

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

Проверим оптимальность опорного плана. Вычислим потенциалы.

Этот опорный план является оптимальным, так как все ?ij<0.

План перевозок:

Общая стоимость: F(x) = 5*4 + 3*7 + 2*5 + 4*6 + 3*3 + 1*5 = 89

Список литературы

1. А.Г. Сухарев, А.В. Тимохов, В.В. Федоров. Курс методов оптимизации.

2. https://ru.wikipedia.org

3. https://studfiles.net

4. https://studopedia.ru

Размещено на Allbest.ru