- •Глава 1. Линейное программирование 3
- •Глава 2. Транспортная задача линейного программирования (тз) 68
- •Глава 3. Динамическое программирование 98
- •Глава 1. Линейное программирование
- •1.1. Математическая модель задачи линейного программирования
- •1.2. Формы записи задач линейного программирования
- •Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой
- •1.3. Геометрическая интерпретация и графический метод решения задач линейного программирования с двумя переменными
- •Алгоритм графического метода решения злп с двумя переменными
- •1.4. Графический метод решения задач линейного программирования сnпеременными
- •1.5. Симплексный метод решения задач линейного программирования
- •Алгоритм решения злп симплексным методом
- •Нахождение начального опорного плана злп ( )
- •Нахождение начального опорного плана злп методом искусственного базиса
- •Нахождение начального опорного плана злп методом Жордановых исключений
- •Шаг Жордановых исключений осуществляется по следующим правилам:
- •Исследование на оптимальность опорного плана при решении злп на
- •Переход к новому опорному плану
- •1.6. Двойственные задачи линейного программирования
- •Правила построения двойственной задачи.
- •Глава 2. Транспортная задача линейного программирования (тз)
- •2.1. Математическая модель транспортной задачи
- •Закрытая и открытая модели транспортной задачи
- •2.2. Решение транспортной задачи
- •Алгоритм решения транспортной задачи
- •Нахождение начального опорного плана методом «минимального элемента»
- •Нахождение начального опорного плана методом «северо-западного угла»
- •Нахождение начального опорного плана методом Фогеля
- •Проверка на оптимальность невырожденного опорного плана методом потенциалов
- •Переход к новому опорному плану
- •Цикл пересчета
- •Глава 3. Динамическое программирование
- •3.1. Задача оптимального распределения ресурсов
- •I этап. Условная оптимизация.
- •II этап. Безусловная оптимизация.
- •3.2. Задача об оптимальной стратегии замены оборудования
- •I этап. Условная оптимизация.
- •II этап. Безусловная оптимизация.
- •Список использованной литературы
Нахождение начального опорного плана злп методом Жордановых исключений
В случае, когда ограничение-равенство системы не имеет предпочтительного вида, его необходимо записать как 0-равенство, т.е. левую часть ограничения переносят в скобках со знаком минус в правую часть, при этом в левой части остается ноль. Если ограничение-равенство системы имеет предпочтительный вид, то предпочтительную (базисную) переменную оставляют в левой части ограничения, а все остальное из левой части переносят в скобках со знаком минус в правую часть. Переменные, которые оказались при этом в правых частях ограничений, являются свободными. Целевая функция должна быть выражена только через свободные переменные и записана в идентичном виде, т.е. от свободного члена отнимают скобку с остальными элементами целевой функции (при этом целевая функция не должна измениться).
Пусть ЗЛП имеет каноническую форму записи с неотрицательной правой частью:
где .
Если ни одно из ограничений не имеет предпочтительной переменной, то задача будет записана следующим образом:
где .
Для нахождения начального опорного плана методом Жордановых исключений необходимо исходя из вида задачи (1.18 – 1.19) заполнить таблицу Жордана и преобразовывать ее до тех пор (см. шаг Жордановых исключений), пока не будет найден начальный опорный план или пока не убедимся, что опорный план отсутствует и задача не имеет решения вследствие несовместности системы ограничений.
Таблица Жордана содержит столбцов, где– число переменных,– число предпочтительных (базисных) переменных истроки, где– число ограничений-равенств. В первом столбце «БП» записываются базисные (предпочтительные) переменные. Если ограничение не имеет предпочтительной переменной, то записывается «0». Второй столбец «1» – столбец свободных членовсистемы ограничений (1.19) а в-строке – элементиз (1.18). Остальные столбцы таблицы – «СП», в основной части которых находятся элементыиз системы (1.19). В-строке в столбцах «СП» записываются коэффициенты при свободных переменных, стоящие в скобках выражения (1.18). Каждому ограничению-равенству из системы (1.19) соответствует строка основной части таблицы. Целевой функции (1.18) соответствует последняя строка таблицы.
Исходя из вида задачи (1.18 – 1.19) заполним таблицу Жордана (табл. 1.1).
Таблица 1.1
|
|
|
|
СП |
|
|
БП |
1 |
|
… |
|
... |
|
0 |
|
|
… |
|
... |
|
... |
... |
... |
… |
... |
.... |
... |
0 |
|
|
… |
|
... |
|
... |
... |
... |
… |
... |
... |
... |
0 |
|
|
… |
|
... |
|
|
|
|
… |
|
... |
|
Преобразование таблицы называется шагом Жордановых исключений и осуществляется относительно выбранного разрешающего элемента. Разрешающий элемент выбирается среди положительных чисел основной части таблицы (которая выделена, ) по наименьшему отношению свободных членов (элементы столбца «1») к соответствующим положительным элементам столбца, выбранного разрешающим.
Пусть столбец будет разрешающим, тогда еслидля, то– разрешающий элемент.