WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 56 | 57 ||

Альтернативные оптимальные решения Когда гиперплоскость, представляющая целевую функцию, параллельна гиперплоскости, соответствующей связывающему ограничению ( которое в точке оптимума выполняется как точное равенство), целевая функция принимает одно и то же оптимальное значение в некоторой совокупности точек пространства решений. Такие решения называются альтернативными оптимальными решениями.

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

Пример:

F()= 2Чx1 + 4Чx2 max при ограничениях x1 + 2Чx2 Ј 5 (ресурс 1) x1 + x2 Ј 4 (ресурс 2) x1 і 0, x2 і 0.

Рис.2 иллюстрирует условия данной задачи ЛП, особенность которой состоит в том, что прямая, представляющая целевую функцию, параллельна прямой, соответствующей одному из связывающих ограничений.

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

Таблица = F(x) = 1/ 1/ 1/ 1/ 5/ 3/ F(x) = F(x) = Каким образом по результатам итерации можно узнать о наличии альтернативных решений? Нулевое значение симплексной разности у небазисной переменной свидетельствует о том, что ее включение в базис не изменит значения целевой функции, но приведет к изменению других переменных.

Любое решение, соответствующее точке (,) принадлежащей отрезку ВС, можно определить как положительновзвешенное среднее двух полученных оптимальных базисных решений, соответствующих точкам В и С. Поэтому, используя координаты точек В и С В: х1 = 0; х2 = 5/2;

С: х1 = 3; х2 = 1;

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

,.

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

Метод искусственного базиса Часто, после приведения ОЗЛП к каноническому виду расширенная матрица системы линейных уравнений (СЛУ) не является Кматрицей (нет начального опорного плана), и, следовательно, решать такую КЗЛП симплексметодом нельзя. Суть метода искусственного базиса состоит в следующем: строится такая вспомогательная КЗЛП (ВКЗЛП) с заранее известным опорным планом, по решению которой либо определяется начальный опорный план исходной задачи, либо устанавливается, что ее множество планов пусто.

Дано:

, i = 1,..., m, rang (A) = m < n, bi 0, i = 1,..., m.

Найти: Кматрицу (начальный опорный план).

Построим следующую ВКЗЛП:

,, i = 1,..., m, xj 0, j = 1,..., n, yi 0, i = 1,..., m, yi – искусственные переменные.

Очевидно, начальный опорный план ВКЗЛП имеет вид:

, = (n+1, n+2,..., n+m).

Применяя симплексметод, находят – решение ВКЗЛП.

Замечание: ВКЗЛП всегда разрешима, так как множество ее планов не пусто, а целевая функция ограничена.

Теорема: Если, то – начальный опорный план исходной КЗЛП. Если, то множество планов исходной КЗЛП пусто и, следовательно, она неразрешима.

Пример: F(X) = 5Чx1 + 3Чx2 + 4Чx3 x x1 + 3Чx2 + 2Чx3 + 2Чx4 = 2Чx1 + 2Чx2 + x3 + x4 =.

x1 + 3Чx2 + 2Чx3 + 2Чx4 + y1 = x1 + 3Чx2 + 2Чx3 + 2Чx4 + y2 = xj0, j = 1,..., 4, y1,20.

= (5,6), = (3,3), = (1,1).

Таблица = F(x)= 1/ 4/ 2/ 1/ 2/ 1/ 4/ 1/ 1/ 3/ 1/ 3/ 1/ 3/ 3/ F(x)= Замечание:

По мере выхода искусственных переменных из базиса, вычисления в соответствующих клетках симплекстаблицы не проводятся.

Получили оптимальный опорный план ВКЗЛП.

(3/4,3/4,0,0,0,0),, (3/4,3/4,0,0).

Теперь решаем симплексметодом исходную задачу:

F(X)= 5Чx1 + 3Чx2 + 4Чx3 x x2 + 3/4Чx3 + 3/4Чx4 = 3/ x1 1/4Чx3 1/4Чx4 = 3/ xj0, j = 1,..., 4.

Таблица = 3/ 1/ 3/ 1/ 3/ 3/ F(x) = 4/ 1/ F(x) = (1, 0, 1, 0), = 9.

Анализ решаемых задач Математическая модель является хорошим средством получения ответов на широкий круг самых разнообразных вопросов, возникающих при принятии оптимальных решений. Например, на этапе постановки задачи часто производится анализ с целью ответа на вопросы: “что будет, если...?“ и/или “что надо, чтобы...?”. Анализ с целью ответа на первый вопрос называется вариантным анализом; на второй решениями по заказу. Для задач распределения ресурсов большой интерес представляет решение задачи минимизации используемых ресурсов при заданном результате.

Рассмотрим следующую исходную задачу:

Первая постановка:

F()= 4X1 + 3X2 + 6X3 + 7X4 (прибыль) при ограничениях на ресурсы 2X1 + X2 + X3 + X4 280 ( трудовые) X1 + X3 + X4 80 (сырье) X1 + 2X2 + X3 250 (финансы) Xj 0, j=1,...,4.

Решив задачу получим: = (0, 125, 0, 80), где X1 = 0 объем производства продукции вида 1, X2 = 125 объем производства продукции вида 2, X3 = 0 объем производства продукции вида 3, X4 = 80 объем производства продукции вида 4.

F() = 935 прибыль от реализации продукции.

Вторая постановка:

F()= 4X1 + 3X2 + 6X3 + 7X4 (прибыль) при ограничениях на ресурсы 2X1 + X2 + X3 + X4 280 ( трудовые) X1 + X3 + X4 80 (сырье) X1 + 2X2 + X3 250 (финансы) X1 10, X2 100, (дополнительные X3 25, ограничения на X4 50 выпуск продукции) Xj0, j=1,...,4.

В результате решения получим: = (10, 100, 25, 45), F() = 805.

Третья постановка:

F() = Y1 + Y2 + Y3 (минимизация используемого ресурса) 2X1 + X2 + X3 + X4 + Y1 = 280 ( трудовые) X1 + X3 + X4 + Y2 = 80 (сырье) X1 + 2X2 + X3 + Y3 = 250 (финансы) X1 10, X2 20 (задаваемый X3 25, X4 40. результат) Y1, Y2, Y3 0 ( неиспользованный ресурс).

Решив задачу получим: = (10, 20, 25, 40), = (175, 5, 175).

При решении по заказу пользователь задает значения тех величин, которые он хочет иметь в оптимальном решении. Такие задачи могут быть трех видов:

1) назначение величины целевой функции;

2) назначение величин искомых переменных;

3) назначение величин используемых ресурсов.

Следует иметь в виду, что во всех этих случаях возможно появление несовместного решения. Рассмотрим такую ситуацию на нашем примере.

Четвертая постановка:

F()= 4X1 + 3X2 + 6X3 + 7X4 (прибыль) при ограничениях на ресурсы 2X1 + X2 + X3 + X4 280 ( трудовые) X1 + X3 + X4 80 (сырье) X1 + 2X2 + X3 250 (финансы) X1 100, X2 100, (дополнительные X3 = 30, X4 = 70 ограничения на выпуск продукции) Xj0, j=1,...,4.

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

Пятая постановка:

F() = t1 + t2 + t3 (минимизация необходимого дополнительного ресурса) 2X1 + X2 + X3 + X4 t1 = 280 ( трудовые) X1 + X3 + X4 t2 = 80 (сырье) X1 + 2X2 + X3 t3 = 250 (финансы) X1 100, X2 100, (задаваемый результат) X3 = 30, X4 = 70.

t1, t2, t3 0 (дополнительный ресурс).

Решив задачу получим: = (100, 60, 30, 70), = (80, 120, 0).

10.2. Специальные задачи линейного программирования в производственном менеджменте Задачи дробнолинейного программирования Общая задача дробнолинейного программирования состоит в определении экстремального значения функции = = (2.1) при условиях, i = 1,..., m, (2.2) xj 0, j=1,...,n, (2.3) где cj, dj, bi и aij некоторые числа, причем > 0 в области допустимых решений. Такое условие не нарушает общности задачи, поскольку в том случае когда эта величина отрицательна, знак минус можно отнести к числителю. Как и в случае основной задачи линейного программирования, экстремальное значение целевая функция (2.1) принимает в одной из вершин допустимого многогранника (естественно, при условии, что эта задача имеет оптимальный план).

Рассмотрим несколько содержательных примеров на составление математической модели.

Пример 1. Для производства n видов изделий предприятие использует m типов взаимозаменяемого оборудования. Каждый из видов изделий необходимо изготовить в количестве bj единиц (j=1,..,n), причем каждый из типов оборудования может быть занят изготовлением этих изделий не больше чем ai часов (i=1,...,m). Время изготовления одного изделия jго вида на iм типе оборудования равно aij часам, а затраты, связанные с производством одного изделия на данном типе оборудования равны cij рублей. Определить сколько изделий каждого вида на каждом из типов оборудования следует произвести так, чтобы себестоимость одного изделия была минимальной.

Пусть Xij количество изделий jго вида, изготовляемых на оборудовании iго типа. Тогда получим (себестоимость одного изделия) (i=1,..., m) – (ограничения на время), (j = 1,..., n) – (ограничения на выпуск изделий), Xij 0, (i=1,...,m), ( j=1,...,n) (условия неотрицательности).

Пример 2. Для выполнения n различных работ могут быть использованы рабочие m квалификационных групп. При выполнении jй работы iй группой рабочих выработка в единицу времени равна cij (i=1,...,m), ( j=1,...,n) рублей. Общий фонд времени, в течение которого iя группа рабочих может быть занята выполнением работ, не превышает bi единиц времени, а объем jй работы равен aj рублей. Составить такой план выполнения работ, при котором производительность труда является максимальной.

Пусть Xij время, выделяемое рабочими iй квалификационной группы на jю работу. Тогда – (производительность труда), (i=1,...,m) (ограничения на время), (j=1,...,n) – (ограничения на объем работы), Xij 0, (i = 1,..., m), (j = 1,..., n) – (условия неотрицательности).

Сформулированная выше задача (2.1)(2.3) может быть сведена к задаче линейного программирования. Для этого следует обозначить (2.4) и ввести новые переменные, (j = 1,..., n). (2.5) Тогда исходную задачу (2.1)(2.3) можно записать в виде (2.6) при условиях, (i=1,...,m), (2.7) (2.8) 0, ( j=1,...,n), 0.

Задача (2.6) (2.8) является задачей линейного программирования и, следовательно, ее решение можно найти известными методами. Зная оптимальный план этой задачи, на основе соотношений (2.5) получим оптимальный план исходной задачи (2.1) (2.3).

Пример 3.

= 2 * X1 + X2 + X3 + 3 * X4 Ј X1 + 2 * X3 + X4 Ј X1 + 2 * X2 + X 3 Ј Xj 0, (j = 1,..., 4).

Сведем данную задачу к задаче линейного программирования. Для этого обозначим через и введем новые переменные, (j=1,...,4). В результате приходим к следующей задаче:

8 * Y1 + 3Y2 + 2 * Y3 + Y 2 * Y1 + Y2 + y3 + 3 * Y4 300 * Y0 Ј Y1 + 2 * Y3 + Y4 70 * Y0 Ј Y1 + 2 * Y2 + y3 340 * Y0 Ј Y1 + Y2 + Y3 + Y4 = Y0, Yj 0, ( j=1,...,4).

Решив данную задачу получим:

(Y0, Y1, Y2, Y3, Y4) = ( 1/70, 1, 0, 0, 0) Используя соотношения, определяем оптимальный план исходной задачи (X1, X2, X3, X4) = (70, 0, 0, 0), F() = 8.

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

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

Математическая модель линейной целочисленной задачи может быть записана следующим образом:

F() = (1), bi 0, i = 1,..., m, (2) xj 0, j = 1,..., n, xj – целые. (3) Существует эвристический подход к решению задач целочисленного программирования (ЗЦП), основанный на решении ЗЦП как задачи ЛП. Использование процедур округления нецелочисленного оптимального решения задачи ЛП дает возможность получать приближенное оптимальное целочисленное решение. Например, если в оптимальном решении двумерной задачи ЛП значения переменных х1 и х2 оказались равными 3,5 и 4,4 соответственно, то в качестве кандидатов на роль приближенного целочисленного оптимального решения необходимо рассмотреть точки (3;4), (4;4), (4;5), (3;5) полученные в результате округления. Заметим однако, что истинное оптимальное целочисленное решение может не совпадать ни с одним из четырех, указанных выше.

ПРИМЕР F() = x1 – 3Чx2 + 3Чх при ограничениях 2Чx1 + x2 х3 Ј 4Чx1 3Чx2 Ј 3Чx1 + 2Чx2 + х3 Ј x1, х2, х3 і 0, целые.

Игнорируя условия целочисленности получим. Никакое округление компонент этого плана не дает допустимого решения, так как искомое целочисленное решение. Таким образом, для решения целочисленных задач необходимы специальные методы.

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

Pages:     | 1 |   ...   | 56 | 57 ||




© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.