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

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

Формы записи ЗЛП В общем случае задача линейного программирования (ЗЛП) формулируется

следующим образом: найти величины х1,…, хn, доставляющие минимум (максимум) функции F(X) = c1x1 + c2x2 +…+ cnxn и удовлетворяющие ограничениям, которые могут быть только равенствами и неравенствами вида

1 1 + + ≤ , = 1, …1 1 + + ≥ , = ( + 1), …1 1 + + = , = ( + 1), …

Среди ограничений часто встречаются условия не отрицательности всех или части

=1

при условиях { 1 1 + 2 2 + + ≤ }.

Различаются еще две основные формы записи задач линейного программирования в зависимости от наличия ограничений разного типа:

а) стандартная форма ЗЛП

б) каноническая форма ЗЛП

= →

=1

При ограничениях

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

= →

=1

эквивалентна задаче поиска максимума

− = −( ) →

=1

Геометрическая интерпретация ЗЛП Совокупность ограничений-неравенств в задаче ЛП определяет некоторую

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

Основная теорема линейного программирования

1)Линейная форма z=c-T*x достигает своего минимума в угловой точке многогранника решений.

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

22

Симплекс-метод. Построение допустимого (опорного) плана. В каких случаях допустимый план не существует?

Название метода связано с тем, что первой задачей, на которой он разрабатывался, был симплекс - многогранник, заданный условиями

Основная идея симплекс - метода:

Рассмотрим основные идеи симплекс-метода. Пусть в Rn заданы n+m переменных хj, из которых первые n являются независимыми (базисными), а остальные m –зависимыми

Необходимо найти max

Алгоритм симплекс-метода включает в себя 3 этапа:

1.Приведение задачи к каноническому виду

2.Поиск опорного решения.

3.Поиск оптимального решения.

Рассмотрим более подробно построение допустимого (опорного) плана Построение опорного плана

Пусть имеется матрица канонической задачи ЛП (каноническая матрица). Прежде всего попытаемся упростить ее за счет исключения ―слабых ограничений.

Предположим, что в s-й строке все коэффициенты, включая свободный член,

неотрицательны, т.е. xn+s=|as1|x1+|as2|x2+...+|asn|xn+|bs|. Тогда при любых неотрицательных значениях xi i=1,2,...,n, xn+s>= 0. Поэтому ограничение xn+s>=0 является несущественным, и s-я

строка может быть вычеркнута из матрицы.

Выявив и исключив из канонической матрицы слабые ограничения, рассмотрим столбец свободных членов. Если все его элементы неотрицательны, то начало координат удовлетворяет всем ограничениям xi>= 0 , i=1,2,...n+m, поэтому является опорным решением задачи ЛП.

23

Если в столбце свободных членов есть отрицательные элементы, то необходимо от них избавиться, сделав шаги Жорданова исключения.

Выбираем разрешающий элемент: по столбцу – наибольший по модулю отрицательный элемент, в строке – тоже самое.

Шаг модифицированного жорданова исключения над симплексной таблицей:

1.На месте разрешающего элемента ставится 1 и делится на разрешающий элемент.

2.Остальные элементы разрешающего столбца меняют знак на противоположный и делятся на разрешающий элемент.

3.Остальные элементы разрешающей строки делятся на разрешающий элемент.

4.Все остальные элементы симплексной таблицы вычисляются по следующей формуле. Формула прямоугольника.

Если как минимум одна из вспомогательных переменных осталась в базисе, то допустимых решений данной ЗЛП не существует.

Симплекс-метод. Построение оптимального плана. Что является признаком оптимальности? Когда ЗЛП имеет множество оптимальных планов, является неограниченной?

Основную идею симплекс-метода смотреть в предыдущем вопросе.

Построение оптимального плана

24

25

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

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

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

26

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

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

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

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

= min { | > 0}

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

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

= min { | > 0}

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

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

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

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

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

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

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

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

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

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

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

27

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

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

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

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

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

28

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

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

равенства

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

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

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

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

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

29

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

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

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

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

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

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

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

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

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

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

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

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

30