Шпаргалка по "Математическому программированию"

47. расчет оценок  оптимальности распределения  транспортных задач  и критерий оптимальности.

Исходя  из соотношения б) теоремы можно  записать следующую формулу для вычисления оценок: δ ij = ui +vj – сij. Для того, чтобы оценки не перепутать с объёмами перевозок, они (оценки) заключаются в круги.

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

 

48. перераспределение  поставок в транспортной  задаче

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

  Для перераспределения осуществляют построение цикла пересчета. В качестве клетки выбирается клетка с наибольшей положительной  оценкой. Эта клетка помечается знаком «+», то есть в неё необходимо записать некоторый объём поставки. Но тогда нарушится баланс по данному столбцу, следовательно, одну из занятых клеток данного столбца необходимо пометить знаком «-», то есть уменьшить объём поставки на такую же величину. Но тогда изменится баланс по данной строке, следовательно, какую-то занятую клетку данной строки необходимо пометить знаком «+». Данный процесс продолжается до тех пор, пока не поставлен знак «-» в строке, где находилась исходная клетка.

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

49. цепочки перераспределения,  их виды.

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

прибавлять  и отнимать Q к имеющимся перевозкам. Так как углов чётное количество, в половине клеток Q прибавится, а в другой половине - отнимется. Обход цикла начинают по часовой стрелке или против с претендующей клетки, помещая туда товар Q, затем из соседней клетки вычитают Q, затем прибавляют и т.д. Сама величина Q выбирается так, чтобы одна из клеток опустошалась, но ни одна из поставок не стала бы отрицательной.

Для этого  Q надо выбрать равным наименьшему уменьшаемому из клеток, в которых Q вычитается. На следующих рис. 7.1 и 7.2 покажем примеры циклов и правило вычисления.

    

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

 

50. Выбор объема перераспределения.

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

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

б) одна из занятых клеток должна стать свободной.

Для того, чтобы эти условия выполнялись, необходимо объём перемещаемой продукции  выбрать следующим: θ=min {хij} -, где {хij} – объёмы перевозок из клеток цикла  пересчёта, помеченных знаком «-».

θ = min{20;30}=20

К значениям  клеток, помеченных знаком «+»прибавляется θ. От значений клеток, помеченных знаком «-», вычитается θ. Значение поставок остальных клеток переписывается без изменений. В результате получим следующую таблицу. 

53. Алгоритм метода  потенциалов.

Алгоритм:

1. Проверить,  выполняется ли для задачи рав-во если нет, то в задачу вводится фиктивный поставщик или потребитель

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

3. Строится начальный  опорный план

4. Определяются  потенциалы пост-ков и потреб-лей

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

6. Загруж-т перспективную  клетку. Оформл-т нов.опорн.план в  виде трансп.таблицы. Переходят  к пункту 4. 
 
 
 
 
 
 
 

54. Учет затрат на  производство и  транспортировку  продукции. Транспортная задача с запретами на поставки.

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

Где Cij ‘ – приведенные затрат на производство одной единицы продукции.

Cij “– затраты на транспортировку одной единицы продукции.

 Дальше  задача решается обычным способом. 

Задачи  с запретами на поставки.

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

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

 

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

учет  ограничений по пропускной способности  маршрутов.

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

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

В некоторых  случаях в задаче требуется, что  например по маршруту Ak Bs должно обязательно осуществиться поставка в объема А ед. В этом случае из объема производства пункта А и объем S Bs вчитается обязательная поставка и задача решается относительно необязательности поставок. После получения оптимального решения обязательно поставка добавляется к объему стоящему в клетке Ak Bs.  
 

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

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

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

 
 
 
 
 

57.Понятие  двойственности. Экономическая  постановка двойственных  задач на примере  задачи об оптимизации  плана выпуска  продукции.

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

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

     Исходная  задача:

     а₁₁х₁+а₁₂х₂+…+ а_1пх_п≤в_{1              |}у₁

     а₂₁х₁+а₂₂х₂+…+ а_2пх_п≤в_{2              |}у₂

     _{………………..                                                 |..}      (1)

     а_т1х₁+а_т2х₂+…+ а_тпх_п≤в_{1           |} у_т 

     x_j≥0, j = 1,n(2) 

     z = c₁x₁+c₂x₂+…+c_nx_n ->max(3)

       _

       X = (x_1,x₂,…, x_n)

     a_ij – кол-во сырья i- го вида, затраченного для выпуска j-го вида продукции

     Двойственная  задача

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

у_i- цена i- го вида сырья имеющегося на предприятии.

     а₁₁у₁+а₂₁у₂+…+ а_т1у_т≥с₁             

     а₁₂х₁+а₂₂у₂+…+ а_т2х_п≥с₂             

     _{………………..}                                                       (1’)

     а_1пу₁+а_2пу₂+…+ а_тпу_т≥с_п            

     у_i≥0, j = 1,m(2’) 

F = b₁y₁+b₂y₂+…+b_my_m ->min(3’)

 

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

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

двойственную  задачу по следующим правилам:

1. Во всех ограничениях исходной задачи свободные члены должны

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

2. Ограничения-неравенства исходной задачи должны иметь знаки,

направленные  в одну строну.

3. Если целевая функция в исходной задаче минимизируется, ограничения-неравенства следует записать со знаком «≤» , тогда в двойственной задаче целевая функция будет минимизироваться и знаки ограничений-неравенств будут «≥».

4. Каждому ограничению исходной задачи соответствует переменная в

двойственной задаче. Если переменная соответствует неравенству, она неотрицательна, если равенству – то переменная без ограничений на знак («произвольная»).