🗊Презентация Распределительный метод линейного программирования

МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПО ЗЕМЛЕУСТРОЙСТВУ» Факультет Заочный Направление 38.03.02 «Менеджмент» Кафедра Землеустройства Дисциплина «Математические методы в экономике» Лекция 2. Распределительный метод линейного программирования Лектор: доцент кафедры землеустройства, к.э.н. Сорокина Ольга Анатольевна

План лекции Понятие линейного программирования. Землеустроительные задачи, решаемые методами линейного программирования. Понятие и сущность транспортной задачи Отличительные особенности распределительных задач линейного программирования. Базовая модель задачи, решаемой распределительным методом Допустимое и оптимальное решения распределительных задач Методы составления первого опорного плана (решения) Алгоритм метода минимального элемента Алгоритм метода максимального элемента Алгоритм метода аппроксимации на min Алгоритм метода аппроксимации на max

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

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

3. Понятие и сущность транспортной задачи Постановка задачи: Имеется m поставщиков с запасом Ai (i=1, 2, ...m); i - номер поставщика; И n – потребителей с потребностями грузов Вj (j= 1, 2, ...n); j – номер потребителя; индексы i, m принадлежат строке; j, n – столбцу. Известна стоимость перевозки единицы груза по каждому возможному маршруту сij из i-го пункта отправления в j-ый пункт назначения. Требуется определить такие оптимальные маршруты поставок xij от i-го поставщика к j-му потребителю (т.е. такой план перевозок), чтобы значение целевой функции достигало своего экстремума (min, max). xij – объем груза, перевозимого из i-го пункта отправления в j-ый пункт назначения.

3. Понятие и сущность транспортной задачи. Табличная форма записи исходных данных транспортной задачи

4. Отличительные особенности распределительных задач линейного программирования. Все условия задачи (ограничения) представлены в виде уравнений. Все переменные в выражаются в одних и тех же единицах измерения (га, км, руб, ц и т. д.). Все коэффициенты при переменных в ограничениях модели всегда равны единице. Каждая переменная входит только в два ограничения: в ограничение по строке и в ограничение по столбцу.

5. Базовая модель задачи, решаемой распределительным методом Экономико-математическая модель состоит из трех составных частей: 1.    целевая функция; 2.    система ограничений; 3.    неотрицательность переменных. Структурная запись I. Целевая функция:              Развернутая запись , где cij — стоимость перевозки единицы груза из I -го пункта отправления в j-ый пункт назначения.

II. Система ограничений Ограничения по строкам Количество перевозимых грузов из i-го пункта отправления в j-ые пункты назначения равно запасу i-го пункта отправления. Структурная запись Развернутая запись x11+x12+x1j+…+x1n=A1 x21+x22+x2j+…+x2n=A2 xi1+xi2+xij+…+xin=Ai xm1+xm2+xmj+…+xmn=Am

Количество перевозимых грузов из i-х пунктов отправления в j-ый пункт назначения должно равняться потребности в j-м пункте назначения. Ограничения по столбцам Структурная запись Развернутая запись

Балансовое условие: Количество распределяемых грузов и потребности в них должны быть равны: Структурная запись Развернутая запись: A1+A2+…+Am=B1+B2+…+Bn,, если модель задачи закрытая; если модель задачи открытая

Для решения задачи открытую модель приводят к закрытому виду путем введения фиктивного пункта отправления с запасом, равным: или фиктивного пункта назначения с потребностью, равной: Стоимость перевозок грузов по фиктивному пункту принимают равными «0».

При расчете разностей к фиктивные элементы (столбец или строка) участвуют в последнюю очередь.  III. Условие неотрицательности переменных Xij ≥0

6. Допустимое и оптимальное решения распределительной задачи Допустимое решение – это такая совокупность значений переменных Xij, которая удовлетворяет всем поставленным в задаче ограничениям. Оптимальное решение – допустимое решение, приводящее к экстремуму (минимуму/максимуму) значение целевой функции.

7. Методы составления первого опорного плана (решения) 1. Метод северо-западного угла. 2. Метод наилучшего элемента (минимального, максимального в зависимости от критерия оптимизации). 3. Метод аппроксимации. Любой из методов позволяет найти опорное решение, но они различаются по количеству итераций, которые необходимо осуществить, и по степени близости базисного решения к оптимальному.

8. Алгоритм метода минимального элемента На каждом шаге алгоритма поиска опорного решения стараются занять максимально возможным ресурсом прежде всего те клетки транспортной таблицы, в которых стоят наименьшие величины Cij. Из всех оценок Cij в таблице выбирают наименьшее. В соответствующую клетку записывают значение Xij, равное наименьшему из соответствующих величин Ai, Bj. Определяют новые значения величин Ai, Bj. Если запас груза Ai равен нулю а потребность в грузе Bj больше нуля, то из таблицы вычеркивают соответствующую строку. Если Bj равен нулю, то вычеркивают столбец. Если обе величины Ai, Bj равны нулю, то вычеркивают только строку или только столбец. С оставшимся элементом далее работают как обычно. Далее указанные операции повторяются до тех пор пока все ресурсы не будут распределены по клеткам.

8. Алгоритм метода минимального элемента Полученное решение необходимо проверить по числу занятых клеток их должно быть m + n – 1. Если число занятых клеток равно этому условию, то такое решение называется невырожденным, если число занятых клеток меньше, то это решение вырождено. Вырожденность можно преодолеть. Если число занятых клеток больше, то нужно искать ошибку в решении. Также проверяем сходится ли сумма по строке с запасами груза Ai, и сумма по столбцу с Bj. Далее считаем целевую функцию.

9. Алгоритм метода максимального элемента При решении задачи на максимум приведенный алгоритм меняется только в первом шаге: вместо минимального значения Cij находят максимальное и далее работают с соответствующей клеткой.

10. Алгоритм метода аппроксимации на min На каждом шаге выбор, очередной клетки, заполняемой ресурсом, осуществляется не на основе строго локальных оценок стоимостей Cij, как в методе минимального элемента, а на основе разностей между оценками. Это позволяет приближенно оценивать полезность данного шага с точки зрения скорейшего приближения к оптимальному решению. по каждому столбцу и строке находят 2 минимальных значения Cij. определяют их разности µi для строк и µj для столбцов. из всех разностей выбирают наибольшую µmax. по строке или столбцу, к которым относится µmax, в клетку где размещается наименьшее значение Cij, записывают значение Xij равное наименьшей из соответствующих величин Ai Bj.

10.Алгоритм метода аппроксимации на min Если запас груза Ai равен нулю а потребность в грузе Bj больше нуля, то из таблицы вычеркивают соответствующую строку. Если Bj равен нулю, то вычеркивают столбец. Если обе величины Ai, Bj равны нулю, то вычеркивают только строку или только столбец. С оставшимся элементом далее работают как обычно. далее указанные операции повторяются до тех пор пока все ресурсы не будут распределены по клеткам. Полученное решение необходимо проверить по числу занятых клеток их должно быть m + n –1. проверяем сходится ли сумма по строке с запасами груза Ai, и сумма по столбцу с Bj. Далее считаем целевую функцию.

10. Алгоритм метода аппроксимации на min При реализации данного алгоритма возможны некоторые особенности: Величины разностей могут иметь одинаковое наибольшее значение. В этом случае нужно брать ту разность для которой в соответствующих столбцах или строках находится наименьшее значение Cij. Если таких Cij несколько то для решения берут ту клетку, которую можно заполнить наибольшим значением Xij. В случае если выбывают 2 элемента необходимо выбрать какой выгоднее вычеркнуть. Для этого по рассматриваемым строке и столбцу выбираем наименьшее значение Cij и вычеркиваем тот элемент, где Cij больше.

11. Алгоритм метода аппроксимации на max При решении задач на максимум приведенный алгоритм меняется в двух пунктах: 1. вместо двух минимальных находят 2 максимальных значения Cij, 4. заполняют клетку грузом с наибольшим значением Cij.

1. Проверка опорного решения на оптимальность методом потенциалов После получения первоначального опорного плана необходимо проверить его на оптимальность. Для определения оптимальности плана используются потенциалы, которые вычисляются по занятым клеткам, по следующим формулам:  i + c ij = j,  i =j- c ij где  i – потенциалы по строкам; j - потенциалы по столбцам. За первый потенциал берется любое число. Чтобы потенциалы были только положительными, необходимо первый потенциал взять чуть больше наибольшей оценки C ij по матрице.

Условие оптимальности План является оптимальным, если для свободных клеток: при решении задач на min:  i +c ij  j , или ij  0 на max:

2. Улучшение опорного плана методом построения улучшающего многоугольника Если условие оптимальности выполняется для всех клеток, то план оптимален. Если условие не выполняется, необходимо провести улучшение плана методом построения улучшающего многоугольника. Начинаем строить улучшающий многоугольник для свободной клетки, в которой характеристика максимальна по модулю. Из отрицательных вершин выбираем наименьшее значение и перемещаем его по вершинам многоугольника. Правила построения улучшающего многоугольника: Строится многоугольник для свободной неотрицательной клетки. Вершины многоугольника должны находиться в занятых клетках, кроме одной начальной, лежащей в испытуемой свободной клетке. Шагать можно по занятым клеткам с поворотом под прямым углом. Стороны многоугольника должны быть параллельны строкам и столбцам матрицы. Знаки присваиваются «+» вершине в свободной клетке; и далее знаки чередуются «-» «+» «-».

Контроль вычислений: После каждого улучшения значение целевой функции должно увеличиваться или уменьшаться (в зависимости критерия оптимизации). Значение целевой функции для контроля, начиная со 2-ой итерации, вычисляют по формуле

3. Несбалансированные задачи Балансовое условие: Количество распределяемых грузов и потребности в них должны быть равны: Структурная запись Развернутая запись: A1+A2+…+Am=B1+B2+…+Bn,, если модель задачи закрытая; если модель задачи открытая

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

4. Задачи с дополнительными ограничениями Дополнительные ограничения типа , причем ,иначе ограничение теряет смысл. Для учета этого ограничения необходимо определить измененные объемы производства и потребления Дальнейший алгоритм действий зависит от конкретных числовых значений рассматриваемых величин и Если оказалось, что то соответствующая строка вычеркивается из таблицы. Аналогично, если то соответствующий столбец вычеркивается из таблицы. Если и и , то из таблицы вычеркиваются и столбец и строка и далее задача решается по намеченному алгоритму.

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

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

Определение опорного решения задачи методом аппроксимации Формализация исходных данных задачи: Введем следующие обозначения: — площадь, которую может обследовать бригада, м2; — площадь объектов недвижимости, м2; — номер бригады: — номер объекта: норма прибыли от обследования – й бригадой -ого объекта недвижимости, руб./ м2; площадь обследования – й бригадой -ого объекта недвижимости, м2; — площадь, которую могут обследовать все бригады фирмы, м2; — площадь объектов недвижимости, м2; — прибыль фирмы, руб.

Запись задачи транспортного типа в структурной форме: Целевая функция: Распределить бригады по землепользованиям объектов так, чтобы прибыль организации от проведения обследований была максимальной. Ограничения по строкам: Сумма производимых работ i –той бригады на j –х объектах должна быть равна площади, которую может обследовать данная бригада: Ограничения по столбцам: Сумма объемов работ на j –ом объекте недвижимости проводимых всеми бригадами должна быть равна площади данного объекта: Балансовое условие: Площадь объемов работ, которые могут выполнить бригады, должна быть равна общей площади объектов недвижимости. Условие неотрицательности переменных:

Проверка сбалансированности задачи

Проверка сбалансированности задачи , задача не сбалансирована, причем Чтобы привести задачу к сбалансированному виду, вводим фиктивную строку с площадью, равной = 2460. Чтобы значение целевой функции не изменилось, оценки по фиктивной строке примем равными нулю С7i=0, i=1,2,3,4,5,6,7. В результате исходная таблица примет вид.

Проверка сбалансированности задачи

Запись ЭММ в расширенном виде 1. Граничные условия а) по строкам: X11+X12+X13+X14=240 X21+X22+X23+X24=1304 X31+X32+X33+X34=450 X41+X42+X43+X44=150 X51+X52+X53+X54=250 X61+X62+X63+X64=800 X71+X72+X73+X74=2460 б) по столбцам: X11+X21+X31+X51+X61+X71=2104 X12+X22+X32+X52+X62+X71=1700 X13+X23+X33+X53+X63+X71=1150 X14+X24+X34+X54+X64+X71=700 2. балансовое условие: 240+1304+450+150+250+800+2460=2104+1700+1150+700=5654 3. условие неотрицательности переменных: 4. Целевая функция задачи: Z=44X11+42X12+45X13+40X14+43X21+40X22+42X23+42X24+29X31+26X32+24X33+27X34+67X41+62X42+65X43+61X44+22X51+19X52+17X53+19X54+43X61+40X62+42X63+41X64

Проверка опорного решения на выполнение граничных условий: а) по строкам: 1.240=240 2. 454+850=1304 3.450=450 4. 150=150 5. 250=250 6. 800=800 7.1700+60+700=2460 б) по столбцам: 1. 454+450+150+250+800=2104 2. 1700=1700 3. 240+850+60=1150 4. 700=700 Проверка на число занятых клеток. ;10=10, т.е. решение верное и невырожденное. Вычисление значения целевой функции. Z=45*240+43*454+42*850+29*450+67*150+22*250+43*800= 129022

Проверка опорного решения на оптимальность: Для занятых клеток За первый потенциал примем произвольное число, больше чем C ij max ; Оценка свободной клетки вычисляется по формуле При решении задач на min решение является оптимальным, если для всех свободных клеток Для свободных клеток считаем оценки и размещаем их в правом нижнем углу свободной клетки.

Потенциалы и оценки для опорного решения задачи

Улучшающий многоугольник. Альтернативное решение. Так как оценки всех незанятых клеток , полученное решение оптимально. Необходимо отметить, что существует альтернативное оптимальное решение, т.к. потенциал клетки с индексом 24 равны нулю. По желанию заказчика работ изменим решение на альтернативное. Для этого построим улучшающий многоугольник. Его вершины должны располагаться в занятых клетках, кроме одной начальной, лежащей в испытуемой свободной клетке. Вершине, лежащей в испытуемой клетке, присваивается знак плюс, далее знаки чередуются. Среди всех Х находящихся в клетках с отрицательными вершинами, выбирается минимальное значение Хmin (Х74=700). Далее перемещаем 700 по многоугольнику с учетом знаков.

Улучшающий многоугольник. Альтернативное решение.

Улучшающий многоугольник. Альтернативное решение.

После получения альтернативного решения подсчитаем целевую функцию: Z=45*240+43*454+42*150+42*700+29*450+67*150+22*250 +43*800=129022. Она не изменилась.

Окончательное решение задачи

Ответ задачи Zопт= 129022+24*450=139822 руб Максимальная прибыль организации от проведения обследовательских работ будет равна 139 822 руб. при следующем распределении бригад по объектам недвижимости: - 1 бригада обследует 240 м2 3 объекта недвижимости; - 2 бригада обследует 454 м2 1 объекта недвижимости и 850 м2 3 объекта недвижимости; - 3 бригада обследует 450 м2 1 объекта недвижимости и 450 м2 3 объекта недвижимости; - 4 бригада обследует 150 м2 1 объекта недвижимости; - 5 бригада обследует 250 м2 1 объекта недвижимости; - 6 бригада обследует 800 м2 1 объекта недвижимости. Для обследования 2460 м2 объектов недвижимости мощностей обследовательской организации не хватило.