- •Сутність задачі лінійного програмування (злп).Сформулюйте і складіть моделі задач "раціонального використання ресурсів" і "раціону" в загальному вигляді.
- •Означення стандартної форми злп і характеристика умов означення на можливість їх виконання.
- •Форми запису злп (розгорнута, скорочена, матрична, векторна) і основні означення (плану, оптимального плану, опорного плану, невиродженого опорного плану).
- •Поняття методу послідовного покращення плану або симплексного методу (см). Основні етапи. Побудова початкового опорного плану.
- •Оцінка оптимальності опорного плану в см (теореми оптимальності і не оптимальності опорного плану). Ознака необмеженості цільової функції.
- •Характеристика симплексної таблиці. Чому в першій симплексній таблиці в стовпцях Aj залишуються компоненти відповідних векторів.
- •Метод штучного базису (м-метод). Теорема про зв'язок оптимальних планів початкової задачі с м-задачі.
- •Сутність двоїстості в лінійному програмуванні. Зв'язок між математичними моделями двоїстих задач. Задача раціонального використання ресурсів і двоїста задача для неї, їх економічна інтерпретація.
- •Симетричні і несиметричні пари двоїстих задач. Можливі види математичних моделей двоїстих пар задач.
- •Економічна постановка і математична модель закритої транспортної задачі (тз). Властивості планів тз.
- •Економічна постановка і математичні моделі відкритих тз. Зведення їх до закритої тз. Інтерпретація додаткових змінних.
- •Характеристика методу розв'язання тз і його порівняння із см. Методи складання початкового опорного плану. Умова, при якій план перевезень буде опорним.
- •Метод потенціалів. Ознака оптимальності опорного плану. Алгоритм знаходження системи потенціалів для виродженого і невиродженого опорних планів.
- •Оцінка оптимальності опорного плану. Побудова циклу перерозподілу поставок. Перехід до другого опорного плану. Ознака неєдності розв'язку тз.
- •Сутність балансового методу і його математичного вираження в макроекономіці. Загальна схема міжгалузевого балансу виробництва розподілу продукції (мгб). Моделі мгб.
- •Характеристика основних розділів мгб. Підсумки іі-го і ііі-го розділів. Вертикальний і горизонтальний розрізи.
- •Характеристика основних параметрів мгб (коефіцієнти прямих, опосереднених та повних витрат матеріальних ресурсів). Методи їх обчислення та економічний зміст.
- •Сутність та значення економічного прогнозування. Часові ряди та їх показники динаміки. Структурні елементи динамічного ряду.
- •Означення виробничої функції та її властивості.
- •Функція Кобба-Дугласа. Обґрунтування значень параметрів а, , , при яких функція Кобба-Дугласа буде виробничою.
- •Економічні показники, обчислювані за допомогою виробничої функції.
Поняття методу послідовного покращення плану або симплексного методу (см). Основні етапи. Побудова початкового опорного плану.
Рассматривалось рациональное использование идеи о переборе угловых точек: если известны какая-нибудь угловая точка (опорный план) и значение целевой функции в ней, то все угловые точки, в которых целевая функция принимает худшие, т.е. большие значения (рассматриваем ЗЛП на минимум целевой функции), заведомо не нужны. Поэтому естественно найти способ перехода от одной угловой точки (опорного плана) к лучшей, от не – к еще лучшей и т.д. В этом и заключается суть симплексного метода (СМ). Таким образом, можно ввести следующее его понятие. СМ – это вычислительная схема, позволяющая при наличии начального опорного плана направленно перебирать опорные планы до тех пор, пока не будет найден оптимальный план или установлено, что ЗЛП не имеет решения.
Существует 4 этапа процедуры СМ: 1) построение начального опорного плана; 2) оценка оптимальности плана; 3) оценка разрешимости ЗЛП; 4) переход от одного опорного плана к лучшему.
Построение начального опорного плана. СМ применим для решения ЗЛП, заданных в каноническом виде. При этом будем рассматривать реализацию алгоритма СМ на ∂ВМ, когда среди соответствующих векторов имеются ортонормированный базис или он построен искусственным образом (М-метод). Итак, рассмотрим ЗЛП, у которой среди соответствующих векторов имеется ортонормированный базис.
Опишем построение начального опорного плана. Пусть ортонормированный базис образует первые m векторов. Тогда ЗЛП имеет вид:
Выпишем соответствующие векторы: ; ; …; ; ; …; .
Переменные, соответствующие векторам, образующим ортонормированный базис, называются базисными. Переменные, соответствующие векторам, не вошедшим в базис, наз. свободными. Если векторы образуют базис, то переменные – базисные, а переменные – свободные. По определению невырожденного опорного плана, базисные переменные должны быть положительными, а свободные – нулевыми. Приравняем в основной системе ограничений переменные к нулю, тогда базисные переменные примут значения Таким образом, получен начальный опорный план:
Оцінка оптимальності опорного плану в см (теореми оптимальності і не оптимальності опорного плану). Ознака необмеженості цільової функції.
Числа называются оценками векторов или оценками плана.
Нетрудно показать, что оценки базисных векторов равны нулю. Действительно, пусть входит в базис, т.е. Тогда для него разложение приобретает вид: . И соответственно:
Теорема (признак неоптимальности невырожденных опорных планов): если для некоторого опорного невырожденного плана существует вектор с положительной оценкой , то не является оптимальным планом, т.е. можно построить план , e – я компонента которого больше нуля и для которого
Теорема (достаточный признак оптимальности опорных невырожденных планов): если для некоторого опорного плана оценки всех векторов неположительны ( ), то - оптимальный план.
Данная теорема справедлива и для вырожденных планов. Если же - невырожденный опорный план, то достаточный признак оптимальности является и необходимым.
Признак неограниченности целевой функции: если для некоторого опорного плана существует вектор , оценка которого положительна и все коэффициенты его разложения по базису неположительны, то целевая функция неограниченна снизу, ЗЛП решения не имеет.
Сутність процесу переходу від одного опорного плану до іншого опорного плану, його економічна інтерпретація в термінах задачі раціонального використання ресурсів. Зміст оцінок оптимального плану.
Выполнив все указанные преобразования для вектора и , удовлетворящего , получим план , который может содержать m+1 положительных компонентов, и, следовательно, в этом случае не будет опорным. Для того, чтобы был опорным, необходимо, но не достаточно, обратить в ноль хотя бы одну из его компонент. Выберем из условия Очевидно, что это можно сделать только в том случае, когда т.е. среди коэффициентов разложения по базису хотя бы один положительный.
Предположим, что минимум в достигается при i=k. Это означает, что и . При подстановке в k-я компонента его обратится в ноль, т.е. .
Таким образом, получим план , содержащий не более m положительных компонент. Он будет опорным, если векторы линейно независимы.
Итак, векторы образуют новый базис, который получен из прежнего введением и выведением . Каждому базису соответствует опорный план, т.е. задачу перебора опорных планов можно решать, перебирая базисы.
Условие, позволяющее ввести в базис вектор , состоит в том, чтобы хотя бы один из его коэффициентов разложения по базису был положительным: В противном случае план всегда будет содержать m+1 положительных компонент и не будет опорным. Выбирая различные , можно построить различные планы.
По оценкам векторов проверяется оптимальность плана. Если все оценки , то, как следует из теоремы о достаточном признаке оптимальности опорных невырожденных планов, план оптимальный. Если среди оценок есть положительные, то, как следует из теоремы о признаке неоптимальности невырожденных опорных планов, план неоптимальный. При этом необходимо перейти к новому опорному плану, т.е. к новому базису, причем в большинстве случаев наиболее целесообразно вводить в базис вектор с наибольшей положительной оценкой.