В. И. Векленко экономико-математические
Скачать 2.89 Mb.
|
^ М-метод заключается в приложении правил симплекс-метода к М-задаче, которая строится на исходной добавлением к левой части системы уравнений в канонической форме исходной ЗЛП единичных векторов неотрицательных искусственных переменных. В целевую функцию исходной задачи при решении на максимум добавляется произведение числа (- М) на сумму искусственных переменных, где М – достаточно большое положительное число. При применении к М-задаче симплекс-метода оценки  j будут зависеть от «буквы М». Поскольку М – достаточно большое положительное число, из базиса будут выводиться в первую очередь искусственные переменные. В процессе решения М-задачи в симплекс-таблице следует вычеркивать искусственные векторы по мере их выхода из базиса. Если все искусственные векторы выделены из базиса, то получаем допустимое решение. Если оптимальное решение М-задачи содержит искусственные векторы или М-задача неразрешима, то исходная задача не имеет допустимых решения.Рассмотрим числовой пример М-метода. Найти максимум целевой функции: max f(  )=3xl+2х2+х3 при условиях:2х1+х2=8, х1+х2+х3=6, х1  0, х20, х30Решение. Матрица условий исходной задачи содержит только один единичный вектор, добавим один искусственный вектор (искусственную неотрицательную переменную y1 в первое ограничение). Построим М-задачу: найти максимум целевой функции max f( ) = 3х1 + 2х2 + х3 - Myl при условиях:2х1+х2+y1=8, х1+х2+х3=6, х1 0, х20, х30, y10.М-задачу решаем симплекс-методом. Начальный опорный план (0,0,6,8). Решение проводим в симплекс-таблицах (табл. 7). Таблица 7 – Решение задачи ЛП М-методом
В начальной таблице наименьшее  j соответствует переменной х1 – она вводится в базис, а искусственная переменная y1 из базиса выводится, так как ей отвечает наименьшее симплексное отношение. Столбец, соответствующий х1, из дальнейших симплексных таблиц вычеркивается.Полученное решение является допустимым планом исходной задачи. Для него все j 0, поэтому он оптимальный. Следовательно, получен оптимальный план исходной задачи (4,0,2), максимальное значение целевой функции f (X*) = 14.Лекция4. ЭКОНОМИКО-МАТЕМАТИЧЕСКИЙ АНАЛИЗ ^ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Из теории двойственности следует, что с каждой задачей линейного программирования сопряжена другая линейная задача, называемая двойственной. По отношению к ней первоначальная задача называется исходной или прямой. Диалектическое единство исходной и двойственной задач заключается в том, что решение одной из них может быть получено непосредственно из решения другой. Прямая задача может быть записана следующим образом:  (1)  (2)  (3)Переменные двойственной задачи yi называют объективно обусловленными оценками, или двойственными оценками. Модель двойственной задачи имеет вид:  (4)  (5)  (6)Каждая из пары двойственных задач является самостоятельной задачей линейного программирования и может быть решена независимо от другой. Однако в оптимальном плане одной из задач находится решение двойственной к ней задачи. Двойственная по отношению к исходной задача составляется по следующим правилам: 1) Целевая функция исходной задачи (1) формулируется на максимум, а целевая функция двойственной задачи (4) – на минимум. В задаче на максимум все неравенства в функциональных ограничениях имеют вид  , а в задаче на минимум – вид . 2) Матрица  ,составлена из коэффициентов при неизвестных в системе ограничений исходной задачи (2), аналогичная матрица в двойственной задаче получается транспортированием:  .3) Число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи (2), а число ограничений в системе двойственной задачи (5) – числу переменных в исходной задаче. 4) Коэффициентами при неизвестных в целевой функции двойственной задачи (4) являются свободные члены в системе ограничений исходной задачи (2), а правыми частями в ограничениях двойственной задачи (5) – коэффициенты при неизвестных в целевой функции исходной задачи (1). 5) Каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения. При этом ограничению, записанному в виде неравенства , соответствует переменная, связанная условием неотрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая переменная двойственной задачи может принимать как положительные, так и отрицательные значения.В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной – в виде неравенств, причем в последней переменные могут быть и отрицательными. В симметричных задачах система ограничений как исходной, так и двойственной задачи задается неравенствами, причем на двойственные переменные налагается условие неотрицательности. ^ 1. Если прямая и двойственная задачи имеют оптимальные решения, то значения целевых функций в их оптимальных планах совпадают: max f(  ) = min g( ) .2. Если прямая задача имеет допустимые решения, а ее целевая функция не ограничена сверху, то двойственная задача не имеет допустимых планов. 3. Если двойственная задача имеет допустимые решения, а целевая функция не ограничена снизу, то прямая задача не имеет допустимых решений. 4. Обе из рассматриваемых задач не имеют допустимых решений. Вторая теорема двойственности утверждает правила дополняющей нежесткости. Пусть = (xl,x2,...,xn) – допустимое решение прямой задачи (1)-(3), а = (y1, y2,...,ym) – допустимое решение двойственной задачи (4)-(6). Для того чтобы они были оптимальными решениями соответствующих взаимодвойственных задач (1)-(3) и (4)-(6), необходимо и достаточно, чтобы выполнялись следующие соотношения:   , (7)  . (8)Условия (7) и (8) позволяют по данным оптимального решения одной из взаимодвойственных задач найти оптимальное решение другой задачи. ^ Конкретными экономическими свойствами оценок yi оптимального плана является: Свойство 1. Оценки как мера дефицитности ресурсов и продукции. Свойство 2. Оценки как мера влияния ограничений на функционал. Свойство 3. Оценки как инструмент определения эффективности отдельных вариантов. Свойство 4. Оценки как инструмент балансирования суммарных затрат и результатов. Экономическое истолкование оценок есть интерпретация их общих экономико-математических свойств применительно к конкретному содержанию задачи. Не использованный полностью в оптимальном плане ресурс получает нулевую оценку. Нулевая оценка ресурса свидетельствует о его недефицитности. Ресурс недефицитен не из-за его неограниченных запасов (они ограничены величиной bi), а из-за невозможности его полного использования в оптимальном плане. Так как суммарный расход недефицитного ресурса меньше его общего количества, то план производства им не лимитируется. Данный ресурс не препятствует и дальше максимизировать целевую функцию f(  ).Ограничивают целевую функцию дефицитные ресурсы. В рассматриваемой сельскохозяйственной задаче – пашня и механизированные работы. Они полностью использованы в оптимальном плане. Оценка таких ресурсов положительна (у1 =1; y3 =0,75). Трудовые ресурсы имеют нулевую оценку (у2=0), они недефицитны. Оценка ресурса показывает, на сколько изменится критерий оптимальности при изменении количества данного ресурса на единицу. Для недефицитного ресурса оценка равна нулю, поэтому изменение его величины не повлияет на критерий оптимальности. Дефицитность ресурса измеряется вкладом единицы ресурса в изменение целевой функции. Если в хозяйстве будет возможность приобрести дополнительно 1 га пашни, то при его использовании стоимость продукции возрастет на 1 тыс. руб. Увеличение механизированных работ на 1 усл. га позволит произвести дополнительно продукции на 750 руб. Величина двойственных оценок в данном случае может служить предельной ценой, которая приемлема при покупке ресурсов. Двойственные оценки могут быть использованы для определения эффективности производства других видов продукции, которые не входили в условия задачи. Например, если производство картофеля требует в расчете на 1 га посадки: 1 га пашни, 100 чел. – дн., 10 усл. га, то стоимость реализованной с 1 га продукции для целесообразности возделывания этой культуры должно быть не менее:  тыс. руб.^ симплексной таблице Для анализа используем результаты решения сельскохозяйственной задачи с ограничениями по трем ресурсам (табл. 8). Таблица 8 – Последняя симплексная таблица для сельскохозяйственной задачи с тремя ресурсами
При решении задачи на максимум характеристики строки оценок  (двойственные оценки), взятые с противоположным знаком, показывают изменения целевой функции при введении в базис небазисной переменной с единичной интенсивностью. Если в базис будет введена переменная х3=1, это значит, что 1 га пашни будет недоиспользован. При этом значении базисных переменных изменятся на величину коэффициентов замещения, находящихся в столбце симплексной таблицы с переменной х3. Знаки этих коэффициентов, по аналогии со знаком двойственной оценки, должны быть изменены на противоположные: =30-30=0 =1+0,5=1,5 =4-1,5=2,5 =4 2,5+10 1,5=25 =25-26=-1В противоположной ситуации, когда в хозяйстве будет возможность использовать дополнительно 1 га пашни, значение целевой функции и базисных переменных изменится на величину коэффициентов замещения, взятых с прямыми знаками:  =4+1,5=5,5 =1-0,5=0,5 =30+30=60 =45,5+101,5=27 =27-26=1Выполнение ограничений:
5,5 га + 0,5 га = 6 га (вместе 5 га)
30 чел. – дн. 5,5 га +150 чел. – дн. 5,0 га = 240 чел. – дн. Недоиспользование трудовых ресурсов составило: 300 чел. – дн. – 240 чел. – дн. = 60 чел. – дн. (х4=60). 3. По механизированным работам: 4 усл. га 5,5 га + 12 усл. га0,5 га=28 усл. гаПри изменении объема ресурсов на несколько единиц коэффициенты замещения в процессе пересчета значений базисных переменных увеличиваются в соответствующее количество раз. При увеличении ресурсов коэффициенты замещения, имеющие отрицательное значение, будут снижать значение соответствующей базисной переменной. То значение дополнительного объема ресурсов, при котором значение базисной переменной достигнет нуля, будет предельным, поскольку при нулевом значении базисная переменная становится свободной (небазисной), и состав базиса изменится. При увеличении ресурсов пашни на 2 га переменная х2 достигнет нулевого значения (2=1/0,5). Следовательно, если ресурсы пашни в хозяйстве увеличатся более, чем на 2 га, последняя симплексная таблица будет непригодной для получения новых значений базисных переменных, поскольку состав базиса изменится, а задачу нужно решить заново. При уменьшении ресурсов пашни уменьшаются базисные переменные х4 и х1. При уменьшении пашни на 1 га переменная х4 уже достигнет нулевого значения (1=30/30). По переменной х1 нулевой значение будет достигнуто при уменьшении пашни на  га ( =4/1,5). Поэтому в случае, когда уменьшается ресурс и в таблице соответствующей небазисной переменной имеется несколько положительных коэффициентов замещения, среди соотношений значений коэффициентов столбца b0 и соответствующих положительных коэффициентов в столбце с небазисной переменной, обозначающей недоиспользование рассматриваемого ресурса, выбирается минимальное, которое и укажет на максимальную величину снижения объема ресурса.Таким образом, предельное уменьшение пашни в хозяйстве может составить 1 га. Предельное изменение ресурса пашни в хозяйстве, при котором состав базисных переменных не изменится, составляет от 4 до 7 га. При увеличении объемов механизированных работ максимальное значение составит: min (30/15; 4/0,125)= 2 (усл. га), а при уменьшении: 1/0,125=4 (усл. га). Пределы изменения объемов механизированных работ, при которых можно использовать коэффициенты замещения последней симплексной таблицы для пересчета значений базисных переменных, составляют от 24 до 30 усл. га. Оптимальные размеры посевных площадей в хозяйстве приводят к недоиспользованию трудовых ресурсов на 30 чел. – дн. Поэтому уменьшение объема ресурса труда на эту величину не изменит состав базиса и значения целевой функции. Уменьшится лишь на соответствующую величину базисная переменная х4. Точно так же повлияет на решение и увеличение трудовых ресурсов с той лишь разницей, что предел увеличения отсутствует. Следовательно, объем трудовых ресурсов в хозяйстве может изменяться от 270 чел. – дн. до бесконечно большой величины. Лекция 5. РАСПРЕДЕЛИТЕЛЬНЫЙ МЕТОД РЕШЕНИЯ ^
распределительной (транспортной) задачи Практически все задачи линейного программирования можно решить, используя ту или иную модификацию симплексного метода. Однако существуют более эффективные вычислительные процедуры решения некоторых типов задач линейного программирования, основанные на специфике ограничений этих задач. Рассмотрим так называемую транспортную задачу по критерию стоимости, которую можно сформулировать следующим образом.   (1)  , (2) В т пунктах отправления А1, А2,...,Ат,, которые в дальнейшем будем называть поставщиками, находится аi (i = 1, 2, ..., т) единиц некоторого однородного продукта. Данный продукт потребляется в п пунктах В1, В2,…, Вn, которые будем называть потребителями; объем потребления обозначим bj (j = 1, 2, ..., п). Известны расходы на перевозку единицы продукта из пункта Ai в пункт Bj, которые равны cij и приведены в матрице транспортных расходов С = (сij). Требуется составить такой план прикрепления потребителей к поставщикам, т.е. план перевозок, при котором весь продукт вывозится из пунктов Ai в пункты Bj в соответствии с потребностью и общая величина транспортных издержек будет минимальной. Обозначим количество продукта, перевозимого из пункта Ai в пункт Bj, через xij. Совокупность всех переменных xij для краткости обозначим  , тогда целевая функция задачи представляет собой линейную форму: (3)Условия (1) означают полное удовлетворение спроса во всех пунктах потребления; условия (2) определяют полный вывоз продукции от всех поставщиков. Необходимым и достаточным условием разрешимости задачи (1) – (3) является условие баланса:  (4)^ Транспортная задача, в которой имеет место равенство (4), называется закрытой и может быть решена как задача линейного программирования с помощью симплексного метода. Однако благодаря особенностям переменных задачи и системы ограничений разработаны специальные, менее громоздкие методы ее решения. Наиболее применяемым методом является метод потенциалов, при котором для каждой i-й строки (i-го поставщика) определяется потенциал ui, а для каждого столбца j - потенциал vj. Сумма потенциалов для перевозки груза от i-го поставщика к j-му потребителю должна быть равна величине транспортных расходов cij, т.е. быть оценена с точки зрения критерия решаемой задачи: cij=vj+ui (5) Если баланс (4) не выполняется, то ограничения (1) или (2) имеют вид неравенств типа «меньше или равно»; транспортная задача в таком случае называется открытой. Для решения открытой транспортной задачи методом потенциалов ее сводят к закрытой задаче путем ввода фиктивного потребителя, если в неравенства превращаются условия (2), или фиктивного поставщика в случае превращения в неравенства ограничений (1). Рассмотрим этапы реализации метода потенциалов для закрытой транспортной задачи. Прежде всего следует отметить, что при условии баланса (4) ранг системы линейных уравнений (1), (2) равен т + п - 1; таким образом из общего числа (m n) неизвестных базисных неизвестных будет (т + п – 1). Вследствие этого при любом допустимом базисном распределении в матрице перевозок, представленной в общем виде в табл. 9, будет занято ровно т + п - 1 клеток, которые будем называть базисными в отличие от остальных свободных клеток. Коэффициент целевой функции в занятых клетках будем выделять полукругом. Первым этапом алгоритма метода потенциалов является составление начального распределения (начального плана перевозок); для реализации этого начального этапа используются методы северо-западного угла, наименьших стоимостей, аппроксимаций Фогеля. На втором этапе выполняется построение системы потенциалов на основе равенства (5) и проверка начального плана на оптимальность; в случае его неоптимальности переходят к третьему этапу, содержание которого заключается в реализации так называемого цикла перераспределения, после чего переходят опять ко второму этапу. Совокупность процедур третьего и второго этапов образует одну итерацию; эти итерации повторяются, пока план перевозок не станет оптимальным по критерию (1). Решение транспортной задачи выполняется в матричном виде. Матрица планирования приведена в таблице 9. Таблица 9 – Матрица планирования перевозок груза
^ Имеется 3 поставщика и 3 потребителя. Ресурсы 1-го поставщика составляют 10 ед. , 2-го – 8, 3-го – 13. Потребности потребителя А составляют 6 ед., Б – 14 ед., В – 11 ед. Транспортная задача закрытая. Издержки на транспортировку единицы груза с учетом расстояния между поставщиками и потребителями приведены в таблице 10. Таблица 10 - Издержки на транспортировку единицы груза от поставщиков к потребителю
Необходимо найти такой вариант грузоперевозок, чтобы суммарные издержки были минимальными. ^ Х11 – объем перевозки грузов от 1-го поставщика в потребителю А, … Хij – объем перевозки груза от i-го поставщика к потребителю j, … Х33 – объем перевозки от 3-го поставщика к потребителю В. Ограничения по объемам поставки: 1-го поставщика: Х11 + Х12 + Х13 = 10 2-го поставщика: Х 21 + Х22 + Х23 = 8 3-го поставщика: Х31 + Х32 + Х33 = 13 Ограничения по потребностям: Потребителя А: Х11 + Х21 + Х31 = 6 Потребителя Б: Х12 + Х22 + Х32 = 8 Потребителя В: Х13 + Х23 + Х33 = 13 Целевая функция: С (min) = 4 Х11 + 5Х12 + 4Х13 + 2Х21 + 3Х22 + 6Х23 + Х31 + 2Х32 + 4Х33 Данная задача отвечает всем требованиям линейного программирования. Ее можно решить симплексным методом. Однако, учитывая, что она имеет особую, довольно простую структуру, ее решают более простым распределительным методом. Первоначальный план составляют различными методами. Наиболее простой из них метод северо-западного угла.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1
1
=а1–b1 из таблицы исключается первый столбец. 
=b1 – а1. Из таблицы исключается первая строка. Похожие:
 | Курс «Экономико-математические методы и модели» посвящен современным методам количественного обоснования управленческих решений,... | | Методические указания предназначены для проведения практических занятий и выполнения домашних заданий по дисциплине «Экономико-математические... |
| Целью преподавания курса является обучение студентов основам работы с экономико-математическими моделями в управлении экономическими... | | Общая запись оптимизационной эмм (задача оптимального программирования). Основные элементы и понятия |
| Экономико-математические методы оптимизации работы с клиентами предприятия финансовой сферы | | Лабораторная работа выполняется и защищается в соответствии с утвержденным расписанием занятий |
| Номером варианта контрольной работы является последняя цифра в шифре зачетной книжки. Пример оформления контрольной работы предложен... | | Студентом выбирается вопросы по номеру в соответствии с последней цифрой зачетной книжки. (Например, если последняя цифра в зачетной... |
| Методические указания написаны в соответствии с программой курса «Математические методы решения задач» и предназначены для самостоятельного... | | «Математические начала натуральной философии», в котором он изложил закон всемирного тяготения и три закона механики, ставшие основой... |