Ответы на вопросы по материалам курса МО

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

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

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

25.Понятие о вырождении ЗЛП. Монотонность и конечность симплекс-метода. Зацикливание.

Рассматривая симплекс-метод, мы предполагали, что задача линейного программирования является невырожденной, т.е. каждый опорный план содержит ровно m

21

положительных компонент, где m - число ограничений в задаче. В вырожденном опорном плане число положительных компонент оказывается меньше числа ограничений: некоторые базисные переменные, соответствующие данному опорному плану, принимают нулевые значения. Используя геометрическую интерпретацию для простейшего случая, когда n - m = 2 (число небазисных переменных равно 2), легко отличить вырожденную задачу от невырожденной. В вырожденной задаче в одной вершине многогранника условий пересекается более двух прямых, описываемых уравнениями вида xi = 0. Это значит, что одна или несколько сторон многоугольника условий стягиваются в точку.

Аналогично при n - m = 3 в вырожденной задаче в одной вершине пересекается более 3-х плоскостей xi = 0.

В предположении о невырожденности задачи находилось только одно значение

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

В вырожденной задаче

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

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

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

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

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

26.Пара двойственных ЗЛП в виде конечных сумм и их взаимосвязь.

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

1.Если прямая задача была задачей минимизации, то двойственная ей становится задачей максимизации, и наоборот.

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

3.Составляем матрицу коэффициентов ограничений, транспонируем её, полученная матрица будет новой системой ограничений.

4.Правые части системы ограничений – это коэффициенты целевой функции, знаки новых ограничений – противоположные исходным.

5.И наконец коэффициенты новой целевой функции – это правые части исходной системы ограничений.

Вторая двойственная задача Второй вид двойственных задач строится исходя из следующей таблицы

22

27.Постановка транспортной задачи (ТЗ) по критерию стоимости в матричной форме. Теорема о существовании допустимого плана и ее обоснование.

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

Транспортную задачу можно сформулировать следующим образом, представив ее в виде таблицы, которую называют распределительной. Распределительную таблицу называют иногда табличной или матричной моделью ТЗ.

23

Цель транспортной задачи – минимизировать общие затраты на реализацию плана перевозок.

Теорема о существовании допустимого плана Для того чтобы ТЗ имела допустимые планы, необходимо и достаточно выполнение

равенства

Модель ТЗ называется закрытой, если суммарный объем груза, имеющегося у поставщиков, равен суммарному спросу потребителей, т.е. выполняется равенство

Если для ТЗ выполняется одно из условий:

то модель ТЗ называется открытой.

28. Закрытая и открытая форма модели ТЗ. Теорема о ранге матрицы ТЗ.

Для того чтобы ТЗ имела допустимые планы, необходимо и достаточно выполнение равенства

Модель ТЗ называется закрытой, если суммарный объем груза, имеющегося у поставщиков, равен суммарному спросу потребителей, т.е. выполняется равенство

24

Если для ТЗ выполняется одно из условий:

то модель ТЗ называется открытой.

Теорема о ранге матрицы ТЗ Ранг матрицы коэффициентов при переменных в транспортной задаче на единицу

меньше числа ограничений: r(A) = m + n –1.

Доказательство:

Рассмотрим задачу с двумя поставщикам и тремя потребителями продукции

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

29.Построение опорного плана ТЗ методами «северо-западный угол», «минимальный элемент», Фогеля.

Смотреть в тетради! Последняя практика.

30.Алгоритм решения ТЗ методом потенциалов.

Алгоритм решения:

1.Приводим задачу к закрытому виду (если в этом есть необходимость)

2.Получаем исходное базисное решение. Число заполненных клеток должно быть равно m+n-1. Если число заполненных клеток меньше m+n-1, то недостающее количество клеток заполняем нулями (условные поставки)

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

ui+vj=cij

Для небазисных переменных рассчитываем оценки оптимальности, используя выражение

25

Сравниваем полученные оценки с нулем. Если они все меньше или равны 0 (для задачи на минимум), то получено оптимальное решение. Если хотя бы одна оценка больше нуля, то переходим к шагу 4.

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

31.Транспортная задача по критерию времени.

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

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

Как и в прочих транспортных задачах, закрытой задача считается при

А открытой – при невыполнении этого равенства. Как и в обычных ТЗ есть поставщики и потребители

Известны tij, i = 1, 2, …, m, j = 1, 2, …, n – время, за которое груз доставляется от каждого i – го поставщика каждому j – му потребителю.

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

Также составляется матрица перевозок, в которой теперь содержатся не тарифы перевозок, а время перевозок.

Математическая модель задачи выглядит:

T(X)=max{tij}min, при xij>0, где xij – объем перевозимого груза от i-го поставщика j-му потребителю, T(X) – время, за которое план перевозок будет полностью выполнен.

Алгоритм решения Транспортная задача по критерию времени методом приоритетных связей решается так

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

26

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

Математическая модель динамической задачи – это дифференциальное уравнение

, где T – время протекания процесса управления, Qi[x(t), U(t)] – мгновенные потери в момент времени t.

33.Общая идея динамического программирования. Принцип оптимальности и принцип погружения.

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

Примером задачи динамического программирования может служить задача нахождения минимального пути в графе.

Принцип оптимальности: оптимальное управление на каждом шаге определяется состоянием системы на начало этого шага и целью управления.

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

34.Математическая формулировка принципа оптимальности.

Принцип оптимальности Беллмана:

35.Вычислительные аспекты динамического программирования.

28