|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Алгоритм Симплекс-метода для решения задачи линейного программирования об оптимальном использовании ресурсов.
Шаг 1. Формулировка ЗЛП (формирование целевой функции и системы ограничений). Шаг 2. Приведение задачи к канонической форме ( перевод функциональных ограничений в систему уравнений с помощью введения дополнительных базисных переменных ). Преобразовать целевую функцию к виду Z - 32 x1 - 27 x2 = 0 и добавить к системе ограничений. Это ограничение называется категориальным, потому что на его основе устанавливается критерий оптимальности.
Переменные x3, … x9 имеют смысл неиспользованных ресурсов. Переменные x10, x11 - объёмы неудовлетворённого спроса. Каждая такая переменная (x3, …x10) присутствует только в одном ограничении с коэффициентом, равным 1. • Набор переменных, где в каждом ограничении присутствует лишь одна переменная из набора и каждая переменная из набора присутствует лишь одном ограничении с коэффициентом 1, называется базисным. • Переменные набора называются базисными. • Остальные переменные – небазисными. • Здесь базисные переменные x3, x4, … x11 (на основе базисных переменных строится текущий опорный план ) • Небазисные - x1, x2 Шаг 3. Построение исходной симплекс-таблицы (получение первоначального допустимого базисного решения). • В левом столбце записываются основные (базисные) переменные, • Во 2-й строке таблицы перечисляются все переменные задачи. • Крайний правый столбец содержит свободные члены системы ограничений b1, b2, ..., bm. • В последней строке таблицы (называется оценочной или категориальной ) записываются: 1) коэффициенты целевой функции 2) значение целевой функции при текущем базисном решении.. • В рабочую область таблицы (начиная со 2-го столбца и 2-ой строки ) занесены коэффициенты aij при переменных системы ограничений.
Опорный план канонической ЗЛП - это допустимое решение ЗЛП, при котором все небазисные переменные полагаются равными 0, вследствие чего базисные переменные становятся равными правым частям ограничений. Число положительных компонент (базисных) совпадает с числом ограничений Т.о., начальный опорный план: X0 =(0; 0; 825; 480; 720; 450; 200; 40; 40; 3000; 3000). Значение целевой функции (Z0 = 32x1 + 27 x2 =0) равно нулю, так она зависит от переменных, неосновных для данного базисного решения.
Шаг 4. Проверка условия коэффициентов категориальной строки. Если отрицательные элементы отсутствуют, задача решена. оптимальное решение найдено. Если есть отрицательные элементы, то надо перейти к Шагу 5. В нашем примере в категориальной строке есть отрицательные элементы, т.е. найденное решение не является оптимальным. Шаг 5. Выбор разрешающего столбца (переменной, вводимой в базис) в соответствии со следующим условием: - Просматривается последняя (категориальная) строка симплексной таблицы и в ней отыскивается наибольший по модулю отрицательный элемент. В нашем примере он равен (-32) и расположен в столбце x1. Таким образом, разрешающим является столбец x1. Переменная x1, соответствующая найденному столбцу, войдёт в базис. Шаг 6. Проверяем элементы разрешающего столбца. - Если среди них нет положительных, то целевая функция неограниченна и решения нет Шаг 7. Выбор разрешающей строки (переменной, выводимой из базиса). - Рассматриваем только положительные элементы разрешающего столбца. - Находим частное от деления элементов столбца ограничений B (последний столбец таблицы, кроме критериального элемента) на элементы разрешающего столбца. - Разрешающей выбирается строка, для которой это частное будет наименьшим: Разрешающим оказалось 2-е ограничение, соответствующее базисной переменной x4, в котором частное равно 1600. Элемент, стоящий на пересечении разрешающей строки и разрешающего столбца, называется разрешающим. У нас разрешающим элементом оказался a21, равный 0, 3.
=>
Т.е. в базисном столбце заменяем переменную x4 на переменную x1. Шаг 8. Пересчет элементов симплекс-таблицы (переход к новому базисному решению). 1) Все элементы разрешающей строки разделить на разрешающий элемент 2) После чего преобразовать все остальные строки (неразрешающие, в ключая категориальную): Из неразрешающей строки вычесть разрешающую строку, умноженную на элемент неразрешающей строки, стоящий в разрешающем столбце. В результате чего э лементы разрешающего столбца становятся равными нулю, кроме разрешающего элемента, который равен 1
Новые базисные переменные: x3, x1, x5, x6, x7, x8, x9, x10, x11, небазисные – x2, x4.
Первое базисное решение: X1 = (1600; 0; 25; 0; 432; 130; 88, 16; 28; 1400; 3000). Значение целевой функции Z1 =51200 Далее повторять с Шага 4 до получения оптимального решения.
Шаг 4 • В последней строке таблицы есть отрицательные элементы -> решение не является оптимальным. Шаг 5. Выберем разрешающий столбец – x2, (единственный отрицательный элемент нижней строки) => Переменную x2 будем переводить в основные. Шаг 6. В разрешающем столбце есть положительные элементы, продолжаем решение. Шаг 7. Определим разрешающую строку. • Наименьшее значение частного от деления элемента bi на элемент, находящийся в разрешающем столбце – в 1-й строке – она разрешающая, переводить в неосновные (исключать из базиса) будем переменную x3. Вместо неё вводить в базис будем x2. • Разрешающий элемент a12 = 0, 2. Шаг 8. Пересчитаем элементы симплексной таблицы в соответствии с правилами, приводимыми выше. Результат пересчета представлен в таблице:
Новые базисные переменные x2, x1, x5, x6, x7, x8, x9, x10, x11, небазисные – x3, x4. Второе базисное решение: X2 = (1575; 125; 0; 0; 362; 98; 79, 16; 26; 1425; 2875). Значение целевой функции Z2 =53775 Шаг 4 симплекс-алгоритма. В последней строке Таблицы есть отрицательный элемент (Столбец X4) => полученное решение не является оптимальным, необходимо продолжить решение. Шаг 5. Выберем разрешающий столбец – X4. Переменную x4 будем переводить в основные. Шаг 6. В разрешающем столбце есть положительные элементы, продолжаем решение. Шаг 7. Определим разрешающую строку. Наименьшее значение частного от деления элемента bi на элемент, находящийся в разрешающем столбце – в 4-й строке – она разрешающая, переводить в неосновные (исключать из базиса) будем переменную x6. Вместо неё вводить в базис будем x4. Разрешающий элемент a44 = 2. Шаг 8. Пересчитаем элементы симплексной таблицы в соответствии с правилами, приводимыми выше. Результат пересчета представлен в таблице:
Новые базисные переменные x2, x1, x5, x4, x7, x8 , x9, x10, x11, небазисные – x3, x4. Третье базисное решение: X3 = (1250; 667; 0; 65; 95; 0; 53, 17; 21; 1750; 2333). Данное базисное решение является оптимальным, так как в критериальной строке отсутствуют отрицательные элементы.. Значение целевой функции Z3 =58000 Таким образом, для получения максимальной прибыли надо произвести: печенья - 1250 кг, бисквитов – 667 кг. Выручка при этом составит 58000 руб. Так как x3=0 и x6=0, то 1-й и 4-й ресурсы расходуются полностью, и 1-е и 4-е ограничения обращаются в верные равенства, остальные ресурсы расходуются не полностью, и соответствующие ограничения образаются в строгие неравенства:
=> (3)
Теоремы двойственности. Теоремы двойственности устанавливают связь между оптимальными планами взаимно двойственных задач. Теорема 1. Если одна из двойственных задач имеет конечный оптимум, то другая также имеет конечный оптимум, причем экстремальные значения целевых функций совпадают:
Т.е.: прибыль предприятия П1 от реализации продукции при оптимальном плане равна оптимальным затратам на приобретение ресурсов предприятием П2. Если целевая функция одной из двойственных задач не ограничена, то условия другой задачи противоречивы.
Т.е., если компонент оптимального плана больше нуля, то при подстановке в соответствующее ограничение двойственной задачи оптимального плана это ограничение обращается в верное равенство, и наоборот.
Популярное:
|
Последнее изменение этой страницы: 2016-08-31; Просмотров: 1098; Нарушение авторского права страницы
Теорема 2 (о дополняющей нежесткости). 
Для того чтобы план и план являлись оптимальными решениями, соответственно, задач (1) и (2), необходимо и достаточно, чтобы выполнялись следующие соотношения: