Метод потенциалов в решении распределительных задач

6. Метод потенциалов  в решении распределительных  задач (определение  первого допустимого  решения, оценка  полученного решения,  нахождение нового  допустимого решения) – из распечатки. Многие прикладные модели в экономике сводятся к ЗЛП. Практически все ЗЛП можно решить, используя ту или иную модификацию симплексного метода. Однако существуют более эффективные вычислительные процедуры решения некоторых типов ЗЛП, основанные на специфике ограничений этих задач. Алгоритм метода потенциалов для закрытой транспортной задачи: 1 этапом является определение первого допустимого решения (составление начального плана поставок). Для реализации этого начального этапа имеется в свою очередь ряд методов: северо-западного угла, наименьших стоимостей (наименьшего элемента в таблице), двойного предпочтения и др. 2 этапом служат посторенние системы потенциалов и проверка полученного плана на оптимальность.  В случае неоптимальности решения переходят к 3 этапу, содержание которого заключается в реализации так называемых циклов перераспределения (проводится корректировка плана прикрепления потребителей к поставщикам), после чего переходят опять ко 2 этапу. Совокупность процедур 3 и 2 этапов образует одну итерацию; эти итерации повторяются, пока план перевозок не окажется оптимальным по критерию. 

6. Метод потенциалов  в решении распределительных  задач (определение  первого допустимого  решения, оценка  полученного решения,  нахождение нового  допустимого решения) – из тетради. Определить оптимальный план распределения продукции между поставщиками и потребителями, при котором запасы поставщиков используются, спрос потребителей удовлетворяется и достигаются минимальные затраты на поставку продукции. 1. определение 1 допустимого решения. Первоначально распределить продукцию можно методом наименьшего элемента в таблице. Распределение начинаем с наименьших затрат на поставку продукции, затем по возрастающей. Поставка по дополнительным каналам проводится в последнюю очередь. Проверка условий: 1.сумма поставок по строке должна быть равна величине запасов. 2.сумма поставок по столбцу должна быть равна потребности. 3.число заполненных клеток должно быть равно m+n-1=4+4-1=7(заполненные базисные клетки). Если число заполненных клеток меньше, то по любой свободной клетке ставится поставка 0 и клетка считается базисной. 2. оценка полученного решения. По заполненным клеткам определяются потенциалы поставщиков и потребителей. Затраты на поставку продукции                      Потенциал 1-ой строки всегда =0.               По свободным клеткам определяется оценка чистого эффекта. План в задаче на минимум считается оптимальным, если все оценки чистого эффекта положительны. Если имеется отрицательная оценка чистого эффекта, следовательно, решение неоптимально. 3. нахождение нового допустимого решения. Для клетки с наименьшей отрицательной оценкой будет осуществляться перепоставка продукции. Цикл – замкнутый набор базисных клеток, для которых прямые, выходящие из клетки цикла, образуют прямой угол, и в каждой строке и столбце может быть только 2 клетки цикла. Для клетки с оценкой W21=-1 осуществим перепоставку продукции. Строим цикл. Клетки цикла нумеруем. Объем перепоставки определяется как минимальный объем поставки в четных клетках цикла. Объем перепоставки к нечетным клеткам цикла – прибавляем, из четных – вычитаем. Проверяем сумму поставок по строкам и по столбцам и число заполненных клеток. 

5. Анализ полученного решения ЗЛП. 1. анализ основных базисных переменных. Определяется оптимальное решение задачи. (например – оптимальный план предполагает производство ковра «Силуэт», 30 шт. и ковра «Детский», 10 шт., максимальная стоимость продукции составит 150 т.р.). 2. анализ основных небазисных переменных. Определяются переменные, которые не входят в оптимальный план, степень неэффективности вида деятельности характеризует оценка чистого эффекта. (например – х1 и х4=0 следовательно производство ковра «Дымка» и «Лужайка» неэффективно,W1=-7 означает, если производить одну единицу ковра «Лужайка», то целевая ф-я, т.е. стоимость продукции снизится на 7 т.р.). 3. анализ дополнительных базисных переменных. (например – х6=200 означает, что в оптимальном плане сырье недоиспользуется на 200 кг.). 4. анализ дополнительных небазисных переменных. Определяется эффективность использования ресурсов или производства продукции.(например – х5, х7=0 означают, что в оптимальном плане недоиспользования труда и оборудования нет. Данные ресурсы полностью используются.W5=-4\3 означает, если недоиспользовать труд на 1 ед-цу, то стоимость продукции снизится на 4 т.р.) 

4. Экономическое содержание симплекс-метода линейного программирования (определение первого допустимого решения, оценка полученного решения, нахождение нового допустимого решения) – вариант 1. Универсальным методом решения ЗЛП явл. симплекс-метод. Суть его заключается в том, что в начале получают допустимый вариант, удовлетворяющий всем условиям, но не обязательно оптимальный. Оптимальность достигается последующим улучшением исходного варианта за определенное число этапов, т.е. итераций. Направление перехода от одного решения к другому выбирается на основе критерия оптимальности. Сначала приводится к системе уравнений, т.е. к каноническому виду. В неравенство типа меньше либо равно вводится дополнительная переменная в левую часть в коэффициентом +1 и означает, возможное недоиспользование ресурсов. В неравенство больше либо равно дополнительная переменная включается в правую часть с коэффициентом +1 и означает сверхплановое производство\сверхплановую реализацию продукции. Существует два вида симплекс-метода: 1. симплекс-метод с естественным базисом. ЗЛП формулируется в канонической форме, при этом матрица коэффициента при неизвестных в системе уравнений должна содержать единичную подматрицу. В этом случае определяется первоначальный план, проверка на оптимальность полученного плана проводится с помощью критерия оптимальности, а переход к новому решению с помощью ряда преобразований. Полученный план снова проверяется на оптимальность, процесс заканчивается за конечное число этапов, причем на последнем выявляется неразрешенность задачи, любой оптимальный план. 2. симплекс-метод с искусственным базисом. Используется, когда затруднительно определить план ЗЛП, записанной в канонической форме. В левую часть системы уравнений добавляется искусственная переменная У с коэффициентом +1, чтобы полученная матрица коэффициентов, при неизвестных, содержала единичную подматрицу. В целевую ф-ю У включаются с коэффициентом +М (если задача решается на минимум) и –М (если задача решается на максимум). У означает невыполнение соответствующего ограничения. В полученной задаче определяется первоначальный план, при решении задачи целевая функция будет зависеть от величины М. В процессе решения искусственные переменные надо исключить из симплексной таблицы по мере их выхода из базиса, т.е. из допустимого решения. Если все искусственные переменные У вышли из базиса, то можно определить оптимальное решение. Если решение содержит переменную У, то задача неразрешима. Дополнительные переменные входят в целевую ф-ю с коэффициентом 0. 

4. Экономическое содержание симплекс-метода линейного программирования (определение первого допустимого решения, оценка полученного решения, нахождение нового допустимого решения) – вариант 2. 1. Определение 1 допустимого решения. Систему неравенств с помощью дополнительных переменных приводим к системе уравнений. В каждом уравнении должна иметься переменная, которая участвует только в данном уравнении и имеет коэффициент К+1, она будет базисной и равной правой части уравнения. Все остальные неизвестные небазисные =0. совокупность полученных значений неизвестных определяет 1-ое допустимое решений задачи. Решение задачи произ-ся в симплексных таблицах. На пересечении строк и столбцов указываются коэффициенты  замещения а  , которые берутся из системы уравнений.

2. Оценка полученного решения. По небазисным переменным определяется оценка чистого эффекта.

При решении  задач на максимум план оптимален, если все оценки чистого эффекта отрицательны. Wжитое показывает на сколько измениться значение целевой функции, если значение житой переменной принять =1 и включить ее в базис. Имеются положительные оценки чистого эффекта, решение не оптимально. 3. Нахождение нового допустимого решения. Определяем переменную,    которая войдет в базис по разрешающему столбцу. Жи со звездочкой равно максимум W житая. Переменная, которая выйдет из базиса, определяется по разрешающей строке, как минимальное симплексное отношение значений х нулевое к положительным коэффициентам замещения по разрешающему столбцу.                             На пересечении разреш-го столбца и строки, находится разреш-ий эл-т. 

3. Общая задача линейного программирования. Необходимым условием использования оптимального подхода к планированию и управлению является гибкость и альтернативность производственно-хозяйственных ситуаций, в условиях которых приходится принимать планово-управленческие решения. Суть принципа оптимальности состоит в выборе планово-управленческого решения, которое наилучшим образом учитывает внутренние возможности и внешние условия произ-ной деят-ти хоз. субъекта. Надо выбрать критерии оптимальности, т.е. экономический показатель, позволяющий сравнивать эффективность планово-управленческих решений. На выбор решения накладывается ряд условий, т.е. выбор осуществляется из некоторой ОДР. Множество задач планирования и управления решаются методами линейного программирования. В ЗЛП критерий эффективности и ограничения з-чи линейный. Если функциональные связи не линейные, то используются методы нелинейного программирования. Если решение необходимо в целых числах, то используются методы целочисленного программирования. Если рассматривается развитие эк-го процесса во времени, то исп-ся методы динамич-го прогр-я.