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

5) Оценки вариантов по критериям могут быть получены только от экспертов.

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

1) Методы решения должны быть приспособлены к естественному для ЛПР языку описания проблемы. Обычно это означает вербальное (словесное) описание оценок по критериям.

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

3) При словесном описании критериальных оценок можно использовать логические процедуры их преобразования для построения решающих правил ЛПР (т.е. правил проведения сравнения вариантов). Эти операции должны быть математически корректными.

4) В методах принятия решений должны быть предусмотрены средства проверки информации, полученной от ЛПР, на непротиворечивость в ходе её получения, средства поиска и устранения противоречий.

5) Метод должен обеспечивать для ЛПР возможность получения объяснений на понятном ему языке.

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

Вербальный анализ

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

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

Наиболее существенная черта вербального анализа решений как научного направления, отличающая его от других известных методологических подходов в теории принятия решений, состоит в использовании нечисловой (качественной) информации на всех этапах анализа и решения задачи без каких либо ее преобразований в числовую. Другими особенностями вербального анализа решений являются: получение информации от лица, принимающего решение (ЛПР) на привычном для него языке; проверка информации, полученной от ЛПР, на непротиворечивость; обеспечение для ЛПР возможностей поэтапного формирования предпочтений путем «проб и ошибок»; логическое обоснование вида решающего правила; возможность объяснения полученного решения.

Эффективность - один из ключевых экономических понятий, и проблема эффективного распределения ресурсов актуальна на долгие годы вперёд. Согласно теории итальянского экономиста Вильфредо Парето, добавленная стоимость секторов и доходы трудовых ресурсов движутся противонаправленно в соответствии с хорошо известным уравнением теплопроводности аналогично газу или жидкости в пространстве, что дает возможность применить методику анализа, используемую в физике, в отношении экономических задач по миграции экономических параметров. Исходя из теории распределения Парето, затраты на выполнение плана находятся в следующей пропорции: 20 % труда реализуют 80 % результата, но остальные 20 % результата требуют 80 % общих затрат. Напрашивается вопрос, а можно ли сделать так, чтобы на достижения основного результата расходовалось основная часть ресурсов? В случае с разработкой муниципальных программ развития необходимо чёткое понимание, какие задачи являются первостепенными, на какие следует использовать больше имеющихся ресурсов. Метод аналитической иерархии (Analytic Hierarchy Process - АНР) широко известен в настоящее время.

Рассмотрим его более подробно.

Постановка задачи, решаемой с помощью метода АНР, заключается обычно в следующем. Даны общая цель (или цели) решения задачи, критерии оценки альтернатив, альтернативы. Требуется выбрать наилучшую альтернативу.

Подход АНР состоит из совокупности этапов.

1. Первый этап заключается в структуризации задачи в виде иерархической структуры с несколькими уровнями: цели -критерии--альтернативы.

2. На втором этапе ЛПР выполняет попарные сравнения элементов каждого уровня. Результаты сравнений переводятся в числа.

3. Вычисляются коэффициенты важности для элементов каждого уровня. При этом проверяется согласованность суждений лица, принимающего решение (ЛПР).

4. Подсчитывается количественный индикатор качества каждой из альтернатив и определяется наилучшая альтернатива. Достоинством метода АНР, привлекающим внимание многих пользователей, является направленность на сравнение реальных альтернатив. Отметим, что метод АНР может применяться и в тех случаях, когда эксперты (или ЛПР) не могут дать абсолютные оценки альтернатив по критериям, а пользуются более слабыми сравнительными измерениями. Метод АНР позволяет решить ряд практических задач.



Вопрос 16. Задачи линейного программирования. Постановка и геометрическая интерпретация задач линейного программирования. Методы линейного программирования. Прямые и двойственные задачи математического программирования. Симплекс-метод. Многокритериальные задачи линейного программирования

1 Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП

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

Несколько слов о самом термине линейное программирование. Он требует правильного понимания. В данном случае программирование - это, конечно, не составление программ для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий.

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

Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:

Задача об оптимальном использовании ресурсов при производственном планировании;

Задача о смесях (планирование состава продукции);

Задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

Транспортные задачи (анализ размещения предприятия, перемещение грузов).

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

Математические модели большого числа экономических задач линейны относительно искомых переменных;

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

Многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.

В общем виде модель записывается следующим образом:

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

= c₁x₁ + c₂x₂ + ... + c_nx_n > max(min);

ограничения:

a11x1 + a12x2 + ... + a1nxn {? = ?} b1,

a21x1 + a22x2 + ... + a2nxn {? = ?} b2,

...

am1x1 + am2x2 + ... + amnxn {? = ?} bm;

требование неотрицательности:

x_j ? 0,

При этом a_ij, b_i, c_j ( ) - заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3).

Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми.

Вектор , удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программирования. План , при котором функция (2.1) достигает своего максимального (минимального) значения, называетсяоптимальным.[1]

Геометрическое решение ЗЛП

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

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

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

1. Сформулировать ЗЛП.

2. Построить на плоскости {х₁, х₂} прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

3. Найти полуплоскости, определяемые каждым из ограничений задачи.

4. Найти область допустимых решений.

5. Построить прямую

c₁x₁ + c₂x₂ = h,

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

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

7. Определить координаты точки максимума (минимума) функции и вычислить значение функции в этой точке.

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

1. Выше уже приводилась формулировка задачи, здесь нам остается лишь повторить ее:

= 2x1 + 4x2 >Размещено на http://www.allbest.ru/

max;

4x1 +6x2 ? 120,

2x1 +6x2 ? 72,

x2 ? 10;

x1 ? 0, x2 ? 0.

2. Теперь построим прямые, соответствующие каждому из функциональных ограничений задачи (см. рисунок 2). Эти прямые обозначены на рисунке (1), (2) и (3).

Рисунок 2. - Геометрическое решение ЗЛП

3. Штрихи на прямых указывают полуплоскости, определяемые ограничениями задачи.

4. Область допустимых решений включает в себя точки, для которых выполняются все ограничения задачи. В нашем случае область представляет собой пятиугольник (на рисунке обозначен ABCDO и окрашен синим цветом).

5. Прямая, соответствующая целевой функции, на рисунке представлена пунктирной линией.

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

7. Осталось вычислить координаты точки С. Она является точкой пересечения прямых (1) и (2). Решив совместно уравнения этих прямых, найдем: , . Подставляя найденные величины в целевую функцию, найдем ее значение в оптимальной точке .

Таким образом, для максимизации прибыли компании следует ежедневно выпускать 24 клюшки и 4 набора. Реализация такого плана обеспечит ежедневную прибыль в размере $64.

Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.

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

В основу симплексного метода положена идея последовательного улучшения получаемого решения.

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

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

Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

1) способ определения какого-либо первоначального допустимого базисного решения задачи;

2) правило перехода к лучшему (точнее, не худшему) решению;

3) критерий проверки оптимальности найденного решения.

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

Далее рассмотрим симплексный алгоритм, не углубляясь в его обоснование.

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

Шаг 1. Формулировка ЗЛП (формирование целевой функции и системы ограничений).

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

= c1x1 + c2x2 + ... + cnxn max;

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

a11x1 + a12x2 + ... + a1nxn ? b1,

a21x1 + a22x2 + ... + a2nxn ? b2,

...

am1x1 + am2x2 + ... + amnxn ? bm;

xj ? 0,

Еще раз повторим формулировку задачи из нашего примера.

= 2x1 + 4x2 >Размещено на http://www.allbest.ru/

max;

4x1 +6x2 ? 120,

2x1 +6x2 ? 72,

x2 ? 10;

Шаг 2. Приведение задачи к канонической форме (перевод функциональных ограничений в систему уравнений).

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

a11x1 + a12x2 + ... + a1nxn + y1 = b1,

a21x1 + a22x2 + ... + a2nxn + y2 = b2,

...

am1x1 + am2x2 + ... + amnxn + ym = bm.

Обозначим добавочные переменные несколько иначе, а именно:

y₁ = x_n+1, y₂ = x_n+2, ...,

y_m = x_n+m,

где n - число переменных в исходной задаче, m - число уравнений.

Все дополнительные переменные также должны быть неотрицательными.

В отношении добавочных переменных нужно сделать еще одно важное замечание. Все они должны иметь тот же знак, что и свободные члены системы ограничений. В противном случае используется так называемый M-метод (метод искусственного базиса).

Выполним второй шаг для нашего примера.

4x1 +6x2 + x3 = 120,

2x1 +6x2 + x4 = 72,

x2 + x5 = 10.

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

При ручной реализации симплексного метода удобно использовать так называемые симплексные таблицы. Исходная симплекс-таблица соответствует первоначальному допустимому базисному решению. В качестве такового проще всего взять базисное решение, в котором основными являются дополнительные переменные x_n+1, x_n+2, ..., x_n+m. Ниже приведены исходная симплексная таблица в общем виде (таблица 2) и в применении к рассматриваемой нами задаче (таблица 3).

Таблица 2. - Общий вид исходной симплекс-таблицы

базис	переменные	bi
	x1	x2	...	xn	xn+1	...	xn+m
xn+1	a11	a12	...	a1n	1	0	0	b1
xn+2	a21	a22	...	a2n	0	...	0	b2
...	...	...	...	...	...	...	...	...
xn+m	am1	am2	...	amn	0	0	1	bm
cj	c1	c2	...	cn	0	0	0	L

Итак, в левом столбце записываются основные (базисные) переменные, в первой строке таблицы перечисляются все переменные задачи. Крайний правый столбец содержит свободные члены системы ограничений b₁, b₂, ..., b_m. В последней строке таблицы (она называется оценочной) записываются коэффициенты целевой функции, а также значение целевой функции (с обратным знаком) при текущем базисном решении (). В рабочую область таблицы (начиная со второго столбца и второй строки) занесены коэффициенты a_ij при переменных системы ограничений.

Таблица 3 - Исходная симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах

базис	переменные	bi
	x1	x2	x3	x4	x5
x3	4	6	1	0	0	120
x4		6	0	1	0	72
x5	0	1	0	0	1	10
cj	2	4	0	0	0	0

Таким образом, в данном базисном решении неосновные переменные x₁ и x₂ равны нулю. Базисные переменные отличны от нуля: x₃ = 120, x₄ = 72, x₅ = 10. Данное базисное решение является допустимым. Естественно, что значение целевой функции в этом случае равно нулю, так как в формировании целевой функции участвуют переменные, которые для данного базисного решения являются неосновными.

Шаг 4. Проверка условия: все c_j ? 0. Если НЕТ - осуществляется переход к шагу 5, если ДА - задача решена. Таким образом, на данном шаге проверяется наличие положительных элементов в последней строке симплексной таблицы. Если такие элементы имеются, необходимо продолжать решение.

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

Шаг 5. Выбор разрешающего столбца (переменной, вводимой в базис). Разрешающий столбец выбирается в соответствии со следующим условием:

где r - номер разрешающего столбца.

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

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

Шаг 6. Проверка условия: все a_ir ? 0. Если ДА - целевая функция неограничена и решения нет, если НЕТ - переход к шагу 7.

Таким образом, необходимо проверить элементы разрешающего столбца. Если среди них нет положительных, то задача неразрешима.

В нашем примере все элементы разрешающего столбца положительны (6, 6 и 1), следовательно, необходимо перейти к шагу 7.

Шаг 7. Выбор разрешающей строки (переменной, выводимой из базиса) по условию:

для air > 0

где s - номер разрешающей строки.

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

Проиллюстрируем выполнение шага 7, обратившись к нашему примеру.

Для первой строки:

D₁ = 120 / 6 = 20.

Для второй строки:

D₂ = 72 / 6 = 12.

Для третьей строки:

D₃ = 10 / 1 = 10.

Наименьший результат деления - в третьей строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. исключать из базисного решения будем переменную x₅.

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

Исходная симплекс-таблица нашего примера с выделенными цветом разрешающей строкой и разрешающим столбцом представлена ниже (таблица 4).

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

Шаг 8. Пересчет элементов симплекс-таблицы (переход к новому базисному решению). Порядок пересчета различных элементов таблицы несколько отличается.

Для элементов разрешающей строки используются следующие формулы:

где s - номер разрешающей строки,

r - номер разрешающего столбца,

, - новые значения пересчитываемых элементов,

a_sj, b_s - старые значения пересчитываемых элементов,

a_sr - старое значение разрешающего элемента.

Таким образом, при пересчете элементов разрешающей строки каждый ее элемент делится на разрешающий элемент.

Еще проще пересчитать элементы разрешающего столбца. Все они (кроме разрешающего элемента) становятся равными нулю:

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

где , , , - новые значения пересчитываемых элементов,

a_ij, b_i, c_j, L - старые значения пересчитываемых элементов.

Применение правила прямоугольника проиллюстрируем, используя таблицу 4. Пересчитаем элемент a₁₁ (в исходной симплекс-таблице его значение равно 4). В таблице 2.6 можно видеть прямоугольник (прочерчен пунктиром), соединяющий четыре элемента, участвующих в пересчете:

т.е.

Аналогичным образом пересчитываются остальные элементы.

По окончании пересчета осуществляется возврат к шагу 4.

Полностью результат пересчета для нашего примера можно видеть в таблице 5.

Таблица 5. - Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах (второе базисное решение)

базис	переменные	bi
	x1	x2	x3	x4	x5
x3	4	0	1	0	-6	60
x4	2	0	0	1	-6	12
x2	0	1	0	0	1	10
cj	2	0	0	0	-4	-40

Таким образом, в новом базисном решении базисными переменными являются: x₂ = 10, x₃ = 60, x₅ = 12 (соответствующие значения можно видеть в последнем столбце таблицы). Неосновные переменные x₁ и x₅ равны нулю. Значение целевой функции в этом случае равно 40 (значение можно видеть в правой нижней ячейке таблицы).

Доведем решение нашего примера до конца.

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

Шаг 5. Выберем разрешающий столбец. Им окажется столбец x₁, поскольку здесь содержится единственный положительный элемент нижней строки. Стало быть, переменную x₁ будем переводить в основные.

Далее. Шаг 6. Проверка показывает, что в разрешающем столбце есть положительные элементы, следовательно, можно продолжать решение.

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

Для первой строки:

D₁ = 60 / 4 = 15.

Для второй строки:

D₂ = 12 / 2 = 6.

Наименьший результат деления - во второй строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. переводить в неосновные (исключать из базиса) будем переменную x₄.

Ниже приведена симплекс-таблица с выделенными разрешающей строкой и столбцом (таблица 6).

Таблица 6. - Симплекс-таблица (второе базисное решение) с выделенными разрешающей строкой и столбцом

базис	переменные	bi
	x1	x2	x3	x4	x5
x3	4	0	1	0	-6	60
x4	2	0	0	1	-6	12
x2	0	1	0	0	1	10
cj	2	0	0	0	-4	-40

Далее перейдем к шагу 8 и осуществим пересчет элементов симплексной таблицы в соответствии с правилами, приводимыми выше. Результат пересчета представлен в таблице 7.

Таблица 7. - Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах (третье базисное решение)

базис	переменные	bi
	x1	x2	x3	x4	x5
x3	0	0	1	-2	6	36
x1	1	0	0	1/2	-3	6
x2	0	1	0	0	1	10
cj	0	0	0	-1	2	-52

Таким образом, в очередном (третьем) базисном решении основными переменными являются: x₁ = 6, x₂ = 10, x₃ = 36. Неосновные переменные x₄ и x₅ равны нулю. Значение целевой функции для этого решения равно 52.

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

Шаг 5. Выберем разрешающий столбец. Им окажется столбец x₅, поскольку здесь содержится единственный положительный элемент нижней строки. Переменную x₅ будем переводить в основные.

Шаг 6. Проверка показывает, что в разрешающем столбце есть положительные элементы, следовательно, можно продолжать решение.

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

Для первой строки:

D₁ = 36 / 6 = 6.

Для третьей строки:

D₂ = 10 / 1 = 10.

Наименьший результат деления - в первой строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. переводить в неосновные (исключать из базиса) будем переменную x₃.

Ниже приведена симплекс-таблица с выделенными разрешающей строкой и столбцом (таблица 8).

Таблица 8. - Симплекс-таблица (третье базисное решение) с выделенными разрешающей строкой и столбцом

базис	переменные	bi
	x1	x2	x3	x4	x5
x3	0	0	1	-2	6	36
x1	1	0	0	1/2	-3	6
x2	0	1	0	0	1	10
cj	0	0	0	-1	2	-52

Далее перейдем к шагу 8 и осуществим пересчет элементов симплексной таблицы в соответствии с правилами, приводимыми выше. Результат пересчета представлен в таблице 9.

Таблица 9. - Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах (четвертое базисное решение)

базис	переменные	bi
	x1	x2	x3	x4	x5
x5	0	0	1/6	-1/3	1	6
x1	1	0	1/2	-1/2	0	24
x2	0	1	-1/6	1/3	0	4
cj	0	0	-1/3	-1/3	0	-64

Таким образом, в очередном (четвертом) базисном решении основными переменными являются: x₁ = 24, x₂ = 4, x₅ = 6. Неосновные переменные x₃ и x₄ равны нулю. Значение целевой функции для этого решения равно 64.

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

На рисунке 2. приведена общая схема симплексного алгоритма, наглядно показывающая порядок его реализации.[2]

Рисунок 2. - Общая схема симплекс-алгоритма

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

при условиях

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

при условиях

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

1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной- на минимум.

2. Матрица

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

в двойственной задаче получаются друг из друга транспонированием (т. е. заменой строк столбцами, а столбцов - строками).

3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи - коэффициенты при неизвестных в целевой функции исходной задачи.

5. Если переменная x_j исходной задачи может принимать только лишь положительные значения, то j-е условие в системе двойственной задачи является неравенством вида “? ”. Если же переменная x_j может принимать как положительные, так и отрицательные значения, то 1 - соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i - соотношение в системе исходной задачи является неравенством, то i-я переменная двойственной задачи . В противном случае переменная у_j может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения прямой задачи и соотношения двойственной задачи являются неравенствами вида “ ”. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.[3]

Вопросы

1. Что такое задачи линейного программирования?

2. В чем геометрический смысл задачи линейного программирования?

3. Какие основные методы линейного программирования?

4. Что такое симплекс метод?



Список литературы

1. Бурков В.Н., Новиков Д.А. Как управлять проект ами. М.: Синтег, 1997.

2. Исследование операций. Т 1, 2. М.: Мир, 1981.

3. Ларичев О.И. Теория и методы принятия решений. М.: Логос, 2000.

4. Ларичев О.И., Мошкович Е.М. Качественные методы принятия р ешений. М.: Наука, 1996.

5. Рыков А.С. Методы системного анализа: многокритериальная и н ечеткая оптимизация, моделирование и экспертные оценки. М.: Экономика, 1999.

6. Рыков А.С. Методы системного анализа: оптимизация. М.: Экон омика, 1999.

7. Васильев Ф.П. Методы оптимиз ации. М.: Факториал Пресс, 2002.

8. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. М.: Высш. шк ола, 1999.

9. Айвазян С.А., Мхитарян В.С. Прикладная статистика и основы эк онометрики. М.: ЮНИТИ, 1998.

10. Организационное управление / Н.И. Архипова, В.В. Кульба, С.А. Косяченко и др. М.: ПРИОР, 1998.

11. Ириков В.А., Тренев В.Н. Распределенные системы принятия реш ений. М.: Наука; Физматлит, 1999.

12. Мушик Э., Мюллер П. Методы принятия технич еских решений. М.: Мир, 1990.

13. Большие системы: моделирование организацио нных механизмов / В.Н. Бурков и др. М.: Наука, 1989.

14. Исследование систем управления / Н.И. Архипова, В.В. Кульба, С.А. Косяченко и др. М.: ПРИОР, 2002.

15. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование. М.: ФИЗМАТЛИТ, 2007.

16. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.

17. Дроздов Н. Д. Алгоритмы дискретного программирования. Тверь 2000

18. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.

19. Учебно-методические материалы для лабораторных и самостоятельных работ по курсу «Численные методы решения прикладных задач. Дискретное программирование. Комбинаторные методы» / Сост. Н. Д. Дроздов. - Калинин, 1990.

20. Бескровный И.М. Анализ альтернатив и?выбор диагностических гипотез. Часть I. Правило Байеса и?методы теории принятия решений // Международный журнал прикладных и?фундаментальных исследований. - 2012. - №1.

21. Исследование операции. т.2 Модели и?применения: пер. с?англ.; под ред. И.М. Бескровного, И.М. Макарова. - М.: Мир, 1981. - 677 с.

22. Теория выбора и?принятия решений: учебное пособие. - М.: Наука, 1982

23. Афанасьев А.М. Учет рисков и доходности альтернативных возможностей инвестирования при оценке эффективности инвестиционного проекта. // Аудит и финансовый анализ №6, 2008. «ДСМ Пресс» (1.1 п.л.).

24. Афанасьев А.М. Анализ эффективности инвестиционного проекта с учетом альтернативных возможностей при случайной величине издержек и дохода. // Аудит и финансовый анализ №3, 2010. «ДСМ Пресс» (0,9 п.л.).

25. Айвазян С.А., Афанасьев М.Ю., Афанасьев А.М.. Оценка экономической эффективности мероприятий банка по рекламированию кредитных продуктов. // Прикладная эконометрика №4(16) 2009. Москва. ООО «Маркет ДС Корпорейшн» (0,8 п.л., лично 0,3 п.л.)

26. Саати Т., Керыс К. Аналитическое планирование. Организация си стем. М.: Радио и связь, 1991.

27. Агальцов В.П. Математические методы в программирование. - М., 2009

28. Данко П.Е. Высшая математика в упражнениях и задачах: В 2т. учеб. пособ. - М.: Высш. шк., 2008

29. Ермаков В.И. Общий курс высшей математики для экономистов. М.: Инфра-М, 2006 г.

30. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании. М.: Дело, 2007 г.

31. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. Минск: Вышейшая школа, 2006 г.

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