13005

Транспортна модель та її застосування в землевпорядкуванні

Лекция

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

Лекция №1.4. Транспортна модель та її застосування в землевпорядкуванні. План 1.Постановка задач лінійного програмування транспортного типу. Види землевпорядних задач що зводяться до задачі лінійного програмування транспортного типу. 2.Методи розв’язання задач...

Украинкский

2013-05-07

584 KB

2 чел.

Лекция №1.4.

Транспортна модель та її застосування в землевпорядкуванні.

План

1.Постановка задач лінійного програмування транспортного типу. Види землевпорядних задач, що зводяться до задачі лінійного програмування транспортного типу.

2.Методи розв’язання задач транспортного типу. Визначення опорного рішення: методи апроксимації, мінімального (максимального) елементу, північно-західного кута.

Понятие и сущность транспортной задачи

Постановка задачи. Имеется m поставщиков с запасом Ai (i=1, 2, ...m);

i - номер поставщика;

n – потребителей с потребностями грузов Вj (j= 1, 2, ...n);

j – номер потребителя;

индексы i, m принадлежат строке; j, n – столбцу.

xij – объем груза, перевозимого из i-го пункта отправления в j-ый пункт назначения.

Известна стоимость перевозки единицы груза по каждому возможному маршруту сij из i-го пункта отправления в j-ый пункт назначения.

Требуется определить такие оптимальные маршруты поставок xij от i-го поставщика к j-му потребителю (т.е. такой план перевозок), чтобы значение целевой функции достигало своего экстремума (min, max).

Особенности транспортной задачи

1. Переменные в транспортной модели выражаются в одних и тех же единицах измерения (га, км, руб, ц и т. д.).

2. Коэффициенты при переменных в ограничениях модели всегда равны единице.

3. Каждая переменная входит в два ограничения: в ограничение - по строке и в ограничение по столбцу.

4. Все ограничения представлены в виде уравнений.

Табличная форма записи исходных данных транспортной задачи

Пункт назначения

Пункт

отправления

1

2

J

n

Запасы груза ai

1

С11

Х11

С12

Х12

С1j

Х1j

С1n

Х1n

А1

2

С21

Х21

С22

Х22

С2j

Х2j

С2n

Х2n

А2

i

Сi1

Хi1

Сi2

Хi2

Сij

Хij

Сin

Хin

Аi

m

Сm1

Хm1

Сm2

Хm2

Сmj

Хmj

Сmn

Хmn

Аm

Потребность в грузах Bj

B1

B2

Bj

Bn

Ai

Bj

Базовая модель задачи

Экономико-математическая модель состоит из трех составных частей:

  1.  целевая функция;
  2.  система ограничений;
  3.  неотрицательность переменных.

Структурная запись

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

Развернутая запись

, где

cij —  стоимость единицы груза из i-го пункта отправления в j-ый пункт назначения.

  1.  Система ограничений

Ограничения по строкам

Количество перевозимых грузов из 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-м пункте назначения.

Ограничения по столбцам

Структурная запись

Развернутая запись

Балансовое условие:

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

Структурная запись: ;

Развернутая запись: Am+A2+…+Am=B1+B2+…+Bn,,

если модель задачи закрытая;

если  модель задачи открытая.

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

или фиктивного пункта  назначения с потребностью, равной:

Стоимость перевозок грузов по фиктивному пункту принимают равными «0».

При расчете разностей к фиктивные элементы (столбец или строка) участвуют.

  1.  Условие неотрицательности переменных

Методы составления первого опорного плана (решения)

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

Алгоритм метода минимального элемента

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

Алгоритм метода максимального элемента

  1.  Из всех оценок  матрицы выбирается максимальная оценка.
  2.  В клетку с максимальным значением оценки  ставится значение поставки, равное минимальному значению соответствующего запаса  или потребностями . Из соответствующего запаса и потребности данная поставка вычитается.
  3.  Выбирается следующее наибольшее значение оценки  и в данную клетку заносится max поставка (min из  или ). Из соответствующего запаса и потребности данная поставка вычитается.
  4.  Повторяем пункт 3 до тех пор, пока все грузы будут распределены.

Алгоритм получения опорного решения

методом аппроксимации на min

1. По каждой строке или столбцу выбирают два min значения c ij 

2. Определяют их разность  к  

3. Из всех разностей выбирают наибольшую  к(max).

4. В столбец или строку, которые относятся к наибольшей разности в клетку с наименьшим значением C ij min заносят требуемую поставку груза.

5. Далее решение повторяют с вычислением новых разностей до получения опорного плана.

Пример решения задачи на min

Получение опорного решения методом аппроксимации.

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

МФ

ОФ

СФ

Выход кормов

Столбец рзностей μk

    bj

ai

35

36

39

μ1

μ2

μ3

1

31

4

100    

5

х      

15

x     

100

1

2

37

25

200   

1

х       

       2

х

200

1

1

3

33

30

200   

3

50  

6

50  

300

3

3

3

Потребность

500

50

50

600

строка разностей

21

2

4

5

2

4

В случае, когда выходит по алгоритму и столбец и строка, то на одном шаге выходит только один элемент либо столбец, либо строка, а второй остается и участвует в решении; в оставшийся элемент, когда на него выпадает максимальная разность, вносится «нулевая» поставка, и т.о. преодолевается вырожденность «нулей» в матрице будет столько, насколько количество занятых клеток меньше m+n-1.

Особенности:

а) Если при решении методом аппроксимации имеются, два одинаковых значения разностей , то первая поставка груза вносится в ту клетку, которой соответствует минимальная оценка c ij- min.

б) Если имеется две max разности к и две min оценки cij то в первую очередь груз заносится в ту клетку, куда можно поставить большую поставку груза.

Алгоритм решения задачи методом аппроксимации на max

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

2. Находят их разность ij-ij..

3. Из всех разностей выбирают наибольшую.

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

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

6. Далее пункты 1-3 повторяют до полного распределения грузов.

Проверка опорного решения на оптимальность;

улучшение неоптимального решения методом потенциалов

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

 i + c ij = j,

где  i – потенциалы по строкам; j  - потенциалы по столбцам.

За первый потенциал берется любое число. Чтобы потенциалы были  только положительными, необходимо первый потенциал взять чуть больше не большей оценки C ij по матрице.

 i =j- c ij

Условие оптимальности

План является оптимальным, если для свободных клеток:

при решении задач на min:  i +c ij  j , или    ij  0

на max:   

Улучшение опорного плана методом построения

улучшающего многоугольника

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

Правило построения улучшающего многоугольника.

1. Стороны многоугольника должны быть  параллельны строкам и столбцам матрицы.

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

3. Знаки присваиваются «+» вершине в свободной клетке; и далее знаки чередуются «-» «+» «-».

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

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

Контроль вычислений:

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

, .

Вырожденные планы задач

Условие вырожденности  m+n-1 – число независимых условий. Количество занятых клеток должно быть равно условию вырожденности, где m - количество строк, n - количество столбцов.

Если количество занятых клеток будет равно условию, то план невырожден.

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

Если количество занятых клеток < условия, то план вырожден.

Признаки врожденности плана:

а=b1,  a1=b2,  a2=b3;

a1=b1+b2,  b1=a1+a4;

a1+a2=b2+b3

a1+a2 = b1+b2+b3+ и др.

Преодоление вырожденности производят в процессе решения задачи методом аппроксимации; В случае, когда выходит по алгоритму и столбец и строка, то на одном шаге выходит только один элемент (либо столбец, либо строка), а второй элемент остается и участвует в дальнейшем решении задачи; в оставшийся элемент, когда на него выпадает максимальная разность , вносится «нулевая» поставка и т.о. преодолевается вырожденность, а нулей в матрице будет столько, насколько количество занятых клеток меньше m+n-1.

Задачи с дополнительными ограничениями

Дополнительные ограничения типа , причем , иначе ограничение теряет смысл.

Для учета этого ограничения необходимо определить измененные объемы производства  и потребления .

Дальнейший алгоритм действий зависит от конкретных числовых значений рассматриваемых величин  и .

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

Дополнительные ограничения вида .

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

При решении задач на min оценку делают равной большой величине, значительно большей величины , например, =10000; это означает, что мы делаем невыгодной транспортировку из i–го пункта отправления в j–й пункт назначения, т. к. стоимость транспортировки стала очень большой. В результате алгоритм решения задачи не допускает возрастания величины  свыше , что и требуется по условию.

Если задача решается на max, то необходимо было бы положить =0, что также означало невыгодность передачи груза из i–го пункта отправления в j–й пункт назначения свыше предписанного груза  (дополнительная прибыль от такой передачи была бы равна нулю).

Помимо рассмотренных выше ограничений на практике встречаются дополнительные ограничения вида  (в частном случае при =0 имеем ).

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

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

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

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

  1.  Учитываются  ли дополнительные условия.
  2.  Восстанавливают первоначальные значения величин , .
  3.  В результате получаем новую таблицу.
  4.  Вычеркиваем из последней таблицы фиктивную строку (столбец), (получаем окончательное решение)
  5.  Записываем ответ.
  6.  
  7.  Определение других оптимальных решений

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

Альтернативные решения с отклонениями целевой функции

от экстремума.

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

  1.  Корректура оптимального плана.

3. Изменение запасов и потребностей в отдельных пунктах при сохранении общего объема производства

Рассмотрим пример решения задач на max.

Пусть запас А4   увеличится на 50, то возникает вопрос на каком другом пункте отправления целесообразно уменьшить ресурс, чтобы  не изменилась.

1

2

3

n

Аi

1

-50

Аi-50

2

3

4

+50

А4+50

m

Bj

B1

B2

B3

B4

Величина поставок  в строке 4 тоже должна возрасти на 50, т. к. , при этом количество занятых клеток может увеличиться. Из каких других занятых клеток, не стоящих в строке 4, целесообразно переместить ресурс так, чтобы изменение z было незначительным? Анализируем все занятые клетки, оценивая величины , т. к. они позволяют рассчитать значение  при перемещении ресурса по столбцу из клетки  в клетку ,  - перемещаемый груз. При решении задачи на max, ij надо брать max, а при решении на min,  берется min, т.к. .

занятой клетке

занятой клетке

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

Анализ оптимальных решений на основе экономической интерпретации потенциалов

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

- средние расходы i-го поставщика на транспортировку единицы продукции к потребителям;

- средние расходы j-го потребителя на доставку единицы продукции.

Термин «средние» предполагает, что, например, значение  характеризует всю продукцию данного поставщика, предназначенную в общем случае для нескольких потребителей  для занятой клетки.

При возрастании на единицу объема производства Аi потребления продукции Bj в пунктах i и j соответственно (т. е. при сбалансированном изменении исходных данных) (клетка ij занята), целевая функция возрастает на величину , т. е. на величину .

Аналогично можно говорить об уменьшении z, если объем производства и потребления в пунктах i и j уменьшится.

При решении задач на min

Необходимо решить на каком конкретно пункте целесообразно сократить потребление продукции и у какого поставщика необходимо уменьшить запас? (При решении задачи на минимум сокращение запасов и потребностей должно быть в пункте с максимальной оценкой!).

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

Аналогично, при увеличении объема продукции, целесообразно взять потребителя с наименьшим потенциалом , а поставщика с наибольшим , тогда , следовательно Z возрастает в наименьшей степени.

Таким образом, на основании анализа потенциалов устанавливаем мощности какого поставщика и потребителя нужно увеличить или уменьшить, после увеличения (уменьшения) , , решить задачу на ЭВМ.

Ai

-50

c

c

c

+50

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

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

Порядок полного оформления решений задач

транспортного типа

1). Дать пояснение всех обозначений, используемых при постановке задачи, с указанием единиц измерения всех величин (Ai, Bj, Cij, Xij).

2). Дать математическую формулировку дополнительных условий, учитываемых в постановке задачи.

3). Проверить задачу на сбалансированность и, при необходимости, привести к сбалансированному виду.

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

5). Привести развернутую запись задачи (ограничения по строкам, ограничения по столбцам, требование к целевой функции).

6). Получить опорное решение заданным способом (процесс решения отразить в таблице).

7). Проверить опорное решение на оптимальность и, при необходимости, получить оптимальное решение методом потенциалов (процесс решения отразить в таблицах).

8). Записать решение формализованно поставленной задачи, и дать его интерпретацию с учетом дополнительных условий (при их наличии) и исходной несбалансированности задачи (если она была), после чего записать окончательное решение задачи.

Схема оформления и методы решения задач транспортного типа

Демонстрационная задача

Найти минимум затрат на перевозку кормов с севооборотных массивов на животноводческие фермы. Данные по затратам на перевозку единицы груза с учетом удаленности участков от производственных центров приведены в табл. 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. Записать математическую формулировку задачи в общем виде.

2. Дать развернутую запись условия задачи с числовым значением переменных и ресурсов.

3. Задачу решить, используя метод наилучшего элемента.

4. Записать ответ.

Определение опорного решения задачи методом минимального элемента

Формализация исходных данных задачи:

Введем следующие обозначения:

m - количество севооборотов (пунктов отправления);

n - количество ферм (пунктов назначения);

i - номер севооборота:

j - номер фермы:

  1.  i, m – индексы строк; j, n – индексы столбцов;

стоимость перевозки единицы объема продукции с i –го севооборота на j-ую ферму;

- объем перевозимой продукции с i –го севооборота на j –ую ферму;

- объем продукции, производимой на i –ом севообороте и предназначенной для транспортировки на фермы, т;

-потребность j –ой фермы в кормах, т;

- целевая функция.

Исходная информация обычно заносится в матрицу специального вида (табл.2)

Таблица 2

Табличная форма записи исходных данных

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

Номера

Номера пунктов приема

Объемы производства

севооборотов

1

2

3

n

продукции

1

C11

X11

C12

X12

C13

X13

C1n

X1n

A1

2

C12

X21

C22

X22

C23

X23

C2n

X2n

A2

m

Cm1

Xm1

Cm2

Xm2

Cm3

Xm3

Cmn

Xmn

AM

Максимальные объемы переработки продукции

B1

B2

B3

Bn

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

Запись задачи транспортного типа в структурной форме:

Ограничения по строкам:

Сумма перевозимых кормов с i –го севооборотного массива на j –е фермы должна быть равна запасу кормов данного севооборота:

Ограничения по столбцам:

Сумма объемов продукции, доставляемых на j –ую ферму со всех севооборотов, должна быть равна потребности в кормах на данной ферме:

Балансовое условие:

Сумма объемов продукции, производимой на всех севооборотных массивах, должна быть равна общей потребности ферм в кормах.

Условие не отрицательности переменных:

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

Должно быть

149 + 163 + 382 = 694

139 +165 + 120 + 130 + 140 =694

Задача сбалансирована (закрыта).

Матричная запись исходных данных задачи после учета требований сбалансированности представлена в табл.3.

Таблица 3

Табличное представление исходных данных задачи

Фермы

Удельные затраты на перевозку груза, тыс.руб/т

Ресурсы

Севообороты

Ферма 1

Ферма 2

ферма 3

Ферма 4

Ферма 5

севооборотов, т

Полевой-1

           55

X11

           48

X12

           49

X13

           60

X14

        25

X15

         149

Полевой-2

           45

X21

           35

X22

           96

X23

           55

X24

        66

X25

         163

Кормовой

           47

X31

           66

X32

           90

X33

           65

X34

        20

X35

         382

Потребности ферм в кормах, т

    139

    165

    120

    130

   140

694

694

1) целевая функция

Z=55x11+48x12+49x13+60x14+25x15+45x21+35x22+96x23+55x24+66x25+47x31+66x32+

+90x33+65x34+20x35 min;

2) граничные условия

Ограничения по строкам исходной матрицы:

   x11+x12+x13+x14+x15=149,

   x21+x22+x23+x24+x25=163,

   x31+x32+x33+x34+x35=382;

Ограничения по столбцам исходной матрицы:

   x11+x21+x31=139,

   x12+x22+x32=165,

   x13+x23+x33=120,

   x14+x24+x34=130,

   x15+x25+x35=140.

3) балансовое условие: 

149+163+382 = 139+165+120+130+140=694;

4) условие неотрицательности неизвестных:

x110, x120, x130, x140, x150, x210, x220, x230, x240, x250, x310,x320, x330, x340, x35 0;

Получение опорного решения методом минимального элемента удобно проводить в таблице специального вида (табл.4).

Таблица 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

 2

120

130

103

140

694

694

Проверка опорного решения на выполнение граничных условий:

а) по строкам:

   2+120+27=149

   163=163

   139+103+140=382

б) по столбцам:

   139=139

   163+2=165

   120=120

   27+103=140

Граничные условия по строкам и столбцам выполняются.

Проверка по числу занятых клеток :

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

, где m – число строк, n – число столбцов.

В нашем случае 7 и (m+n-1)=3+5-1=7; то есть решение верное и невырожденное.

Вычисление целевой функции:

Z==2*48+120*49+27*60+163*35+139*47+103*65

+140*20=29329

Проверка опорного решения на оптимальность.

Введем новые характеристики (потенциалы поставщиков и потребителей продукции  и  соответственно.

Вычисление потенциалов  и:

Для занятых клеток

За первый потенциал примем сonst – произвольное число; max=90, чтобы обеспечить положительность, тогда 90+48=138 и т.д.

Оценка свободной клетки вычисляется по формуле

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

Таблица 5

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

Севообороты

Удельные затраты на перевозку груза, тыс.руб/т

Ресурсы

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

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

Целевую функцию вычисляем для контроля формул, используя вычисленные потенциалы  и :

Z =

Zконтр. = (62*139+68*165+69*120+80*130+35*140) – (20*149+33*163+15*382) =29329.

Формализованное представление оптимального решения задачи приведено в табл.6.

Таблица 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

Ответ: затраты на перевозку кормов с севооборотных массивов на животноводческие фермы будут минимальны и равны 29329 тыс. рублей при следующем распределении перевозок с севооборотов на фермы:

с полевого севооборота 1: 2 т на 2 ферму, 120 т на 3 ферму, 27т на 4 ферму;

с полевого севооборота 2: 163 т на 2 ферму;

с кормового севооборота: 139 т на 1 ферму, 103 т на 4 ферму, 140 т на 5 ферму.

PAGE  2


EMBED Equation.3  

Уменьшение объема производства

EMBED Equation.3  

В клетке с максимальной оценкой уменьшаем поставку

EMBED Equation.3  Увеличение объема производства

EMBED Equation.3  

EMBED Equation.3  

270

300

_

 200

+

 170

30

50

___

30

   +

конт =

m    n

    =   c ij x ij min

         i=1j=1  

               n               m

конт.= Вj j- Аi i

               j=1           i=1

С in +i = 0 (i=1,2,...m) или 

C im +i = 0 (j=1,2,...n)

             m              n       

bn+i = ai *-  b j

             i =1      j =1

                 n         m

Am+i = Bj -A i

                j=1        i=1


 

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

23306. Етномовні макроспільності первісності - загальна хар-ка; індоєвропейська родина 19 KB
  Ностратична макроспільнота Ескалеутська родина екімоси алеути – мови народів Півночі Алтайська родина – тюркська татарська узбецька киргизька туркменська турецька монгольська бурятська калмицька Уральські мови фіноугорські мови та діалекти Дравідійська родина – еламська протоіранська Картвельська – грузинська та діалекти народів Закавказзя Індоєвропейська – 12 мов та мовних груп: 1. індоіранські давньоіндійські мови зокрема мова Вед санскрит давньоіранські мови Авести 3. тохарські мови 7. альбанські мови 8.
23307. Археологічні культури первісності на території України 18.5 KB
  ; €œІсторія української культури€ т. 1 Основні етапи розвитку матеріальної та духовної культури первісного суспільства на території України 1. Головним об’єктом дослідження історії первісних суспільств зокрема на території України є так звані археологічні культури – група або декілька груп чи комплексів груп матеріальних викопних археологічних знахідок які харся трьома спільностями: спільність території поширення цих пам’яток часу або хронологічного періоду поширення технології виготовлення 1 знаряддя праці з природних та штучних...
23308. Культурно-мистецьке життя Галицько-Волинського князівства 15 KB
  життя ГВК літературни процес образотворче мистецтво та архітектура ГВК 1 Впродовж другої половини ХІІІ ст. процеси давньоукраїнського державотворення переміщується на західноукраїнські землі де галицькі князі Роман Мстиславич і його син Данило Галицький створили ГВК. Протяго майже 40 років Данило Романович об’єднав етнічні українські землі у складі ГВК. ГВК втратило політичну незалежність і було поділено між Польським та Угорським королівствами.
23309. ІУК як наукова дисципліна 26.5 KB
  Розвиток ІУК в ХХ ст. Важливий внесок у становлення ІУК як науки про культуру протягом ХІХ ст. зробили: вихованці та викладачі внз Харківський Київський університети науковці з академічних установ Росія АвстроУгорщина Німеччниа Франція представники різних державних і громадських наукових товариств ІсторикоФілологічне Товариство Харківський унт КАК Київська археографічна комісія Південнозахідний відділ РГТ Російське географічне товариство комісій КАК об’єдання наковців та окремі дослідники Основними напрямами...
23310. Культура як об’єкт наукового дослідження 18.5 KB
  Дослідженням культури в усіх її проявах займаються науки про культуру: історія культури теорія культури філософія культури соціологія культури культурологія соціальна онтологія. більшість наук використовують методи а загальноісторичний окремий тип соціальноекономічного розвитку суспільства ототожнюється із однойменним типом культури б локальногеографічний поділ культур світу на етнічні народні регіональні континентальні Інші типи культур: класові професійні субкультури молодіжні етнічні та інші 2. Чинники формування...
23311. Классификация гласных звуков. Принципы классификации гласных по МФА. Дифтонги 22.5 KB
  Дифтонги. дифтонги сложный гласный состоящий из двух элементов образующих один слог чем и обеспечивается фонетическая целостность. Дифтонги нисходящие – aurum восходящие иа.
23312. Сравнительно-исторический метод в языкознании. Периодизация. Внешняя и внутренняя реконструкция 28 KB
  Сравнительноисторический метод – метод классификации языков который служит для сравнительного изучения языкового материала. Принципы и методы сравнительноисторического метода: 1 Тщательный отбор языкового материала подлежащего сравнению. Сравниваемые языковые формы должны соотноситься по значению но подобная соотнесенность может быть лишь частичной. 3 Реконструкция праязыковых форм.
23313. Зависимость композиции произведения от художественного метода, рода и жанра 28.5 KB
  Зависимость композиции произведения от художественного метода рода и жанра. Главные особенности: исключительные обстоятельства действия исключительные герои Автор затушёвывает особые свойства героя для создания романтического образа Цыгане Пушкина – культ свободы В романтических произведениях автор своё субъективное начало проявляет более широко и властно чем в классицистических. композиция лирического произведения см. ответ на вопрос №49 композиция драматического произведения см.