Презентация на тему: МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное

Реклама. Продолжение ниже
МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
План лекции
1.Землеустроительные задачи, решаемые методами линейного программирования.
1. Землеустроительные задачи, решаемые методами линейного программирования.
2. Понятие и сущность транспортной задачи
2. Понятие и сущность транспортной задачи. Табличная форма записи исходных данных транспортной задачи
2. Понятие и сущность транспортной задачи. Особенности транспортной задачи
3. Базовая модель задачи, решаемой распределительным методом
II. Система ограничений Ограничения по строкам Количество перевозимых грузов из i -го пункта отправления в j -ые пункты назначения равно запасу i -го пункта
МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное
Балансовое условие: Количество распределяемых грузов и потребности в них должны быть равны: Структурная запись Развернутая запись: A 1 + A 2 +…+ A m = B 1 + B
Для решения задачи открыт ую модел ь приводят к закрытому виду путем введения фиктивного пункта отправления с запасом, равным:
При расчете разностей  к фиктивные элементы (столбец или строка) участвуют в последнюю очередь.   III. Условие неотрицательности переменных Xij ≥0
4. Методы составления первого опорного плана (решения)
5. Алгоритм метода минимального элемента
5. Алгоритм метода минимального элемента
6. Алгоритм метода максимального элемента
7. Алгоритм метода аппроксимации на min
7.Алгоритм метода аппроксимации на min
7. Алгоритм метода аппроксимации на min
8. Алгоритм метода аппроксимации на max
9. Проверка опорного решения на оптимальность методом потенциалов
Условие оптимальности План является оптимальным, если для свободных клеток: при решении задач на min :  i + c ij   j, или  ij  0 на max:
10. Улучшение опорного плана методом построения улучшающего многоугольника
Начинаем строить улучшающий многоугольник для свободной клетки, в которой характеристика максимальна по модулю. Из отрицательных вершин выбираем наименьшее
11. Задачи с дополнительными ограничениями Дополнительные ограничения типа, причем, иначе ограничение теряет смысл. Для учета этого ограничения необходимо
11. Дополнительные ограничения вида
После получения оптимального решения, учитывают все дополнительные ограничения. Для этого дополняют таблицу выброшенными ранее строкой и столбцом, в которых
МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное
Схема оформления и методы решения задач транспортного типа Демонстрационная задача №1
Порядок выполнения задачи:
Определение опорного решения задачи методом минимального элемента Формализация исходных данных задачи: Введем следующие обозначения: m - количество
МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное
МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное
МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное
МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное
МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное
МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное
МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное
МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное
МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное
МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное
МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное
1/43
Средняя оценка: 4.3/5 (всего оценок: 43)
Код скопирован в буфер обмена
Скачать (349 Кб)
Реклама. Продолжение ниже
1

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

Факультет Заочный Специальность 120300 «Землеустройство» Кафедра Землеустройства Дисциплина « Экономико-математические методы и моделирование » Лекция 2. Распределительный метод линейного программирования Лектор: доцент кафедры землеустройства, к.э.н. Сорокина Ольга Анатольевна

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
2

Слайд 2: План лекции

1. Землеустроительные задачи, решаемые методами линейного программирования. 2. Понятие и сущность транспортной задачи 3. Базовая модель задачи, решаемой распределительным методом 4. Методы составления первого опорного плана (решения) 5. Алгоритм метода минимального элемента 6. Алгоритм метода максимального элемента 7. Алгоритм метода аппроксимации на min 8. Алгоритм метода аппроксимации на max 9. Проверка опорного решения на оптимальность методом потенциалов 10. Улучшение опорного плана методом построения улучшающего многоугольника 11. Дополнительные ограничения

Изображение слайда
1/1
3

Слайд 3: 1.Землеустроительные задачи, решаемые методами линейного программирования

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

Изображение слайда
1/1
4

Слайд 4: 1. Землеустроительные задачи, решаемые методами линейного программирования

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

Изображение слайда
1/1
5

Слайд 5: 2. Понятие и сущность транспортной задачи

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

Изображение слайда
1/1
6

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

Пункт назначения B n Пункт отправления 1 2 J … n Запасы груза a i 1 С 11 Х 11 С 12 Х 12 С 1 j Х 1 j С 1 n Х 1 n А 1 2 С 21 Х 21 С 22 Х 22 С 2 j Х 2 j С 2 n Х 2 n А 2 i … С i1 Х i1 С i2 Х i2 С ij Х ij С in Х in А i m С m1 Х m1 С m2 Х m2 С mj Х mj С mn Х mn А m Потребность в грузах B j B 1 B 2 B j  A i  B j Пункт назначения Пункт отправления 1 2 j… n Запасы груза а i 1 C11 X11 C12 X12 C1j X1j C1n X1n A1 2 C21 X21 C22 X22 C2j X2j C2n X2n A2 i… Ci1 Xi1 Ci2 Xi2 Cij Xij Cin Xin Ai m Cm1 Xm1 Cm2 Xm2 Cmj Xmj Cmn Xmn Am Потребность в грузах В i В1 В2 В j В n A i B j

Изображение слайда
1/1
7

Слайд 7: 2. Понятие и сущность транспортной задачи. Особенности транспортной задачи

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

Изображение слайда
1/1
Реклама. Продолжение ниже
8

Слайд 8: 3. Базовая модель задачи, решаемой распределительным методом

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

Изображение слайда
1/1
9

Слайд 9: II. Система ограничений Ограничения по строкам Количество перевозимых грузов из i -го пункта отправления в j -ые пункты назначения равно запасу i -го пункта отправления. Структурная запись Развернутая запись x 11 + x 12 + x 1 j +…+ x 1 n = A 1 x 21 +x 22 +x 2j +…+x 2n =A 2 x i1 +x i2 +x ij +…+x in =A i x m1 +x m2 +x mj +…+x mn =A m

Изображение слайда
1/1
10

Слайд 10

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

Изображение слайда
1/1
11

Слайд 11: Балансовое условие: Количество распределяемых грузов и потребности в них должны быть равны: Структурная запись Развернутая запись: A 1 + A 2 +…+ A m = B 1 + B 2 +…+ B n,, если модель задачи закрытая; если модель задачи открытая

Изображение слайда
1/1
12

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

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

Изображение слайда
1/1
13

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

Изображение слайда
1/1
14

Слайд 14: 4. Методы составления первого опорного плана (решения)

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

Изображение слайда
1/1
Реклама. Продолжение ниже
15

Слайд 15: 5. Алгоритм метода минимального элемента

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

Изображение слайда
1/1
16

Слайд 16: 5. Алгоритм метода минимального элемента

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

Изображение слайда
1/1
17

Слайд 17: 6. Алгоритм метода максимального элемента

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

Изображение слайда
1/1
18

Слайд 18: 7. Алгоритм метода аппроксимации на min

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

Изображение слайда
1/1
19

Слайд 19: 7.Алгоритм метода аппроксимации на min

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

Изображение слайда
1/1
20

Слайд 20: 7. Алгоритм метода аппроксимации на min

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

Изображение слайда
1/1
21

Слайд 21: 8. Алгоритм метода аппроксимации на max

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

Изображение слайда
1/1
22

Слайд 22: 9. Проверка опорного решения на оптимальность методом потенциалов

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

Изображение слайда
1/1
23

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

Изображение слайда
1/1
24

Слайд 24: 10. Улучшение опорного плана методом построения улучшающего многоугольника

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

Изображение слайда
1/1
25

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

Изображение слайда
1/1
26

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

Изображение слайда
1/1
27

Слайд 27: 11. Дополнительные ограничения вида

Первоначальные действия по учету таких ограничений аналогичны действиям для случая ограничений вида. Если же обе указанные величины оказались больше нуля, то дополнительно проводится блокировка соответствующей оценки C e. При решении задач на min оценку делают равной большой величине, значительно большей величины C y, например, C y =10000; это означает, что мы делаем невыгодной транспортировку из i –го пункта отправления в j –й пункт назначения, т. к. стоимость транспортировки стала очень большой. В результате алгоритм решения задачи не допускает возрастания величины X y свыше D y, что и требуется по условию. Если задача решается на max, то необходимо было бы положить C y =0, что также означало невыгодность передачи груза из i –го пункта отправления в j –й пункт назначения свыше предписанного груза D y (дополнительная прибыль от такой передачи была бы равна нулю). Помимо рассмотренных выше ограничений на практике встречаются дополнительные ограничения вида (в частном случае при L y =0 имеем ). Ограничения данного вида не учитываются при постановке задачи. Их анализ ведется после получения оптимального решения задачи.

Изображение слайда
1/1
28

Слайд 28: После получения оптимального решения, учитывают все дополнительные ограничения. Для этого дополняют таблицу выброшенными ранее строкой и столбцом, в которых должно быть записано указанное значение X y, кроме того необходимо восстановить первоначальные значения A i, B j Бессмысленно последнюю таблицу проверять на оптимальность методом потенциалов, т. к. мы принудительно изменили полученное оптимальное решение для того, чтобы учесть дополнительные условиям. После получения оптимального решения рисуется новая матрица окончательного решения, в которой учитываются ограничения. Таким образом, после решения проверяют: 1)   Учитываются ли дополнительные условия. 2)   Восстанавливают первоначальные значения величин A i, B j. 3)   В результате получаем новую таблицу. 4)   Вычеркиваем из последней таблицы фиктивную строку (столбец), (получаем окончательное решение) 5)   Записываем ответ

Изображение слайда
1/1
29

Слайд 29

Порядок полного оформления решений задач транспортного типа 1). Дать пояснение всех обозначений, используемых при постановке задачи, с указанием единиц измерения всех величин (A i, B j, C ij, X ij ). 2). Дать математическую формулировку дополнительных условий, учитываемых в постановке задачи. 3). Проверить задачу на сбалансированность и, при необходимости, привести к сбалансированному виду. 4). Привести структурную запись задачи (ограничения по строкам, ограничения по столбцам, балансовое условие, условие неотрицательности переменных, требование к целевой функции). 5). Привести развернутую запись задачи (ограничения по строкам, ограничения по столбцам, требование к целевой функции). 6). Получить опорное решение заданным способом (процесс решения отразить в таблице). 7). Проверить опорное решение на оптимальность и, при необходимости, получить оптимальное решение методами потенциалов и улучшающего многоугольника (процесс решения отразить в таблицах). 8). Записать решение поставленной задачи, и дать его интерпретацию с учетом дополнительных условий (при их наличии) и исходной несбалансированности задачи (если она была), после чего записать окончательное решение задачи.

Изображение слайда
1/1
30

Слайд 30: Схема оформления и методы решения задач транспортного типа Демонстрационная задача №1

Найти минимум затрат на перевозку кормов с севооборотных массивов на животноводческие фермы. Данные по затратам на перевозку единицы груза с учетом удаленности участков от производственных центров приведены в табл. 1. Таблица 1 Табличная форма записи исходных данных транспортной задачи Фермы Севообороты Удельные затраты на перевозку грузов, руб / т Ресурсы севооборотов, т Ферма1 Ферма2 Ферма3 Ферма4 Ферма5 Полевой-1 55 48 49 60 25 149 Полевой-2 45 35 96 55 66 163 Кормовой 47 66 90 97 20 382 Потребности ферм в кормах, т 139 165 120 130 140

Изображение слайда
1/1
31

Слайд 31: Порядок выполнения задачи:

1. Записать математическую формулировку задачи в общем виде. 2.Дать развернутую запись условия задачи с числовым значением переменных и ресурсов. 3.Задачу решить, используя метод наилучшего элемента. 4. Записать ответ.

Изображение слайда
1/1
32

Слайд 32: Определение опорного решения задачи методом минимального элемента Формализация исходных данных задачи: Введем следующие обозначения: m - количество севооборотов (пунктов отправления); n - количество ферм (пунктов назначения); i - номер севооборота : j - номер фермы: i-  i, m – индексы строк; j, n – индексы столбцов; стоимость перевозки единицы объема продукции с i –го севооборота на j -ую ферму; объем перевозимой продукции с i –го севооборота на j –ую ферму; - объем продукции, производимой на i –ом севообороте и предназначенной для транспортировки на фермы, т; - потребность j –ой фермы в кормах, т; Z - целевая функция

Изображение слайда
1/1
33

Слайд 33

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

Изображение слайда
1/1
34

Слайд 34

Проверка сбалансированности задачи Должно быть 149 + 163 + 382 = 694 139 +165 + 120 + 130 + 140 = 694 Задача сбалансирована (закрыта). Матричная запись исходных данных задачи после учета требований сбалансированности представлена в табл.3. Таблица 2 Табличное представление исходных данных задачи Фермы Удельные затраты на перевозку груза, тыс.руб/т севообороты Ферма 1 Ферма 2 Ферма 3 Ферма 4 Ферма 5 Ресурсы севооборотов, т Полевой-1 55 Х11 48 Х12 49 Х13 60 Х14 25 Х15 149 Полевой-2 45 Х21 35 Х22 96 Х23 55 Х24 66 Х25 163 Кормовой 47 Х31 66 Х32 90 Х33 65 Х34 20 Х35 382 Потребности ферм в кормах, т 139 165 120 130 140 694 694

Изображение слайда
1/1
35

Слайд 35

1) целевая функция Z=55x 11 +48x 12 +49x 13 +60x 14 +25x 15 +45x 21 +35x 22 +96x 23 +55x 24 +66x 25 + + 47x 31 +66x 32 + 90 x 33 +65 x 34 +20 x 35 min ; 2) граничные условия Ограничения по строкам исходной матрицы: x 11 + x 12 + x 13 + x 14 + x 15 =149, x 21 + x 22 + x 23 + x 24 + x 25 =163, x 31 + x 32 + x 33 + x 34 + x 35 =382; Ограничения по столбцам исходной матрицы: x 11 + x 21 + x 31 =139, x 12 + x 22 + x 32 =165, x 13 + x 23 + x 33 =120, x 14 + x 24 + x 34 =130, x 15 + x 25 + x 35 =140. 3) балансовое условие : 149+163+382 = 139+165+120+130+140=694; 4) условие неотрицательности неизвестных: Х 11,12,13,14,15,21,22,23,24,25,31,32,33,34,35 >=0

Изображение слайда
1/1
36

Слайд 36

Таблица 4 Получение опорного решения методом наилучшего минимального элемента Фермы Удельные затраты на перевозку груза, тыс.руб/т севообороты Ферма 1 Ферма 2 Ферма 3 Ферма 4 Ферма 5 Ресурсы севооборотов, т Полевой-1 55 48 2 49 120 60 27 25 149 147 27 Полевой-2 45 35 163 96 55 66 163 Кормовой 47 139 66 90 65 103 20 140 382 242 103 Потребности ферм в кормах, т 139 165 120 130 103 140 694 694

Изображение слайда
1/1
37

Слайд 37

Проверка опорного решения на выполнение граничных условий: а) по строкам: 2+120+27=149 163=163 139+103+140=382 б) по столбцам: 139=139 163+2=165 120=120 27+103=140 Граничные условия по строкам и столбцам выполняются. Проверка по числу занятых клеток : Количество занятых клеток в опорном плане должно быть равно условию вырожденности: К зан <= m + n – 1, где m – число строк, n – число столбцов. В нашем случае K зан =7 и (m+n-1)=3+5-1=7; то есть решение верное и невырожденное. Вычисление целевой функции: Z == =2*48+120*49+27*60+163*35+139*47+103*65+140*20=29329 Проверка опорного решения на оптимальность. Введем новые характеристики (потенциалы поставщиков и потребителей продукции и соответственно.

Изображение слайда
1/1
38

Слайд 38

Для занятых клеток За первый потенциал примем с onst – произвольное число; C ij max = 90, чтобы обеспечить положительность, тогда 90+48=138 и т.д. Оценка свободной клетки вычисляется по формуле При решении задач на min решение является оптимальным, если для всех свободных клеток. Для свободных клеток считаем оценки и размещаем их в правом нижнем углу свободной клетки (табл.5).

Изображение слайда
1/1
39

Слайд 39

Потенциалы и оценки для опорного решения задачи Севообороты Удельные затраты на перевозку груза, тыс.руб/т Ресурсы севооборотов, т 132 138 139 150 105 Ферма 1 Ферма 2 Ферма 3 Ферма 4 Ферма 5 90 Полевой – 1 55 13 48 2 49 120 60 27 25 10 149 103 Полевой – 2 45 16 35 163 96 60 55 8 66 64 163 85 Кормовой 47 139 66 13 90 36 65 103 20 140 382 Потребности ферм в кормах, т 139 165 120 130 140 694 694

Изображение слайда
1/1
40

Слайд 40

В данном случае для всех свободных клеток условие оптимальности выполняется, поэтому полученное решение оптимально. Целевую функцию вычисляем для контроля формул, используя вычисленные потенциалы и : Z = Z контр. = (62*139+68*165+69*120+80*130+35*140) – (20*149+33*163+15*382) =29329. Формализованное представление оптимального решения задачи приведено в табл.6.

Изображение слайда
1/1
41

Слайд 41

Таблица 6 Оптимальное решение задачи J i 1 2 3 4 5 Ресурсы, т 1 55 48 2 49 120 60 27 25 149 2 45 35 163 96 55 66 163 3 47 139 66 90 65 103 20 140 382 Потреб - ности, т 139 165 120 130 140 694 694

Изображение слайда
1/1
42

Слайд 42

Ответ: затраты на перевозку кормов с севооборотных массивов на животноводческие фермы будут минимальны и равны 29329 тыс. рублей при следующем распределении перевозок с севооборотов на фермы: с полевого севооборота 1: 2 т на 2 ферму, 120 т на 3 ферму, 27т на 4 ферму; с полевого севооборота 2: 163 т на 2 ферму; с кормового севооборота: 139 т на 1 ферму, 103 т на 4 ферму, 140 т на 5 ферму.

Изображение слайда
1/1
43

Последний слайд презентации: МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное

Спасибо за внимание!

Изображение слайда
1/1
Реклама. Продолжение ниже