Задача линейного программирования разрешима если

Введение Концепции и методы Концепции и геометрическая интерпретация Общая постановка задач линейного программирования Слабые и избыточные переменные Невыполнимые и Основные выполнимые решения Уравнений ограничений Оптимизация с помощью симплексных методов Сложная таблица Математика линейного программирования Вырождение искусственных переменных Формирование и решение задач Формирование задачи линейного программирования-Простое уточнение решения задачи линейного программирования для простого анализа чувствительности к изменениям в правой части ограничения EquationChanges в коэффициентах целевой функции Changes в коэффициентах ограничений EquationsAddition новых переменных Addition Большего количества ограничений EquationsClosureSelected Список текстов по линейному программированию и ExtensionsReferencesProblems

Введение

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

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

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

Термин программирование линейного программирования относится не к компьютерному программированию. А к планированию. Линейное программирование было разработано примерно в 1947 году. До появления компьютера. Когда Джордж Б. Данциг (1) признал обобщение в математике планирования и задач планирования. Развитие линейного программирования последовало за достижениями в области цифровых вычислений. И теперь проблемы. Связанные с несколькими тысячами независимых переменных и уравнений ограничений. Могут быть решены.

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

Затем будет описан метод решения с использованием больших вычислительных кодов линейного программирования. А решение задачи нефтепереработки с использованием IBM Mathematical Programming System Extended (MPSX) проиллюстрирует процедуру и даст типичные результаты. Полученные из этих больших кодов. Как только оптимальный получено решение. Будут детализированы процедуры анализа чувствительности. Использующие оптимальное решение для определения диапазонов по важным параметрам. Где оптимальное решение остается оптимальным. Таким образом. Другое решение линейного программирования не требуется.

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

Формулировка Задачи линейного программирования-Простая задача

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

Это будет включать в себя разработку целевой функции на основе затрат или прибыли процесса или установки и уравнений ограничений на основе наличия сырья. Спроса на продукцию. Ограничений мощности оборудования и возможностей преобразования. В качестве примера для иллюстрации этих процедур будет использован простой нефтеперерабатывающий завод. Также оптимальное решение будет получено с использованием большого кода линейного программирования для иллюстрации использования одного из этих типов программ. Доступных на большом компьютере. В следующем разделе оптимальное решение общей задачи линейного программирования будет расширено до анализа чувствительности. И эти результаты будут проиллюстрированы

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

На рис. 4-7 показана технологическая схема простого нефтеперерабатывающего завода. А в таблице 4-2 дано определение названия каждого из технологических потоков. На этом нефтеперерабатывающем заводе всего три технологические установки: атмосферная дистилляционная колонна сырой нефти. Установка каталитического крекинга и каталитический риформинг.

Ректификационная колонна сырой нефти разделяет сырую нефть на пять потоков: это топливный газ. Прямогонный бензин. Прямогонная нафта. Прямогонный дистиллят и прямогонный мазут. Часть прямогонной нафты перерабатывается через каталитический риформер для улучшения ее качества. То есть повышения октанового числа. Кроме того, части прямогонного дистиллята и прямогонного мазута обрабатываются через установку каталитического крекинга для улучшения их качества. Чтобы их можно было смешивать с бензином. Завод производит четыре продукта: премиальный бензин. Обычный бензин. Дизельное топливо и мазут.

Даже для этого простого нефтеперерабатывающего завода существует 33 расхода. Для которых необходимо определить оптимальные значения. Эта небольшая задача указывает на одну из трудностей больших задач линейного программирования. Постановка задачи достаточно прямолинейна. Однако существует серьезная бухгалтерская проблема. Связанная с отслеживанием большого числа переменных. сбор надежных данных для этих переменных обычно занимает много времени (9).

В таблице 4-3 приведены мощности. Эксплуатационные расходы. Технологический поток. Массовые выходы и объемные выходы для трех технологических установок нефтеперерабатывающего завода.

Они типичны для нефтеперерабатывающего завода среднего размера в районе побережья Мексиканского залива. Массовые выходы были взяты из данных Аронфски. Даттона и Тайяабхана (10) и преобразованы в объемные выходы с использованием гравитационных данных API. Операционные расходы покрывал технический отдел крупной нефтяной компании. Располагающей нефтеперерабатывающими заводами на побережье Мексиканского залива.

Характеристики качества и физические свойства технологических потоков приведены в табл.4-4, а стоимость сырой нефти и цены реализации продукции-в табл. 4-5.

Данные в таблице 4-4 были приведены Аронфским et.al (29). А затраты и цены в таблице 4-5 были получены из Нефтегазового журнала (11). Информация, приведенная в табл. 4-3, 4-4 и 4-5, необходима для построения целевой функции и уравнений ограничений для модели линейного программирования нефтеперерабатывающего завода.

Стандартной практикой является представление задачи линейного программирования для нефтеперерабатывающего завода в матричном виде. Как показано на рис.4-8.

В первой строке коэффициенты членов целевой функции перечислены в соответствии с их соответствующими переменными. Отпускные цены показаны как положительные. А затраты-как отрицательные. Поэтому задача формулируется так. Чтобы максимизировать прибыль. Эти цифры были взяты из таблицы 4-5, и было удобно объединить стоимость сырой нефти (32,00 долл. колонна атмосферной перегонки сырой нефти ($1,00/баррель). Чтобы показать общую стоимость $33,00 за баррель сырой нефти. Обработанной на рис.4-7. Следовательно. Первая строка рисунка 4-8 представляет целевую функцию. Приведенную ниже:

-33.0 СЫРОЙ + 0.01965 FGAD — 2.50 SRNRF + 0.01965 FGRF — 2.20 SRDSCC

-2.20 SRFOCC + 0.01965 FGCC + 45.36 PG + 43.68 RG + 40.32 DF + 13.14 FO Уравнения ограничений начинаются со второй строки на рис. 4-8. Они сгруппированы с точки зрения количественных и качественных ограничений на сырье и продукцию. С точки зрения производительности технологической единицы с использованием объемных выходов. А также с точки зрения разделения потока между технологическими единицами и смешивания в продукты.

Второй ряд-это ограничение доступности сырой нефти. Ограничивающее нефтеперерабатывающий завод до 110 000 баррелей в день. Далее следуют четыре ограничения по количеству и качеству. Связанные с каждым продуктом. Это ежедневные требования к производству и смешиванию и два ограничения качества. Они были извлечены из рисунка 4-8 и показаны в таблице 4-6 для четырех продуктов. Минимальное ограничение производства гласит. Что нефтеперерабатывающий завод должен производить не менее 10 000 баррелей премиального бензина в день. Чтобы соответствовать требованиям маркетингового подразделения компании. Ограничения смешивания гласят. Что сумма потоков. Идущих на производство премиального бензина. Должна равняться суточному производству премиального бензина. Ограничения качества используют линейное смешивание. И сумма каждого компонента. Взвешенная по его качеству. Должна соответствовать или превышать качество продукта. Это проиллюстрировано с премиальным ограничением смешивания октанового числа бензина. Которое записывается следующим образом. Используя информацию из матрицы:

Следующий набор информации, приведенной в матрице уравнений ограничений на рис. 4-8, представляет собой описание работы технологического агрегата с использованием объемного выхода. Приведенного в таблице 4-3. Этот раздел матрицы был извлечен и показан в таблице 4-7 для трех технологических блоков. Что касается объемных выходов для ректификационной колонны сырой нефти. То эти данные свидетельствуют о том. Что объемный расход сырой нефти в 35,42 раза превышает расход топливного газа из ректификационной колонны, т. е.:

35.42 СЫРАЯ НЕФТЬ — FGAD = 0 (4-12)Соответствующие выходы других продуктов перегонки сырой нефти определяются таким же образом. Для каталитического риформера выход табл. 4-6 Количественные и качественные ограничения для продуктов нефтепереработки топливного газа (ФГРФ) и бензина риформера (РФГ) задаются следующими уравнениями:

158.7 SRNRF — FGRF = 0 (4-13)0.928 SRNRF — RFG = 0 (4-14)Аналогичные уравнения используются в матрице, рис. 4-8, и суммируются в таблице 4-7 для установки каталитического крекинга.

Использование объемных выходов для получения линейных уравнений для описания производительности технологических агрегатов необходимо при линейном программировании. Результаты будут удовлетворительными до тех пор. Пока объемные выходы точно описывают производительность этих технологических установок. Эти объемные выходы зависят от условий эксплуатации установки. Таких как температура. Расход сырья. Активность катализатора и т. Д. Следовательно. Иметь оптимальное решение эти объемные выходы должны соответствовать наилучшей производительности отдельных технологических установок. Чтобы учесть изменения объемных выходов в зависимости от условий эксплуатации. Иногда отдельная программа моделирования соединяется с кодом линейного программирования для получения наилучших значений объемных выходов. Затем используется итерационная процедура для сближения оптимальных расходов линейного программирования с соответствующими значениями объемных выходов из программы моделирования. Рис. 6-5.)

Последняя группа терминов на рис. 4-8 дает материальный баланс вокруг точек. Где потоки разделяются между технологическими единицами и смешиваются в продукты. Поток, который будет разделен, задается коэффициентом 1, а результирующие потоки имеют коэффициент -1. Например, прямогонная нафта от перегонки сырой нефти разделяется на четыре потока. Один отправляется в каталитический риформер. А остальные три используются для смешивания премиального бензина. Обычного бензина и дизельного топлива. Уравнение для этого разбиения:

SRN — SRNRF — SRNPG — SRNRG — SRNDF = 0 (4-15)Существует в общей сложности семь расщеплений потока. Как показано на рис.4-8.

Эта информация теперь доступна для определения оптимальных условий работы нефтеперерабатывающего завода. Оптимальное решение было получено с помощью программы Mathematical Programming System Extended (MPSX). Запущенной на IBM 4341. Формат, используемый этим кодом линейного программирования. Стал отраслевым стандартом в соответствии с Murtagh (12) и не ограничивается серией кодов MPS. Разработанных первоначально для компьютеров IBM. Следовательно. Мы также опишем процедуру ввода кода из-за его более общий характер. Кроме того, мы будем использовать эти результаты нефтепереработки для иллюстрации дополнительной информации. Которую можно получить из анализа чувствительности.

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

Построив матрицу задачи линейного программирования. Мы теперь готовы решить ее с помощью большой компьютерной программы линейного программирования. Входные и выходные данные для этих программ стали относительно стандартными (12). Что делает изучение одной из них полезным при использовании любой из других. Решение простой задачи было получено с помощью расширенной системы математического программирования IBM Mathematical Programming System Extended (MPSX). Подробная документация приведено в руководствах IBM (15,16) и Murtagh(12) по использованию программы. А ниже описано ее использование для решения задачи нефтепереработки. Управляющая программа MPSX. Используемая для решения этой задачи. Приведена в таблице 4-8. Первые две команды. PROGRAM и INITIALZ. Определяют начало программы и устанавливают стандартные значения по умолчанию для многих дополнительных параметров программы. TITLE записывает символьную строку между ними кавычки вверху каждой страницы выходных данных. Четыре команды ПЕРЕМЕЩЕНИЯ дают заданные пользователем имена входным данным (XDATA). Версии задачи с внутренним машинным кодом (XPBNAME). Целевой функции (XOBJ) и вектору правой стороны (XRHS). Затем CONVERT вызывает процедуру преобразования входных данных из двоично-десятичного (BCD) или коммуникационного формата в машинный код для использования программой. И BCDOUT имеет входные данные напечатаны. Следующие три команды, SETUP. CRASH и PRIMAL. Указывают на то. Что целевая функция должна быть максимизирована. Начальная основа создана. И метод primal должен использоваться для решения проблемы. Выход из PRIMAL находится в машинном коде. Поэтому РЕШЕНИЕ вызывается для получения BCD-вывода решения. Команда RANGE используется в анализе чувствительности для определения диапазона. В котором находятся переменные.. Правые стороны. И коэффициенты могут меняться без изменения базиса. Последние два оператора. EXIT и PEND. Сигнализируют о завершении управляющей программы и возвращают управление операционной системе компьютера.

Входные данные в программу MPSX делятся на четыре раздела: ИМЯ, СТРОКИ. СТОЛБЦЫ и RHS. Первые два приведены в таблице 4-9. Раздел ИМЯ-это одна строка. Содержащая идентификатор. ИМЯ и пользовательское имя для следующего блока входных данных. (MPSX имеет положения для отслеживания нескольких проблем во время выполнения управляющей программы). Когда программа запускается. Она ищет входные данные с тем же именем, что и те. Что хранятся во внутренней переменной XDATA. Раздел СТРОКИ содержит имя каждой строке модели предшествует буква. Указывающая. Является ли она строкой без ограничений (N). Целевой функцией. Ограничением меньше или равно ограничению (L). Ограничением больше или равно ограничению (G) или ограничением равенства (E).

Раздел Это список ненулевых элементов в каждом столбце матрицы задач (рис. 4-8). Каждая строка содержит имя столбца. За которым следует до двух имен строк и соответствующих им коэффициентов из рисунка 4-8.

Последний раздел ввода показан в таблице 4-11. Здесь правые коэффициенты вводятся так же. Как коэффициенты для каждого столбца были введены в разделе COLUMS. То есть только ненулевые элементы. За концом блока данных следует карта ENDATA.

Решение задачи нефтепереработки представлено в таблице 4-12 (а) и (б). Как указано в распечатке из программы MPSX. Он разделен на два раздела. Первый из которых содержит информацию об ограничениях (строки). А второй-информацию о переменных потока очистки (столбцы).

В разделе СТРОКИ есть восемь столбцов вывода. Первый — это внутренний идентификационный номер. Присвоенный каждой строке программой. Второй столбец — это имя. Данное строкам во входных данных. Далее идет столбец AT. Который содержит пару кодовых букв для обозначения состояния каждой строки в оптимальном решении. Строки ограничений в базисе имеют код BS. Неосновные ограничения неравенства. Которые достигли своего верхнего уровня. или нижние пределы имеют код UL или LL. А ограничения равенства имеют код состояния EQ. Четвертый столбец — это активность строки. Определяемая уравнением:

Это оптимальное значение левой части уравнений ограничений. Однако он вычисляется путем вычитания переменной slack из правой части. Столбец с надписью SLACK ACTIVITY содержит значение переменной slack для каждой строки. Следующие три столбца связаны с анализом чувствительности. В шестом и седьмом столбцах показаны нижние и верхние пределы. Установленные для операций строки. Последняя колонка. ДВОЙНАЯ АКТИВНОСТЬ дает Множители Лагранжа. Которые также называются симплексными множителями. Теневые цены и неявные цены. Как будет показано далее при анализе чувствительности. Они будут соотносить изменения в деятельности с изменениями в целевой функции. Кроме того, точка в таблице означает ноль. То же самое соглашение используется в Симплексной таблице.

Изучение этого раздела выпуска показывает. Что активность (или значение) целевой функции (строка 1, OBJ) составляет 701 823,4, то есть максимальная прибыль для нефтеперерабатывающего завода составляет 701 823,40 долл. Проверяя строки. Которые находятся на своих нижних границах. LLредмет производственных ограничений. Обнаруживается. Что только строка 15, FOMIN. Находится на своем нижнем пределе в 10 000 баррелей в день. Что указывает на то. Что должно быть произведено только минимально необходимое количество мазута. Однако ряд 3, PGMIN, строка 7, RGMIN и строка 11, DFMIN, находятся выше своих нижних пределов со значениями 47 113 баррелей/день для премиального бензина, 22 520 баррелей/день для обычного бензина и 12 491 баррель/день для дизельного топлива. Подробнее об информации в этой таблице будет сказано при обсуждении анализа чувствительности.

Раздел Первые три аналогичны первым трем в разделе СТРОК, то есть идентификационный номер интервала, имя столбца и то, находится ли переменная в базисе BS или находится на его верхнем или нижнем пределе, UL или LL. Четвертая колонка. АКТИВНОСТЬ. Содержит оптимальное значение для каждой переменной. Коэффициенты стоимости целевой функции перечислены в столбце ВХОДНЫЕ ЗАТРАТЫ. УМЕНЬШЕННАЯ СТОИМОСТЬ это величина на которую будет увеличена целевая функция на единицу прироста каждой неосновной переменной и является частью анализа чувствительности. Он задается cj’ уравнения(4-29).

Для этой простой модели нефтеперерабатывающего завода было определено 33 переменные. Оптимальное значение которых было определено. И выполнено 38 уравнений ограничений. Для реального нефтеперерабатывающего завода были бы тысячи уравнений ограничений. Но они были бы разработаны таким же образом. Как описано здесь. Как видно, модель (уравнения ограничений) была простой. И рассматривался только один набор условий работы установки каталитического крекинга. Каталитического риформинга и колонны дистилляции сырой нефти.

Если оптимальные расходы не совпадают с соответствующими значениями объемных выходов. Поиск может быть выполнен путем повторения задачи для получения соответствия оптимальных расходов и объемных выходов. Это должно быть выполнено с помощью отдельной программы моделирования. Которая генерирует объемные выходы от расхода через технологические единицы. (См. Рис. 6-5) Таким образом. Линейная модель установки может быть составлена с учетом нелинейных технологических операций. Другая процедура. Последовательное линейное программирование. Использует линейное программирование также выполняется итеративно. И это будет обсуждаться в главе 6. Состояние промышленной практики. Использующей как линейное программирование. Так и последовательное линейное программирование. Описано Смитом и Боннером(13) для конфигурации новых нефтеперерабатывающих заводов и химических заводов. Расширения заводов. Экономической оценки инвестиционных альтернатив. Оценки новой технологии. Операционных планов существующих заводов. Изменения кормов. Калькуляции затрат. и распределение продукции. Оценка соглашений о переработке и обмене. Прогнозирование отраслевых тенденций и экономических последствий изменений в регулировании.

Анализ чувствительности

Получив оптимальное решение для задачи линейного программирования. Хотелось бы знать. На сколько могут измениться коэффициенты затрат. Например, до того. Как необходимо будет решить задачу. На самом деле есть пять областей. Которые следует изучить на предмет их влияния на оптимальное решение. Это:

изменения в правой части уравнений ограничений. Бичанги в коэффициентах целевой функции. Cjchanges в коэффициентах уравнений ограничений. Aijaddition новых переменных. Aijaddition большего количества уравнений ограничений. Изменения в правой части уравнений ограничений соответствуют изменениям максимальной мощности технологической единицы или доступности сырья, например. Изменения в коэффициенты целевой функции соответствуют изменениям себестоимости или цены реализации продукции. А изменения коэффициентов уравнений ограничений соответствуют изменениям объемных выходов процесса. Добавление новых переменных и уравнений ограничений соответствует добавлению новых технологических единиц на заводе. Очень важно знать. Как эти различные коэффициенты и параметры могут изменяться без каких-либо изменений. изменение оптимального решения. И это может уменьшить количество раз. Когда задача линейного программирования должна быть решена.

До проведения этого постоптимального анализа необходимо разработать некоторые предварительные математические выражения для анализа влияния указанных пяти областей на оптимальное решение. Это обратные значения оптимального базиса и множителей Лагранжа. Чтобы получить матрицу, называемую обратной к оптимальному базису, А-1, рассмотрим. Что оптимальный базис был найден ранее описанным симплексным методом. Есть m уравнений ограничений и n переменных. Заданных уравнениями 4-1a, b и c. Для удобства ненулевые переменные в оптимальном базисе были переставлены так. Чтобы перейти от 1 к m, (x1*, x2*,…,xm*, 0, 0,…, 0); и есть (n — m) переменных. Не входящих в базис. Значение которых равно нулю. Оптимальное решение этой задачи линейного программирования указано ниже. Где x* содержит только m ненулевых базисных переменных.

и

A* x* = b (4-17)Для решения для x* обе стороны приведенного выше уравнения умножают на обратный оптимальный базис A*-1, элементами которого являются bij. И получают:

x* = A-1b (4-18)Следует отметить. Что A-1 может быть получен на последнем шаге симплексного метода. Если все ограничительные уравнения требуют слабых переменных. Если нет, то она должна быть получена из исходной постановки задачи с использованием оптимального базиса. Найденного из симплексного метода.

Задача линейного программирования может быть решена классическим методом множителей Лагранжа. Однако Симплексный метод дает систематическую процедуру нахождения оптимального базиса. Найдя оптимальный базис симплексным методом. Формулировка множителя Лагранжа и обратная величина оптимального базиса будут использованы для определения влияния изменения правой части на оптимальное решение. Следовательно. Необходимо вычислить значения множителей Лагранжа следующим образом. Умножение каждого уравнения ограничения (4-1b) на множитель Лагранжа li и добавление к уравнению целевой функции (4-1a) дает следующее уравнение:

где x1-xm-положительные числа. То есть значения переменных в базисе. А xm+1-xn-ноль. То есть значения переменных. Не входящих в базис.

Для решения этой задачи классическими методами частные производные p по независимым переменным и множители Лагранжа будут установлены равными нулю. Взятие частных производных p относительно множителей Лагранжа просто дает уравнения ограничения, а взятие частных производных относительно независимых переменных xj* (j = 1, 2, …m) дает:

и xj* для j = m + 1,…n равно нулю. Так как x* является оптимальным решением.

Значения множителей Лагранжа получены из решения уравнения (4-20). Записанное в матричной нотации уравнение (4-20) имеет вид:

c + ATl = 0 (4-21). Где AT-транспонирование матрицы A.

Использование матричного тождества [AT]-1 = [A-1]T и решение для множителей Лагранжа дает:

l = -[A-1]T c (4-22)В терминах элементов. Обратных оптимальному базису bik. Уравнение (4-22) можно записать в виде:

Исходя из этого. Можно определить влияние пяти изменений на оптимальное решение. Для оценки этих изменений будет использоваться обратная оптимальному базису А-1 и множители Лагранжа. Следующий пример иллюстрирует вычисление обратного оптимального базиса и множителей Лагранжа.

Пример 4-6

Решите следующую задачу симплексным методом и вычислите обратную от оптимального базиса и множителей Лагранжа:

Maximize: 2×1 + x2 + x3 = pSubject to: x1 + x2 + x3 + x4 = 10×1 + 5×2 + x3 — x5 = 20An изначально выполнимый базис недоступен. И для его получения необходимо выполнить либо искусственные переменные. Либо алгебраические манипуляции. Алгебраические манипуляции используются для того. Чтобы x1 и x2 были переменными в базисе. В результате получается:

— x3 — 9/4×4 — 1/4×5 = p — 17½ p = 17½x1 + x3 + 5/4×4 +1/4×5 = 7½ x1 = 7½ x2 — 1/4×4 — 1/4×5 = 2½ x2 = 2½ x3 = 0 x4 = 0 x5 = 0 Это оптимум. Так как все коэффициенты неосновных переменных в целевой функции отрицательны. При известном оптимальном решении исходная задача теперь принимает вид:

Maximize: 2×1 + x2 = 17½Subject to: x1 + x2 = 10×1 + 5×2 = 20 Обратная величина оптимального базиса вычисляется с использованием метода кофактора

где || A ji || = || A ij || T. И || A ij || коэффициенты матрицы A.(8)

Множители Лагранжа вычисляются с помощью уравнения (4-22)

l = -[A-1]T c или l1= -9/4 и l2 = ¼

Изменения в правой части Уравнений ограничений

Изменения в правой части уравнений ограничений, т. Е. Изменения bi. Вызовут изменения значений переменных в оптимальном решении, xj. Чтобы оптимальное решение оставалось оптимальным. Xj не могут стать отрицательными. Уравнение (4-18) будет использоваться для оценки изменений xj. Вызванных изменениями bi. Используется j-я составляющая уравнения 4-18.

При изменении bi на величину Dbi новое значение xj*. Называемое x*j,new равно:

чтобы оптимальное решение x* оставалось оптимальным. Значения x*j,new не должны становиться отрицательными. Проблема должна быть решена,если какой-либо из x*j. New становится отрицательным.

Изменение значения целевой функции для изменения БИ вычисляется с помощью уравнения (4-19). Поскольку левая часть уравнения (4-19) в оптимуме равна нулю. Его можно записать в виде:

Используя ту же процедуру для изменения Dbi. Изменение значения целевой функции составляет:

Именно из этого уравнения множители Лагранжа получают название теневых цен. Поскольку они имеют размеры долларов за единицу и используются для вычисления нового значения целевой функции из изменений bi. Это называется расчетом предельных издержек.

Как правило. В больших компьютерных программах линейного программирования часть вычислений включает в себя вычисление x*j. New и p*new для верхних и нижних пределов bi. Кроме того. Можно вычислить значения Dbi. Которые дадут максимально возможное изменение xj*. То есть xj,new = 0. Одновременные изменения в правой части уравнений ограничений могут быть выполнены с использованием правила 100%. И эта процедура описана Bradley et al. (19).

Пример 4-7

Для задачи. Приведенной в примере 4-6, найдите новое оптимальное решение для Db1 = -5 без решения задачи. Использование уравнения (4-25) для вычисления изменений xi дает:

x1,new = x1 + b11 Db1 +b12 Db2x2,new = x2 + b21 Db1 +b22 db2 Подстановка в значения для Db1 = -5 и Db2 = 0 дает

x1,новый = 7½+ (5/4)(-5) = 5/4×2,new = 2½ + (-¼)(-5) = 15/4 Используя уравнение (4-27). Изменение целевой функции вычисляется как:

p*new = p* — [l1 Db1 + l2 Db2] = 17½ — (-9/4) (-5)p*new = 25/4 Изменения в правой части уравнений ограничений являются частью анализа чувствительности программы MPSX. В таблице 4-12(а) приведены наименьшие и наибольшие значения правой части уравнений ограничений для того. Чтобы оптимальное решение оставалось оптимальным как НИЖНИЙ ПРЕДЕЛ. Так и ВЕРХНИЙ ПРЕДЕЛ. Кроме того, были вычислены множители Лагранжа. Которые называются ДВОЙНОЙ АКТИВНОСТЬЮ в номенклатуре MPSX таблицы 4-12(а). В этой таблице NONE указывает на отсутствие привязки. А точка указывает на то. Что значение было равно нулю. Соответственно. В таблице 4-12(б) даны верхний и нижний пределы по переменным. В этом случае точка указывает. Что нижняя граница была равна нулю. И НИ ОДНА не указывает. Что не было верхней границы для переменной. Потому что ГРАНИЦЫ не использовались.

Изменение коэффициентов целевой функции

Необходимо рассмотреть влияние на оптимальное решение изменений стоимостных коэффициентов переменных в базисе и не в базисе также. Обращаясь к уравнению (4-19). Коэффициенты переменных. Не входящих в базис. Т. е. xm+1,…,xn должны оставаться отрицательными для максимизации.

Если коэффициент становится положительным из-за изменения коэффициентов затрат. Было бы выгодно. Чтобы эта переменная вошла в базис.

На значения множителей Лагранжа влияют изменения стоимостных коэффициентов переменных в базисе. Так как они связаны уравнением (4-23). Термин в скобках в уравнении (4-28) называется приведенной стоимостью(19). И этот термин удобно определить как c’j для получения уравнения. Учитывающего влияние изменения коэффициентов затрат на оптимальное решение.

где cj’ должен оставаться отрицательным. Чтобы оптимальное решение оставалось оптимальным для максимизации.

Множители Лагранжа. Liючаются из уравнения (4-29). Подставляя уравнение (4-23) для получения:

Для изменения Dcj в коэффициенте несущественных переменных затрат cj и для изменения Dck в коэффициенте затрат основных переменных ck можно показать. Что следующее уравнение имеет:

При максимизации новые коэффициенты должны оставаться отрицательными для переменных. Не входящих в базис. Чтобы оптимальное решение оставалось оптимальным, т. е.:

си-Джей, новенькая

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

Если проблема должна быть решена. Обычно удобно ввести искусственную переменную и перейти от этой точки к новому оптимальному решению. Большие коды линейного программирования обычно имеют это положение. Кроме того, они могут рассчитать диапазон значений коэффициентов затрат. При которых оптимальное решение остается оптимальным. И соответствующее влияние на целевую функцию. Используемая процедура называется правилом 100% и описана Брэдли и др.(19).

Пример 4-8

Для задачи. Приведенной в примере 4-6, вычислите эффект изменения коэффициента затрат c1 от 2 до 3 и c3 от 1 до 4, т. е. Dc1 = 1 и Dc3 = 3. Используя уравнение (4-31). Получим следующие результаты для j = 3,4,5 (так как Dc2 = 0).

c’3, new = c’3 + Dc3 — Dc1[a13b11+ a23b12]подставляя

c’3, новый = -1 + 3 — (1)[(1)(5/4) + (1)(- ¼ )] = 1c’4, new = c’4 + Dc4 — Dc1[a14b11+ a24b12]замена

c’4, новый = -9/4 + 0 — (1)[(1)(5/4) + (0)(- ¼ )] = -13/4c’5, new = c’5 + Dc5 — Dc1[a15b11+ a25b12]замена

c’5,новый = — ¼ + 0 — (1)[(0)(5/4) + (-1)(-¼)] = — ½ Может быть получено улучшение целевой функции. Для c’3 новое больше нуля. Увеличение x3 от нуля до положительного числа приведет к увеличению значения целевой функции. Однако проблему придется решать.

В программе MPSX команда RANGE и параметрика используются для нахождения диапазона. В котором переменные. Правые части и коэффициенты целевой функции и ограничений могут изменяться без изменения базиса оптимального решения. Вывод команды RANGE состоит из четырех разделов: разделы 1 и 2 для строк и столбцов на их предельных уровнях и разделы 3 и 4 для строк и столбцов на промежуточном уровне (в основе). Которые будут описаны здесь. Дополнительная информация приводится в справочниках (12, 15 и 16).

В таблице 4-13 выходные данные ДИАПАЗОНА показаны для строк ограничений на верхнем и нижнем предельных уровнях. Первые четыре столбца имеют то же значение. Что и в выводе из РЕШЕНИЯ. Следующие четыре имеют по две записи для каждой строки. НИЖНЯЯ АКТИВНОСТЬ и ВЕРХНЯЯ АКТИВНОСТЬ-это нижняя и верхняя границы диапазона значений. Которые может иметь активность строки (правая сторона). Поскольку переменная slack для строки равна нулю на предельном уровне. Верхняя и нижняя активности численно равны границам диапазона. Который правые стороны могут иметь. Две записи СЕБЕСТОИМОСТИ ЕДИНИЦЫ — это изменения целевой функции на единицу изменения деятельности при переходе от действия решения к верхней или нижней границе. Столбец, помеченный ПРОЦЕССОМ ОГРАНИЧЕНИЯ. Содержит имя строки или столбца. Которые покинут базу. Если будут нарушены границы действия. Столбец status. ATывает на состояние левой строки или столбца. Например, в строке 15 таблицы 4-13 строка ФОМИНА находится на своем нижнем пределе, ее значение активности равно 10 000, а правая сторона может принимать значения от 5 652,8 до 12 252,2 без изменения базиса. Если ФОМИН опустится ниже 5 652,8, то CCFODF покинет базу. Если ФОМИН превысит 12 252,2, то SRFODF покинет базу. Стоимость, связанная с изменением ФОМИНА. Составляет $27,18 за баррель. А прибыль уменьшается при увеличении ФОМИНА.

Аналогичная информация представлена в табл.4-14 о диапазоне. В котором несущественные действия (переменные) на верхних или нижних границах могут изменяться без вытеснения строки или столбца в ОГРАНИЧИВАЮЩЕМ ПРОЦЕССЕ из основы. В таблицу включается дополнительный столбец Если целевая функция коэффициент затрат если перейти к БОЛЕЕ НИЗКОЙ СТОИМОСТИ. То активность возрастет до ВЕРХНЕЙ АКТИВНОСТИ. Точно так же. Если его стоимость падает ниже ВЕРХНЕЙ СТОИМОСТИ. Активность будет снижена до БОЛЕЕ НИЗКОЙ АКТИВНОСТИ.

Третий раздел результатов исследования диапазона приведен в таблице 4-15. Он содержит информацию об ограничениях. Которые не находятся на своих границах и. Следовательно. Лежат в основе оптимального решения. Заголовки столбцов имеют то же значение. Что и заголовки для раздела 1, за исключением того. Что здесь переменные. Перечисленные в разделе ОГРАНИЧЕНИЕ ПРОЦЕССА. Войдут в основу. Если границы будут превышены.

Четвертый раздел, показанный в таблице 4-16, дает анализ диапазона столбцов в базисе. Как и в таблице 4-15, переменная. Перечисленная в разделе Наибольший интерес здесь представляют записи для столбцов с коэффициентами в целевой функции. Это СЫРАЯ НЕФТЬ(39), FGAD(40). SRNRF(45), FGRF(46). SRFOCC(49), FCCC(50). PG(57), RG(62). DF(67) и FO(71). Исследуя первую строку таблицы 4-16, можно обнаружить, что если коэффициент затрат станет равен — 41,15, то активность (расход сырой нефти) снизится со 100 000 до 94 572,98. Следовательно. При увеличении себестоимости сырой нефти до 40,09 долл./барр. (эксплуатационные расходы-1,00 долл./барр.) нефтеперерабатывающий завод должен снизить свою пропускную способность всего на 5,2%. Также обратите внимание. Что более низкая стоимость премиального бензина (PG) составляет 44,082, в то время как входная стоимость составляет 45,35. Если бы оптовая цена продажи премиального бензина упала до $44,08 за баррель. То заводу было бы выгодно производить 23 655 баррелей в сутки. Что почти на 50% ниже оптимального значения 47 111 баррелей в сутки. Производимого в настоящее время. Аналогичный анализ для мазута (FO) показывает. Что, вероятно. Никогда не будет выгодно добывать мазут. Так как цена продажи должна была бы увеличиться с $13,14/барр. до $ 40,32 за баррель до того. Как добыча должна быть увеличена выше минимума.

Изменения коэффициентов уравнений ограничений

Обращаясь к уравнению (4-29), видно. Что изменения в aij для неосновных переменных вызовут изменения в c’j. Чтобы оптимальное решение оставалось оптимальным. C ‘ j Чтобы оценить изменения коэффициентов уравнений ограничений aij. Требуется несколько страниц алгебраических манипуляций. Эта разработка аналогична приведенным здесь для BI и cj и подробно обсуждается Гарвином (3) и Гассом (4). А также предметом параметрического программирования, т. Е. Оценки набора диапазонов на aij. Bi и cj. Где оптимальное решение остается оптимальным. Из-за ограничений по пространству эти результаты здесь не будут приведены. Кроме того, код MPSX имеет возможность делать эти оценки. Как уже упоминалось ранее.

Добавление новых переменных

Эффект добавления новых переменных можно определить. Изменив уравнение (4-19). Если в задачу добавить k новых переменных. То в уравнение (4-19) будет добавлено k дополнительных членов. А коэффициент k-го члена равен:

Каждый из этих k членов может быть вычислен с помощью имеющейся информации. Если все они меньше нуля. То исходное оптимальное решение остается максимальным. Если уравнение (4-34) больше нуля. То решение может быть улучшено. И проблема должна быть решена. Искусственные переменные обычно используются для оценки дополнительных переменных для получения нового оптимального решения.

Добавление дополнительных уравнений ограничений

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

Пример 4-9

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

Минимизировать: x1 — 3x2Subject to: 3×1 — x2

x1 — 3×2 (+ 2×5) = c c = 03×1 — x2 + x3 (+ 2×5) = 7 x3 = 7-2×1 + 4×2 + x4 = 12 x4 = 12×1 = 0x2 = 0 При применении Симплексного метода x2 входит и x4 покидает базис.

Выполнение алгебраических манипуляций дает:

— 0.5×1 + 0.75×4 (+ 2×5) = c + 9 c = -9 2.5×1 + x3 + 0.25×4 (+ 2×5) = 10 x3 = 10 — 0.5×1 + x2 + 0.25×4 = 3 x2 = 3×1= 0x4= 0 Когда применяется Симплексный метод. X1 входит и x3 покидает базис. Давая следующие результаты:

0.2×3 + 0.8×4 (+ 2.4×5) = c + 11 c = -11×1 + 0.4×3 + 0.1×4 (- 0.8×5) = 4 x1 = 4 x2 + 0.2×3 + 0.3×4 (+ 0.4×5) = 5 x2 = 5×3= 0x4= 0 Получено оптимальное решение. При котором все коэффициенты переменных в целевой функции (не в базисе) положительны.

Вычислим инверсию оптимального базиса А-1 и множителей Лагранжа. Получив оптимальное решение следующим образом:

Для множителей Лагранжа используется уравнение (4-22) :

l = — [A-1]T · и подстановка дает

Если первое уравнение ограничения изменяется следующим образом путем добавления другой переменной x5:

3×1 — x2 + 2×5:

x1 — 3×2 + 2x5determine. Как это добавление новой переменной влияет на оптимальное решение. Найденное ранее. Задача линейного программирования теперь имеет следующий вид:

x1 — 3×2+ 2×5 = c

3×1 — x2 + 2×5 + x3 = 7

-2×1 + 4×2 + x4 = 12 Для определения того. Остается ли оптимальное решение оптимальным. Используется уравнение (4-34). Для этой задачи n = 4, k = 1 и m = 2, а уравнение (4-34) имеет вид:

[c5 + a1,5 l1+ a2,5 l2]подстановка дает:

x5 не находится в базисе и имеет нулевое значение.

Термины в скобках показывают решение с включенной дополнительной переменной. Как видно, коэффициент на последнем шаге такой же. Как и вычисленный по уравнению (4-34).

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

-4×1 + 3×2 + 8×5 + x6 = 10 Уравнение ограничения добавляется к набору оптимальных решений. Поэтому задача не должна быть полностью решена и является:

0.2×3 + 0.8×4 + 2.4×5 = c + 11

x1+ 0.4×3 + 0.1×4 — 0.8×5 = 4

x2 + 0.2×3 + 0.3×4 + 0.4×5 = 5

-4×1+ 3×2 + 8×5 + x6 = 10×6 используется в качестве переменной в основе из дополнительного уравнения ограничения. x1 и x2 исключаются из добавленного уравнения ограничения алгебраической манипуляцией и дают:

0.2×3 + 0.8×4 + 2.4×5 = c + 11 c = -11×1 + 0.4×3 + 0.1×4 — 0.8×5 = 4 x1 = 4

x2 + 0.2×3 + 0.3×4 + 0.4×5 = 5 x2 = 5

x3 — 0.5×4 + 10×5 + x6 = 11 x6 = 11

x4= 0 x5= 0 Найдено новое оптимальное решение. Так как все коэффициенты в целевой функции положительны. Искусственные переменные обычно использовались бы. Особенно в компьютерной программе. Чтобы дать осуществимую основу и перейти к оптимуму.

Закрытие

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

Математическая структура задачи линейного программирования была введена путем графического решения простой задачи. Решение было найдено на пересечении уравнений ограничений. Затем был представлен симплексный алгоритм. Который показал процедуру перехода от одного пересечения уравнений ограничений (базового допустимого решения) к другому и улучшения целевой функции на каждом шаге до достижения оптимального значения. дошло. Увидев симплексный метод в действии. Мы обсудили важные теоремы линейного программирования. Которые гарантировали. Что глобальный оптимум будет найден для линейной целевой функции и линейных ограничений. Затем были представлены методы. Которые проиллюстрировали. Как схема технологического процесса и связанная с ней информация могут быть преобразованы в задачу линейного программирования для оптимизации промышленного процесса. Это было проиллюстрировано на простом примере нефтеперерабатывающего завода. И решение было получено с использованием большого стандартного кода линейного программирования Mathematical Programming System Extended (MPSX) на компьютере IBM 4341. Глава была включена в обсуждение процедур постоптимального анализа. Оценивающих чувствительность решения к изменению важных параметров задачи линейного программирования. Эта чувствительность анализ был проиллюстрирован простыми примерами и результатами решения простой задачи с использованием кода MPSX.

Список избранных источников приводится в конце главы для получения дополнительной информации. Эти тексты включают следующие темы. Пересмотренный Симплексный метод представляет собой модификацию Симплексного метода. Позволяющую получить более точное и быстрое решение с помощью цифровых вычислительных машин. Задача двойного линейного программирования преобразует исходную или первичную задачу в соответствующую двойственную задачу которая может быть решена более эффективно легче. Чем первоначальная проблема. Параметрическое программирование-это расширение анализа чувствительности. При котором диапазоны параметров aij. Bi и cj вычисляются непосредственно с учетом более чем одного параметра одновременно. Кроме того, существуют методы декомпозиции. Которые берут чрезвычайно большую проблему и разделяют или декомпозируют ее на ряд более мелких проблем. Которые могут быть решены с разумным компьютерным временем и пространством. В дополнение. Для класса транспортных и сетевых задач разработаны специальные методики. Облегчающие их решение. Линейное программирование было расширено. Чтобы рассмотреть множество конфликтующих критериев. То есть более чем одну целевую функцию. И это было названо целевым программированием. Важным расширением линейного программирования является случай. Когда переменные могут принимать только целочисленные значения. И этот случай был назван целочисленным программирование. Более того, линейное программирование и теория игр тесно связаны для разработки оптимальных стратегий. Наконец, почти все большие компьютеры имеют один или несколько продвинутых кодов линейного программирования. Способных решать задачи с тысячами ограничений и тысячами переменных. Правильно собрать и ввести достоверные данные при использовании этих программ-очень трудоемкая и утомительная задача. Эти коды, например, MPSX. Они очень эффективны и используют методы разреженной инверсии матриц. Методы работы с плохо обусловленными матрицами. Структурные форматы данных и упрощенные входные и выходные преобразования. Кроме того, они обычно включают постоптимальное ранжирование. Обобщенное верхнее ограничение и параметрическое программирование (9,12). Опять же, темы. Упомянутые выше. Обсуждаются в статьях и книгах в Ссылках и Выбранном списке текстов в конце главы.

Избранный список текстов по линейному программированию и расширению Stopbazaraa, M. S.. And J. J. Jarris. Linear Programming and Network Flows. John Wiley and Sons, Inc.. New York (1977).

Charnes, A.. And W. W. Cooper, Management Models and Industrial Applications of Linear Programming, Vol. 1 и 2, John Wiley and Sons, Inc.. New York (1967).

Гарфинкель, Р. С. и Г. Л. Немхаузер. Целочисленное программирование. John Wiley and Sons, Inc.. Нью-Йорк (1972).

Glicksman, A. M.. Введение в линейное программирование и теорию игр. John Wiley and Sons, Inc.. New York (1963).

Гринберг, Х.. Целочисленное программирование. Academic Press. New York (1971).

Hadley, G. H.. Linear Programming. Addison-Wesley. Inc., Reading. Mass. (1962).

Land, A. H.. And S. Powell. Fortran Codes for Mathematical Programming: Linear, Quadratic and Discrete. John Wiley and Sons, Inc.. New York (1973).

Lasdon, L., Теория оптимизации для больших систем. Macmillan and Co.. New York (1970).

Naylor, T. H.. And E. T. Byrne. Linear Programming Methods and Cases. Wadsworth Publishing. Co., Balmont. Calif. (1963).

Orchard-Hays. W.nced Linear Programming Computing Techniques. McGraw-Hill Book Co.. New York (1968).

Пападимитриу. К. Х. и К. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc.. Englewood Cliffs. New Jersey (1982).

Schrage, L.. Linear Programming Models with LINDO. Scientific Press, Palo Alto. Calif.(1981).

Taha, H. A.. Integer Programming: Theory, Applications and Computations. Academic Press. New York (1975).

Referencestop1.Dantzig, G. B.. Linear Programming and Extensions. Princeton University Press, Princeton. N. J. (1963).

2.An Введение в линейное программирование, I. B. M. Data Processing Application Manual E20 — 8171, I. B. M. Corp.. White Plains, NY (1964).

3.Garvin, W. W.. Introduction to Linear Programming. McGraw-Hill Book Co.. N. Y. (1966).

4.Там же, стр.

5.Там же, стр.

6.Там же, стр.

7.Gass, S. I.. Linear Programming: Methods and Applications, 5th Ed.. McGraw-Hill Book Co.. New York (1985).

8.Smith, C. L.. R. W. Pike. P. W. Murrill. Formulation and Optimization of Mathematical Models. International Textbook Co., Scranton. Pa. (1970).

9.Holtzman, A. G.. Mathematical Programming for Operations Researchers and Computer Scientists, Ed. A. G. Holtzman. Marcel Dekker, Inc.. New York (1981).

10.Aronofsky, J. S.. J. M. Dutton. And M. T. Tayyabkhan. Management Planning with Linear Programming in Process Industry Operations. John Wiley and Sons, Inc.. New York (1978).

11.Anonymous, Oil and Gas Journal, 394 (3 мая 1982).

12.Murtagh, B. A.. Advanced Linear Programming: Computation and Practice. McGraw-Hill Book Co.. New York (1981).

13.Smith, M. G.. And J. S. Bonner. Computer-Aided Process Plant Design, Ed. M. E. Leesley. Gulf Publishing Co., Houston. P. 1335 (1982).

14.Stoecker, W. F.. Design of Thermal Systems, 2nd Ed.. McGraw-Hill Book Co.. P.271 New York (1980).

15.IBM Mathematical Programming System Extended/370 (MPSX/370) Программное справочное руководство, SH19-1095-3, 4-е Изд., IBM Corp.. White Plains, NY.

16.IBM Mathematical Programming System Extended/370 Primer, GH19-1091-1, 2-е Изд., IBM Corp.. White Plains, NY (1979).

17.Ignizio, J. P.. Linear Programming in Single and Multiple Objective Systems. Prentice-Hall, Inc.. Englewood Cliffs. N. J. (1982).

18.Quandt, R. E.. And H. W. Kuhn,

19.Bradley, S. P., A. C. Hax. And T. L. Magnanti. Applied Mathematical Programming. Addison-Wesley Publishing Co., Reading. Mass. p. 97 (1977).

Проблемы

4-1. Решите следующую задачу симплексным методом.

Максимизация: 6x1 + x2 = p

При условии: 3x1 + 5x2    13

6x1 + x2   12

x1 + 5x2   10

Определите диапазон на x1 и x2, для которого оптимальное решение остается оптимальным. Объяснять. (Примечание: Нет необходимости использовать анализ чувствительности.)

Решение

4-2. Решите следующую задачу симплексным методом.

Максимизация: x1 + 2x2 + 3x3 — x4 = p

При условии: x1 + 2x2 + 3x3 + x5 = 15

2x1 + x2 + 5x3 + x6 = 20

x1 + 2x2 + x3 + x4 = 10

Начните с x4, x5и x6 в основе.

Решение

4-3 а. Решите следующую задачу симплексным методом.

Максимизация: 2x1 + x2 = p

При условии: x1 + x2   6

x1 — x2   2

x1 + 2x2  10

x1 — 2x2   1

b.Вычислите обратную оптимальному базису. И наибольшие изменения в biдля оптимального решения остаются оптимальными.

Решение

4-4. Решите симплексным методом следующую задачу.

Максимизация: 3x1 + 2x2 = p

При условии: x1 + x2   8

2x1 + x2   10

Решение 4-5 а. Решите следующую задачу симплексным методом.

Максимизация: x1 + 2x2 = p

При условии: x1 + 3x2   105

-x1 + x2    15

2x1 + 3x2   135

-3x1 + 2x2   15

  1. Решите эту задачу с помощью классической теории. Используя множители Лагранжа. И объясните. Почему множители Лагранжа иногда называют

Решение

4-6а. Решите следующую задачу симплексным методом с использованием слабых и искусственных переменных:

Максимизация: x1 + 10x2 = p

При условии: -x1 + x2  >> 5

3x1 + x2    15

b.Вычислите обратную величину оптимального базиса и множителей Лагранжа.

c.Вычислите наибольшие изменения в правой части уравнений ограничений (bj‘s), чтобы оптимальное решение в части (a) оставалось оптимальным.

Решение

4-7. Решите следующую задачу симплексным методом. Используя минимальное количество слабых. Избыточных и искусственных переменных. Необходимых для изначально осуществимого базиса.

Минимизировать: 2x1 + 4x2 + x3 = c

При условии: x1 + 2x2 — x3   5

2x1 — x2 + 2x3 = 2

-x1 + 2x2 + 2x3   > 1

Решение

4-8а. Решите следующую задачу симплексным методом. Используя искусственную переменную x6 во втором уравнении ограничения и добавив к целевой функции член-106×6.

Максимизация: 2x1 + x2 + x3 = p

При условии: x1 + x2 + x3   10

x1 + 5x2 + x3   > 20

b.Вычислите эффект изменения коэффициента затрат c1 от 2 до 3, т. е. Dc1 = 1, и c3 от 1 до 4, т. е. Dc3 = 3, используя результаты примера 4-6.

в) Не решая задачу. Найдите новое оптимальное решение. Если первое уравнение ограничения изменить на следующее. Используя результаты примера 4-6.

x1 + x2 + x3    5

Кроме того, вычислите новые оптимальные значения x1 и x2 и значение целевой функции.

Решение

4-9.Рассмотрим следующую задачу линейного программирования

Максимизация: 2x1 + x2 = p

При условии: x1 + 2x2   10

2x1 + 3x2   12

3x1 + x2   15

x1 + x2    4

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

b.Следующая матрица является обратной к оптимальному базису, A-1. Умножьте эту матрицу на матрицу A, чтобы получить единичную матрицу I.

c.Вычислите множители Лагранжа для задачи.

d.Вычислите изменения в правой части уравнений ограничений. Которые приведут к тому. Что все значения переменных в базисе станут равными нулю.

Решение

(3) Рассмотрим следующую задачу. Основанную на анализе смешивания.

Минимизировать: 50x1 + 25x2 = c

При условии: x1 + 3x2  >> 8

3x1 + 4x2  > 19

3x1 + x2  > 7

а.Решите эту задачу симплексным методом.

б.Вычислите обратную величину оптимального базиса и множителей Лагранжа.

c.Определить влияние на оптимальное решение (переменные и стоимость), если правая часть уравнений второго ограничения изменена с 19 на 21, а правая часть уравнений третьего ограничения изменена с 7 на 8.

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

3/4 c1/c2    3

Решение

4-11.Рассмотрим следующую задачу линейного программирования.

Максимизация: x1 + 9x2 + x3 = p

при условии: x1 + 2x2 + 3x3   9

3x1 + 2x2 + 2x3   15

а.Решите эту задачу симплексным методом.

б.Вычислите обратную величину оптимального базиса и множителей Лагранжа.

в) Определите наибольшие изменения в правой части и в коэффициентах затрат переменных в базисе. Чтобы оптимальное решение оставалось оптимальным.

Решение

4-12.Решите следующую задачу симплексным методом. Чтобы продемонстрировать свое понимание использования слабых и искусственных переменных. Используйте переменную slack в первых двух уравнениях ограничений и искусственную переменную в третьем уравнении ограничений в качестве изначально возможной основы.

Максимизация: x1 + 2x2 = p

При условии: -x1 + x2    2

x1 + x2   6

x1 + x2  > 1

Решение

4-13 

а.Выведите уравнение (4-31) из уравнения (4-30). Объясните значение членов в уравнении (4-31) и обсудите применение этого уравнения в анализе чувствительности. Связанном с коэффициентами переменных в целевой функции.

б.Начав с уравнения (4-25), покажем. Что изменение в b, дающее предел на Db для x*i, new = 0, равно —b.

Решение

4-14. На электростанции. Которая является частью химического завода или нефтеперерабатывающего завода. Можно производить как электричество. Так и технологический пар (высокого и низкого давления). Типичная электростанция имеет ограничения. Связанные с мощностью турбины. Давлением и количеством пара. А также потребностью в электроэнергии. В Stoecker(14) разработана следующая экономическая и технологическая модель для простой электростанции. Производящей электроэнергию. Пар высокого давления x1и пар низкого давления x2.

Максимизация: 0.l6x1 + 0.14 x2 = p

При условии: x1 + x2   20

x1 + 4x2   60

4x1 + 3x2   72

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

Решение

4-15. Компания производит два уровня чистоты продукта. Который продается в галлонных контейнерах. Продукт А имеет более высокую чистоту. Чем продукт В. С прибылью в размере 0,40 доллара за галлон. Произведенный на А. И 0,30 доллара за галлон. Произведенный на В. Продукт А требует вдвое большего времени обработки. Чем продукт В. И если весь продукт В является продуктом. То com[any может производить 1000 галлонов в день. Однако запас сырья достаточен только для 800 галлонов в день как А. Так и В комбинированный. Продукт A требует контейнера. Из которого доступно только 400 контейнеров по одному галлону в день. В то время как для B. При условии. Что весь продукт может быть продан как A. Так и B. Какие объемы каждого из них должны быть произведены. Чтобы максимизировать прибыль? Решите задачу графически и симплексным методом.

Решение

4-16. Установка для обогащения воска. Как показано ниже. Получает сырье с низкой концентрацией воска и перерабатывает его в продукт с высокой концентрацией воска. В Стокере(14) отпускные цены продуктов равны х1, 8 долл. за сто фунтов и х2, 6 долл. за сто фунтов; затраты на сырье равны х3, 1,5 долл.за сто фунтов и х4, 3 долл. за сто фунтов.

Завод работает в следующих условиях:

  1. Такое же количество воска покидает растение. Как и входит в него.
  2. Приемные мощности завода ограничены не более чем 800 фунтов/час.
  3. Упаковочные средства могут вместить максимум 600 фунтов/час х2и 500 фунтов/час х1.

Если эксплуатационные затраты завода постоянны. Используйте Симплексный алгоритм для определения плана закупок и производства. Который приводит к максимальной прибыли.

Решение

4-17. Компания производит продукт и побочный продукт. И производство ограничено двумя ограничениями. Одна-от наличия сырья. А другая-от мощности перерабатывающего оборудования. Продукт требует 3,0 единиц сырья и 2,0 единиц перерабатывающих мощностей. Побочный продукт требует 4,0 единиц сырья и 5,0 единиц перерабатывающих мощностей. Имеется в наличии 1700 единиц сырья и в общей сложности 1600 единиц перерабатывающих мощностей. Прибыль составляет $2,00 в год. единица измерения для продукта и 4,00 доллара за единицу для побочного продукта.

Экономическая модель и ограничения таковы:

Максимизация: 2x1 + 4x2

При условии: 3x1 + 4x2    1700 ограничение на сырье

2x1 + 5x2  1600 ограничение производительности обработки

  1. Определите максимальную прибыль и производство продукта х1и побочного продукта х2с помощью симплексного метода.
  2. Вычислите обратную величину оптимального базиса и множителей Лагранжа.
  3. i. Если общее количество доступного сырья увеличивается с 1700 до 1701 года. Определите новый продукт. Побочный продукт и прибыль.
  4. Если дополнительные 10 единиц перерабатывающей мощности могут быть получены по цене 7 долларов, то есть 1600 увеличено до 1610, стоит ли получать эту дополнительную мощность?
  5. Может быть получен второй побочный продукт. Требующий 4,0 единицы сырья и 3 1/3 единицы перерабатывающей мощности. Определите прибыль. Которая должна была бы быть получена на этом побочном продукте. Чтобы рассмотреть его производство.

Решение

4-18.(14) Химический завод, технологическая схема которого показана на рис. 4-9, производит аммиак. Соляную кислоту, мочевину. Карбонат аммония и хлорид аммиака из углекислого газа, азота. Водорода и хлора. Значения x на рис. 4-9 показывают скорость потока в молях в час.

Затраты на кормовые запасы равны c1, c2, c3иc4, а стоимость продуктовравна p5 , p6, p7и p8 в долларах за моль. Где индекс соответствует индексу величины x. В реакторе 3 соотношения молярных скоростей потока составляют m =3×7 и x1 = 2×7, а в других реакторах применяются простые материальные балансы. Емкость реактора 1 равна или меньше 2000 моль/чNH3, а емкость реактора 2 равна или меньше 1500 моль/ч HCl. Как указано в Stoecker (14).

а) Разработайте выражение для получения прибыли.

b.Напишите уравнения ограничений для этого растения.

Решение

4-19.(8)Технологическая схема простого нефтеперерабатывающего завода показана на рис. 4-10. Ниже приведены цены и характеристики качества продукции. А также их минимальные производственные показатели:

Текущая стоимость нефти составляет $32,00 за баррель

Эксплуатационные затраты на сепарацию в сырой нефти по-прежнему составляют $0,25 за баррель на каждый произведенный продукт. Эксплуатационные затраты на установку каталитического крекинга составляют $0,10 для прямогонного дистиллята и $0,15 для прямогонного мазута.

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

Мощность установки каталитического крекинга не должна превышать 50 000 баррелей в сутки. А сырая нефть по-прежнему ограничена на уровне 100 000 баррелей в сутки. Сырая нефть разделяется в сыром перегонном кубе на три объемные фракции: 0,2 прямогонного бензина, 0,5 прямогонного дистиллята и 0,3 прямогонного мазута. В установке каталитического крекинга производится распределение продукта по 0,7 баррелям кат. нафта, 0,4 легких кат. циклическое масло и 0,2 барреля тяжелого кошка. цикловое масло получают из расчета на баррель прямоточного дистиллята. Прямой пробег распределения мазута составляет 0,1 барреля cat. нафта, 0,3 бочки легкого кота. цикл масла. И 0,7 барреля тяжелой кошки. масло цикла.

Представьте матричное представление этого простого нефтеперерабатывающего завода. Аналогичное показанному на рис. 4-8. Обязательно включите целевую функцию и ограничения материального баланса. Единицы измерения и смешивания.

Решение

4-20.Для получения результатов оптимизации МПС простого НПЗ рассмотрим следующее:

a.In Таблица 4-12(b) на стр. 4-60 показывает. Что переменная SRNPG не находится в основе. Вычислите наибольшее изменение коэффициента стоимости SRNPG. Чтобы оптимальное решение оставалось оптимальным. Убедитесь, что это правильный ответ. По результатам анализа чувствительности. Приведенным в таблице в главе.

b.In Таблица 4-12(б) расход мазута (ФО) находится на оптимальном значении 10 000 баррелей в сутки. Рассчитайте изменение прибыли при увеличении расхода мазута до 11 000 баррелей в сутки с помощью множителей Лагранжа. Приведет ли это изменение к тому. Что проблема будет решена в соответствии с результатами МПС, и почему?

в) Отдел маркетинга компании требует минимум 5000 баррелей в день остаточного топлива. Нового продукта. Остаточное топливо (RF)-это прямогонный мазут (SRFO) непосредственно из атмосферной ректификационной колонны. Цена составляет $ 10,00 за баррель, и он продается Приведите необходимые модификации матрицы на рис. 4-8, чтобы определить оптимальный способ работы нефтеперерабатывающего завода с этим новым продуктом.

Решение

4-21.Подготовьте матрицу уравнений целевой функции и ограничений из технологической схемы контактного процесса для серной кислоты. Аналогичную приведенной на рис. 4-8 для простого нефтеперерабатывающего завода. Технологическая схема контактного процесса приведена на рис. 7-21. Используйте следующие данные и предположите. Что единицы. Не включенные ниже. Имеют фиксированные операционные затраты. Которые не влияют на оптимизацию.

Решение

4-22.(17)В линейном программировании существует двойная задача. Которая получается из исходной или первичной задачи. Во многих случаях двойственная проблема может быть решена с меньшими трудностями. Чем первичная. Первичная проблема и соответствующая ей двойственная проблема изложены ниже в общем виде.

Первичная проблема Двойная проблема

Максимизировать: cTx Минимизировать: bTv

Subject to: A x  b Subject to: AT v > c

x > 0    v > 0

Отношения между первичными и двойственными проблемами суммируются следующим образом. Во-первых, двойственность двойственности-это первичная проблема. M x n primal дает n x m dual. Для каждого первичного ограничения существует двойная переменная и наоборот. Для каждой первичной переменной существует двойное ограничение. И наоборот. Числовое значение максимума первичного равно числовому значению минимума двойственного. Решением двойной задачи являются множители Лагранжа первичной задачи.

  1. Дайте первичную задачу следующей двойной задачи.

Минимизировать: 10в1 + 15в2

При условии: v1 + 5v2   >> 8

v1 + v2  > 4

  1. Решите двойственную задачу симплексным методом.
  2. Используя решение двойной задачи. Определите оптимальные значения переменных в первичной задаче.

Решение

4-23.Двойная задача линейного программирования может быть получена из первичной задачи с использованием множителей Лагранжа. Используя форму уравнений. Приведенную в задаче 4-22 для основной задачи. И учитывая. Что переменные слабины были добавлены к ограничениям, покажем. Что функция Лагранжа может быть записана как:

L(x, l) = cT x + lT(A xb)

Переставьте это уравнение так. Чтобы оно имело следующий вид.

L(x, l) = —bTl + xT(AT + c)

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

Минимизировать: bTl

В зависимости от: ATl >> c

Это двойная задача. Приведенная в задаче 4-22. Обратите внимание. Что независимыми переменными двойной задачи являются множители Лагранжа или

4-24.Первичное программирование может быть преобразовано в двойственную задачу. Как описано в задачах 4-22 и 4-23. Этот подход используется в тех случаях. Когда дуальную задачу решить легче. Чем первичную. Общая форма первичной задачи и ее двойственности была дана в задаче 4-22.

  1. Решите двойственную задачу первичной задачи и ее двойственную задачу. Приведенную ниже.

Первичная проблема

Минимизировать: 10x1 + 6x2 + 8x3

В зависимости от: x1 + x2 + 2x3 >> 2

5x1 + 3x2 + 2x3 > 1

Двойная проблема:

Максимизировать: 2v1 + v2

При условии: v1 + 5v2   10

v1 + 3v2   6

2v1 + 2v2   8

  1. В этой процедуре решение первичной задачи является отрицательным коэффициентом коэффициентов слабых переменных в целевой функции конечной итерации Симплексного метода двойной задачи. А решение двойной задачи является отрицательным коэффициентом множителей Лагранжа для первичной задачи. Приведите решение первичной задачи и множители Лагранжа для первичной задачи и покажите. Что минимум целевая функция первичной задачи равна максимуму целевой функции двойной задачи.
  2. В основной задаче дайте матрицу. Которую нужно инвертировать. Чтобы вычислить обратную оптимальному базису.
  3. Вычислите множители Лагранжа. Используя уравнение (4-22). И покажите. Что они согласуются с решением двойной задачи.
  4. К задаче добавляется новая переменная x6, как показано ниже.

Минимизировать: 10x1 + 6x2 + 8x3 + 2x6 = p

При условии: x1 + x2 + 2x3 + x4 + 5x6 = 2

5x1 + 3x2 + 2x3 + x5 + 3x6 = 1

Останется ли оптимальное решение оптимальным или проблему придется решать? Объяснять.

Решение