Линейное программирование

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

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

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Контрольная работа № 1 по дисциплине

«Автоматизированные информационно-управляющие системы»

2012

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

1. Сформулировать по заданному 24-хзначному числу задачу линейного программирования вида:

где все параметры модели должны быть определены на основе таблиц 3, 4, 5, а также из следующих условий:

Таблица 3

Таблица 4

Таблица 5

2. Придумать оригинальную содержательную постановку задачи, которой соответствует модель из п.1.

3. Найти оптимальное решение модели, сформированной в п.1.

4. Произвести анализ на чувствительность модели, сформированной в п.1.

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

4.2. То же, что и п.4.1, но только для базисных переменных.

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

4.4. Найти пределы, в которых могут меняться константы в правых частях соотношений в п.1, не нарушая оптимальности прежнего решения.

4.5. Пусть в правых частях первых двух ограничений в п.1 константы b₁ и b₂ могут одновременно быть изменены. Найти систему неравенств, при выполнении которой прежнее решение остается оптимальным. Изобразить допустимую область графически.

5. Двойственная задача.

5.1. Записать для задачи, сформированной в п.1, двойственную задачу.

5.2. Найти оптимальное решение двойственной задачи.

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

5.4. Пусть вводятся новые управляемые переменные x₁₀ и x₁₁. Коэффициенты при x₁₀ и x₁₁ записаны в табл.6. Целесообразен ли ввод данных переменных? двойственный задача коэффициент переменная

Таблица 6

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

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

1. Формулируем модель для 24-хзначного числа. Получаем:

Целевая функция:

2. Небольшой цех по производству макаронных изделий заключил договор о поставке шести видов продукции:

х₁- рожки

х₂- ракушки

х₃- вермишель

х₄- спагетти

х₅- лапша

х₆- фигурные

Цех производит мебель из трех основных видов сырья:

1- Мука из твердых сортов пшеницы

2- Яйцепродукты

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

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

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

Строим первый опорный план, для этого перейдем к канонической форме, вводя дополнительные переменные. В первом неравенстве вводим базисную переменную x₇. Во втором неравенстве вводим базисную переменную x₈. В третьем неравенстве вводим базисную переменную x₉. Получаем систему:

Решаем систему относительно базисных переменных x₇, x₈, x₉,

Полагая, что свободные переменные равны 0, получаем первый опорный план:

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

Итерация №0.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент по модулю.

Вычисляем значения D_i по строкам как частное от деления: b_i / a_i3 и из них выбираем наименьшее min (6: 4, 13: 6, 12: 4 ) = 1,5

Следовательно, первая строка является ведущей.

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

После преобразований получаем новую таблицу:

Индексная строка не содержит отрицательных элементов, следовательно, найден оптимальный план:

4. Проведем анализ на чувствительность.

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

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

может изменяться в пределах ,

может изменяться в пределах ,

может изменяться в пределах ,

может изменяться в пределах ,

может изменяться в пределах ,

может изменяться в пределах

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

Для этого изменим коэффициент при базисной переменной и получим выражение для целевой функции:

Из полученного выражения можно определить, что полученное решение является

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

Переменные и рассматривать не будем, так как они являются остаточными.

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

Строим график неравенств:

4.4. Найдем пределы, в которых могут меняться константы в правых частях соотношений в п.1, не нарушая оптимальности прежнего решения. Для этого рассмотрим начальный и конечный планы:

Рассмотрим b в строке начального плана. Произведем замену 6 6+.

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

Рассмотрим b в строке начального плана. Произведем замену 13 13+. Остаточная переменная входит в базис и на первой и на последней итерации с коэффициентом 1. Поэтому сохранится в строке без изменений. Таким образом, ранее полученное решение останется допустимым, если . Иначе будет <0, что недопустимо.

Рассмотрим b в строке начального плана. Произведем замену 12 12+. Остаточная переменная входит в базис и на первой и на последней итерации с коэффициентом 1. Поэтому сохранится в строке без изменений. Таким образом, ранее полученное решение останется допустимым, если . Иначе будет <0, что недопустимо.

4.5. При одновременном изменении ограничений b₁ и b₂ происходит одновременное изменение остаточных переменных и , что можно выразить через приращения ₇ и ₈.

Тогда правые части уравнений во второй системе будут равны:

Получаем систему неравенств:

Область, ограниченная полученной системой сохраняет оптимальность исходного решения. Эта область имеет вид:

5. Двойственная задача

5.1. Формулировка двойственной задачи имеет вид:

5.2. Решение двойственной задачи дает оптимальную систему оценок ресурсов.

Используя последний план прямой задачи, находим оптимальный план двойственной задачи:

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

Оптимальный план двойственной задачи равен:

= 1,5

= 0

= 0

5.3. Для анализа чувствительности, подставляем полученное оптимальное решение двойственной задачи в систему неравенств:

5.4. Согласно заданному варианту, значения коэффициентов новых переменных:

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

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

6. Динамическая задача.

Для динамической задачи производства корпусной мебели, если не изменять ассортимент продукции x_i, в течение трех периодов времени производства возможны изменения исходной модели:

прибыльность каждого вида продукции -- описывается матрицей ||с_i,t|| (i- вид продукта, t-период времени).

рецептура -- описывается матрицей ||a_j,i||_t (расход компонента j на единицу продукта i в период времени t).

запасы на складе-- описываются матрицей ||b_j,t||. В первый период времени это данность, в последующие периоды - сумма остатков с предыдущего периода и вновь докупаемого количества компонента, т.е. матрица ||b_j,t|| --это плановые закупки сырья j на период t, без учета остатков за предыдущий период..

произведенная продукция i за период t -- || x_i,t ||

Кроме этого можно ввести дополнительные управляемые переменные и ограничения:

|| y_j,t || -- остаток компонента j на период t. Этот остаток требует затрат на хранение || s_j,t ||

|| z_i,t || -- остаток невостребованной готовой продукции i, на период t. Тоже требует затрат на свое хранение || k_i,t ||. В качестве ограничения снизу, влияющего на этот остаток здесь может выступать гарантированный спрос на продукцию (контракты например), описываемый матрицей || d_i,t ||. С учетом остатков готовой продукции, || d_i,t || приобретает смысл проданной продукции i за период t. В результате получаем равенство x_i,t + z_{i,t -1}= d_i,t + z_i,t

Чтобы не изменять динамически запасы на складе, минимальную потребность в запасах можно определить заранее и ввести в ограничения ||b_j,t|| , а затраты на закупку сырья можно включить в коэффициенты прибыльности целевой функции ||с_i,t||.

В результате получаем модель:

Размещено на Allbest.ru