Управление технологическими процессами


Математическая задача линейного программирования



страница10/16
Дата10.05.2018
Размер1.04 Mb.
ТипКонспект
1   ...   6   7   8   9   10   11   12   13   ...   16

2.2. Математическая задача линейного программирования

2.2.1. Основная математическая задача


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

Индекс j=1, 2, ... , n обозначает j-й тип технологического процесса, xj – его объем или интенсивность; xj  0. Ограниченные ресурсы обозначаются термином «ингредиент» и обозначаются индексом i=1, 2, ..., m. Коэффициент пропорциональности обозначается через aij, знак зависит от того, потребляется или производится ингредиент. Параметр bi, если он положителен, обозначает количество i-го ингредиента, поступающего в систему из внешних источников; если отрицателен – то обозначает количество i-го ингредиента, производимое системой.

Зависимости между xj выражаются в виде системы m линейных уравнений:

a11x1+a12x2+...+a1nxn=b1,

a21x1+a22x2+...+a2nxn=b2,

………………………



am1x1+am2x2+...+amnxn=bm,

где xj  0 ( j=1, 2, …, n).

Цель состоит в выполнении этих требований так, чтобы общая стоимость была минимальна. Стоимость может измеряться в денежном исчислении, числом включенных в процесс людей или количеством использованного дефицитного ресурса. Общая стоимость z есть линейная функция интенсивностей (целевая функция):

с1x1+с2x2+...+сnxn= z.

Канонической системой с упорядоченным подмножеством переменных, называемых базисными, является такая система, где для каждого i m i-я базисная переменная имеет единицу в i-м уравнении и нулевые коэффициенты в других уравнениях.



x1 + а1m+1xm+1 + … + а1nxn= b1,

x2 + а2m+1xm+1 + … + а2n xn= b2,.

……………………………….



xm + аmm+1xm+1 + … +аmnxn= bm.

Частное решение, полученное путем приравнивания независимых переменных нулю и нахождения зависимых переменных, называется базисным решением:



x1=b1; x2=b2; …; xr = bm; x r+1=x r+2 =.....= xn = 0.

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

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

2.2.2. Симплекс-алгоритм при заданном начальном допустимом базисном
решении


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

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

Итерационный процесс состоит из трех шагов.

1. Найти переменную для включения в базис.

Переменные xm+1, ..., xm являются небазисными.

Находим наименьший из коэффициентов c'm+1, …, c's, …, c'n. Пусть это коэффициент c's. Если c's < 0, то увеличение xs приведет к убыванию функции z. В связи с этим принимается соглашение, что если некоторые коэффициенты c'j отрицательны, то из них следует выбрать наибольший по модулю коэффициент. Это разумно, но несущественно, поскольку подходит любое отрицательное значение c'j. Если все c's  0, то значение функции z не может быть уменьшено, и минимум найден.

2. Найти переменную для исключения из базиса.

Насколько можно увеличивать xs, не нарушая условия неотрицательности текущих базисных переменных? Если в i-м ограничении аis > 0, то наибольшее значение, которое может принимать xs равно b'i/a'is, иначе переменная xi станет отрицательна. Если аis  0, то при увеличении xs базисная переменная xi будет возрастать. Таким образом, xs может увеличиваться до значения .

Если этот минимум находится в строке r, то xr обращается в нуль, когда xs принимает значение b'r/a'rs.

Другие базисные переменные останутся неотрицательными. Элемент a'rs называется ведущим элементом, строка r – ведущей строкой, а столбец s – ведущим столбцом.

3. Построить новую каноническую форму.

Теперь новый базис x1, x2, ..., xs, ..., xm. Переменная xs стала базисной. Чтобы построить новую каноническую форму, коэффициент при xs в ведущей строке сделаем равным 1, поделив строку на ars, чтобы образовать новую ведущую строку. Затем удалим xs из других ограничений. Для этого из i-й строки (ir) с xs с коэффициентом a'is при xs вычтем a'is  (новая ведущая строка). Чтобы преобразовать целевую функцию с коэффициентом c's ( < 0) при xs, вычтем c's  (новая ведущая строка) из строки, соответствующей целевой функции.

Теперь, построив новую каноническую форму, необходимо вернуться к шагу 1 и выбрать минимальное из чисел cj. В конце концов мы обнаружим, что все они положительны; это и будет означать, что минимум функции z достигнут.

Блок-схема симплекс-алгоритма представлена на рис. 11.



Рис. 11. Блок-схема симплекс-алгоритма


2.2.3. Порождение начального базисного допустимого решения
в симплекс-методе


На первом шаге симплекс-метода в стандартную форму вводятся искусственные переменные и искусственная целевая функция, равная сумме введенных искусственных переменных. Получающаяся вспомогательная задача является задачей в канонической форме. С этого момента применяется симплекс-алгоритм. Он состоит из ряда ведущих операций, объединенных в этап 1, которые производятся с последовательностью различных канонических форм. Целью этих действий является нахождение допустимого решения, если оно существует. Если последняя каноническая форма имеет допустимое решение, то искусственная функция равна нулю, а следовательно, равны нулю искусственные переменные. Искусственные переменные исключаются и вторично применяется симплекс-алгоритм к полученной канонической форме с исходной целевой функцией. Эта группа операций объединяется в этап 2. Цель этого этапа состоит в нахождении оптимального решения, если оно существует.

Вопросы для самопроверки:

1. Как решаются задачи методом линейного программирования?

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

3. В чем состоит современный подход к производственным операциям некоторого предприятия

4. Какие противоречивые факторы действуют в задаче производства и хранения?

5. Какие факторы действуют в задаче снабжения инструментами?

6. Какой параметр минимизируется в задаче снабжения инструментами?

7. Что такое «каноническая система уравнений»?

8. В чем отличие симплекс-алгоритма от симплекс-метода?

9. Какие действия включает симплекс-алгоритм?


Каталог: general information -> institutes -> engineering institute -> department of quot mechanical engineering quot -> educational-methodical-activity
educational-methodical-activity -> Конспект лекций Омск 2007 удк
educational-methodical-activity -> Математическое моделирование элементов конструкции и технологического процесса механической обработки детали на основе теории графов
educational-methodical-activity -> Конспект лекций ч. 1 Омск
general information -> Тесты для аспирантов (общие вопросы философии науки) Базовый уровень
general information -> Программа вступительного экзамена по специальности


Поделитесь с Вашими друзьями:
1   ...   6   7   8   9   10   11   12   13   ...   16


База данных защищена авторским правом ©znate.ru 2019
обратиться к администрации

    Главная страница