WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:   || 2 |

«МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ПОДГОТОВКИ К ТЕСТИРОВАНИЮ ПО ДИСЦИПЛИНАМ МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ, МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ В ПРИНЯТИИ РЕШЕНИЙ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (ЧАСТЬ I) ...»

-- [ Страница 1 ] --

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ЭКОНОМИКИ И ФИНАНСОВ»

КАФЕДРА ВЫСШЕЙ МАТЕМАТИКИ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

ДЛЯ ПОДГОТОВКИ К ТЕСТИРОВАНИЮ

ПО ДИСЦИПЛИНАМ

«МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ»,

«МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ

В ПРИНЯТИИ РЕШЕНИЙ»

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (ЧАСТЬ I)

ИЗДАТЕЛЬСТВО

САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

ЭКОНОМИКИ И ФИНАНСОВ

Рекомендовано научно-методическим советом университета Методические указания для подготовки к тестированию по дисциплинам «Методы оптимальных решений», «Математические методы и модели в принятии решений». Линейное программирование (Часть I). – СПб.: Изд-во СПбГУЭФ, 2012. – 65 с.

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

Составители выражают благодарность В.Н. Десницкой за помощь в работе.

Составители: канд. экон. наук, доцент Н.Е. Авдушева, канд. физ.-мат. наук, доцент В.Г. Дмитриев, старший препод. О.Н. Коростелева, канд. физ.-мат. наук, доцент С.В. Петрас, д-р техн. наук, профессор В.А. Рыжов, д-р техн. наук, профессор Г.В. Савинов Рецензент канд. физ.-мат. наук, доцент И.К. Лицкевич © СПбГУЭФ, 1. Общие сведения 1.1. Общая задача линейного программирования (ЛП) состоит в вычислении оптимального (наибольшего или наименьшего) значения линейной целевой функции f ( X ) c1 x1 c2 x2... cn xn c0 на множестве D, которое определяется конечной системой линейных ограничений (нестрогих линейных неравенств и линейных уравнений). Каждая точка X ( x1, x2,..., xn ) из множества D называется допустимым планом задачи, а само множество D называется множеством, или областью, допустимых планов В дальнейшем для точек и n -мерных векторов используется одно и то же обозначение X ( x1, x2,..., xn ). Координаты x1, x2,..., xn называются компонентами плана Другими словами, допустимым планом называется план, компоненты которого удовлетворяют всем ограничениям задачи.





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

Поиск наибольшего значения целевой функции называется задачей на максимум, наименьшего – задачей на минимум. Соответственно используются обозначения f ( X ) Max и f ( X ) Min.

1.2. В следующих трех случаях решение задачи ЛП не представляет трудностей:

Opt 1) если f ( X ) c0 (целевая функция постоянная), то f c0, а D Opt D– все допустимые планы являются оптимальными планами;

2) если D (множество допустимых планов является пустым), то задача ЛП не имеет решения;

3) если D {a} (множество допустимых планов состоит из одной точки), Opt f (a) и DOpt {a}.

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

1.3. Множество допустимых планов задачи ЛП всегда является выпуклым n и замкнутым множеством в пространстве R (в частности, и пустое множество, и множество из одной точки считаются выпуклыми и замкнутыми). Выпуклость множества допустимых планов означает, что все точки отрезка, соединяющего любые два допустимых плана, являются допустимыми планами задачи.

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

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

Координаты вершины множества D R являются решением некоторой системы из n линейных уравнений. Эти n уравнений выбираются из совокупности уравнений, которые возникают после замены в исходных ограничениях знаков неравенства на знаки равенства. Рассматриваются только такие системы, которые имеют единственное решение (системы с ненулевым определителем).





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

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

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

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

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

1.6. Опорная гиперплоскость может пересекать выпуклое множество по отрезку, лучу (полупрямой) или целой прямой. В этом случае говорят, что на границе выпуклого тела имеется ребро или, соответственно, бесконечное ребро. Наглядные примеры ребер – стороны треугольника, ребра пирамиды или параллелепипеда. У круга на плоскости ребер нет. Лучи, ограничивающие угол на плоскости, являются его бесконечными ребрами.

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

Два опорных плана называются соседними, если они соединимы ребром.

1.7. Множество в пространстве Rn называется ограниченным, если оно целиком содержится внутри некоторого шара. Типичное ограниченное множество допустимых планов имеет, по крайней мере, две вершины. Если множество допустимых планов неограниченное, то оно содержит, по крайней мере, одно бесконечное ребро.

1.8. Примеры множеств допустимых планов на плоскости.

Четырехугольник ABCD ограниченное множество допустимых планов.

Точки A, B, C, D вершины.

MN, PQ опорные прямые, MN строго опорная прямая.

1.9. Множество уровня целевой функции f ( X ) определяется линейным уравнением c1 x1 c2 x2... cn xn c левая функция принимает одно и то же значение, равное t. В пространстве R множество уровня является гиперплоскостью, а при n = 2 (на плоскости) – прямой линией. В случае плоскости говорят о линиях уровня целевой функции.

В пространстве Rn множества уровня t R образуют семейство параллельных гиперплоскостей, а в случае плоскости семейство параллельных прямых.

Ненулевой вектор N = (c1, c2,…, cn) является нормальным вектором (нормалью) ко всем гиперплоскостям (линиям, если n = 2) уровня целевой функции. Имеется в виду, что этот вектор перпендикулярен (ортогонален) всем гиперплоскостям (линиям, если n = 2) уровня целевой функции.

1.10. Градиент функции в точке X является постоянным вектором (не зависящим от точки), ортогональным (перпендикулярным) к гиперплоскостям ее уровня (линиям уровня, если n = 2).

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

вестно, что для линейной функции ее приращение f ( X, X ) f ( X X) Если вектор X приращения аргумента ортогонален градиенту функции, f ( X, X ) d f ( X, X ) 0. При этом длина вектора X не имеет значето ния. Поэтому можно говорить, что приращение целевой функции в направлении, ортогональном градиенту, равно нулю.

Также можно говорить о знаке приращения целевой функции в направf (X, X ) d f (X, X ) f ( X ), X дует, что если скалярное произведение, то знак приращения функции положительный и функция возрастает в направлении вектора X. Есf ( X ), X убывает в направлении вектора X. Пусть – угол между векторами знак приращения целевой функции положительный (отрицательный), если угол острый (тупой).

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

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

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

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

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

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

1. Нахождение какого-либо опорного плана.

2. Выяснение, является ли опорный план оптимальным.

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

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

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

В матрично-векторной форме ограничения стандартной задачи ЛП кратко записывают следующим образом:

Здесь X ( x1, x2,..., xn ) – план, – матрица системы ограничений разn. B (b1, b2,..., bm ) – вектор правых частей ограничений, где bi могут мера m быть произвольными числами.

Подробная запись матрично-векторной формы ограничений имеет вид:

Если правые части ограничений стандартной задачи неотрицательные, то множество допустимых планов непустое, так как содержит, по крайней мере, один план O (0,0,...,0), который является опорным планом. Если условие неотрицательности правых частей не выполняется, то множество допустимых планов может оказаться пустым.

2.2. Задачу вида при условии, что ранг матрицы A равен m (числу ее строк), будем называть канонической задачей ЛП.

В отличие от стандартной задачи в канонической задаче все ограничения являются уравнениями и предполагается, что m n (при m n множество допустимых планов либо состоит из одной точки, либо пустое). Знаки правых частей уравнений могут быть произвольными.

2.3. Добавляя к m уравнениям системы ограничений n m уравнений, где k 1,..., n m, можно получить системы из n линейных ураввида jk нений с n неизвестными, ранг которых равен n. Для этого выбираются какиелибо m столбцов матрицы системы ограничений, образующие базисный (не равный нулю) минор, а дополнительные уравнения формируются для переменных, соответствующих остальным столбцам.

Допустимые (неотрицательные) решения таких систем являются опорными планами канонической задачи ЛП. Отсюда следует вывод.

Опорные планы канонической задачи ЛП содержат не менее чем n m нулевых компонент.

Пример. Пусть система ограничений канонической задачи имеет вид Решение этой системы X (0;0;2;1) является опорным планом.

При x2 0, x4 0 решение системы (15;0; 23;0) оказывается недопустимым. Еще один опорный план (6 5;0;0;23 25) получается при добавлении уравнений x2 0, x3 0. Решения остальных трех систем оказываются недопустимыми. Множество допустимых планов этого примера содержит ровно два опорных плана (две вершины).

2.4. Существует еще один подход к получению опорных планов задачи ЛП в канонической форме, основанный на разделении переменных на базисные и свободные – прием, используемый при решении неопределенных систем линейных уравнений. Выбирается любой набор из m столбцов матрицы, образующих линейно независимую систему. Такой набор образует базис в m -мерном пространстве R m, а переменные, соответствующие этим столбцам, называются базисными. Остальные переменные называются свободными, или небазисными.

Вектор B правых частей системы ограничений является элементом проm странства R и единственным образом представляется линейной комбинацией векторов выбранного базиса. Пусть, для определенности, базис состоит из поA1... An m An m Вектор (0;...;0; xn m 1 ;...; xn ) является одним из решений уравнения A X B.

Решение уравнения A X B, в котором все свободные переменные равны нулю, называется базисным решением. Допустимое базисное решение системы ограничений называется базисным планом задачи. Понятие базисного плана подразумевает разделение переменных на базисные и свободные.

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

Это равносильно тому, что переменные x3, x4 объявляются базисными, а x1, x2 – свободными. Полагая свободные переменные равными нулю, получаем систему уравнений для базисных переменных:

В итоге имеем базисный план X (0;0;2;1).

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

2.5. Отметим, что опорный и базисный план задачи ЛП в канонической форме содержат, по крайней мере, n m нулевых компонент. Однако план, содержащий n m нулевых компонент, может не быть опорным.

Опорный или базисный план, содержащий точно n m нулевых компонент, называется невырожденным. Если нулевых компонент больше, чем n m, то план (опорный или базисный) вырожденный. Применительно к базисному плану невырожденность означает, что все базисные переменные строго положительные. В вырожденном базисном плане имеются нулевые значения базисных переменных. Чтобы отличить нули базисных переменных от нулей свободных переменных будем отмечать их нижним подчеркиванием. Например, план X (1;3;0;6;0; 0) вырожденный, базисными переменными являются x1, x2, x4 и x6 и, а свободными – x3 и x5.

В случае вырождения одному опорному плану может отвечать несколько базисных планов, отличающихся только выбором свободных и базисных переменных. Например, разные базисные планы (1;3; 0;0;0) и (1;3;0;0; 0) отвечают одному опорному плану (1;3;0;0;0).

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

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

Отметим, что вершина множества допустимых планов – точка n -мерного пространства, фактически задается базисом m -мерного пространства, который выбирается из столбцов матрицы системы ограничений. Если базис выбран, то после решения соответствующей системы уравнений получаются значения базисных переменных. Будет ли найденное решение допустимым, зависит от выбора базиса.

Базис, соответствующий оптимальному плану задачи, называется оптимальным базисом.

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

2.7. Будем называть каноническую задачу ЛП канонической базисной (или приведенной), если в матрице условий имеются m столбцов, из которых можно составить единичную матрицу, а вектор правых частей B 0.

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

а в матрице A имеется m столбцов, из которых можно составить единичную матрицу (эти столбцы могут располагаться в произвольном порядке).

Отметим, что множество допустимых планов канонической базисной задачи содержит базисный план, в котором базисные переменные равны координатам вектора B.

Пример задачи ЛП в канонической базисной форме:

Матрица системы ограничений образованную четвертым и вторым столбцами (именно в таком порядке). Переменные x4 и x2 считаем базисными, переменные x1, x3 – свободными. Полагая 0, находим значения базисных переменных: x4 7, x2 5. В итоге получаем базисный план X (0;5;0;7). Значение целевой функции на этом плане равно нулю.

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

1. Задача на минимум (максимум) преобразуется в задачу на максимум (минимум) введением новой целевой функции f ( X ) f ( X ). Например, 2. Преобразование f 0 ( X ) f ( X ) c0 позволяет избавиться от коэффициента c0 в целевой функции. Например, 3. Умножение неравенства на минус единицу меняет его знак. Например, 4. Ограничение в виде уравнения эквивалентно системе из двух ограничений в виде неравенств. Например, 5. Любое неравенство можно превратить в уравнение с помощью дополнительных (или балансовых) неотрицательных переменных. В неравенство со знаком меньше или равно дополнительная переменная вводится со знаком плюс, в неравенство со знаком больше или равно – со знаком минус.

Например, при введении дополнительных переменных x3 0, x4 0 следующая система неравенств преобразуется в систему уравнений:

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

ная будет принимать только неотрицательные значения. Допустим, что переменная 2 может принимать произвольные (по знаку) значения. Так как любое число можно представить разностью двух неотрицательных чисел, то ввеx2, x2 x. Новые переменные x1, x2, x2 удовлетворяют условию неотрицательности. При этом целевая функция соответственно изменяется, например:

7. Допустим, что система ограничений задачи ЛП соответствует канонической базисной форме. Тогда каждая базисная переменная может быть выражена через свободные переменные. Исходная целевая функция после исключения базисных переменных преобразуется к приведенному виду.

Для примера рассмотрим задачу Первый и четвертый столбцы матрицы системы ограничений образуют единичную матрицу, поэтому переменные x1, x4 – базисные, x2, x3 – свободные.

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

Подставив найденные выражения в целевую функцию и приведя подобные члены, получаем f ( X ) в приведенной форме:

3.2. Пример. Приведем к канонической форме общую задачу ЛП.

Решение. Введем во второе и третье неравенства системы ограничений балансовые переменные x5 0 и x6 0, а переменную x3, не удовлетворяющую условию неотрицательности, представим в виде разности двух неотрицательных переменных: x3 x3 x3. Вместо целевой функции f ( X ) введем новую X ( x1, x2, x3, x3, x5, x6 ). В результате получаем новую задачу в канонической форме:

Расширенная матрица этой задачи имеет вид:

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

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

Пример. Приведем к канонической базисной форме стандартную задачу Решение. Добавляя неотрицательные балансовые переменные x5, x6, x7, преобразуем каждое неравенство в уравнение. Целевая функция новой задачи f ( X, X ), где X ( x5, x6, x7 ), фактически остается без изменений, так как балансовые переменные входят в нее с нулевыми коэффициентами. В результате получаем каноническую базисную задачу Расширенная матрица полученной задачи имеет вид:

Последние три столбца матрицы образуют единичную матрицу. В качестве базисных переменных естественно выбрать x5, x6, x7, переменные x1, x2, x3, x исходной задачи будут свободными. Целевая функция имеет приведенный вид.

4. Примеры задач ЛП 4.1. Задача производственного планирования Предприятие может выпускать n видов продукции, используя для этого m видов сырья. Обозначим через aij количество сырья вида i, необходимое для производства единицы продукции вида j. Пусть bi – запас сырья вида i. Прибыль (выручку), получаемую предприятием от реализации единицы продукции вида j, обозначим j.

План производства определяет объемы выпуска каждого вида продукции и может быть полностью охарактеризован переменными j – объемами выпуска продукции вида j. По своему смыслу эти переменные должны быть неотрицательными.

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

определяет количество сырья вида i, которое используется Произведение при выпуске планируемого объема j продукции вида j. Сумма всех таких проn равна количеству сырья вида i, необходимого для производизведений j ства всех видов продукции в планируемых объемах. Следовательно, для каждого i 1, m должно выполняться неравенство Критерием эффективности производственного плана естественно считать суммарную прибыль от реализации всей произведенной продукции. Произвеcx дение j j равняется прибыли, которая будет получена при реализации всей продукции вида j. Суммарная прибыль равна Требуется найти такой план выпуска продукции из имеющегося сырья, чтобы прибыль, получаемая при реализации этой продукции, была максимальной.

В итоге математическая модель задачи принимает вид:

4.2. Оптимизация рациона питания (задача о диете) Для откорма животных может быть использовано n видов кормов. Ежедневный рацион должен содержать m необходимых для животных полезных веществ (белков, жиров, углеводов, витаминов и т. п.). Известны содержание ij полезного вещества вида i в единице корма вида j и суточная потребность bi в веществе вида i. Известна стоимость j единицы каждого вида корма.

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

Математическая модель данной задачи запишется так:

5. Графический метод решения задачи ЛП 5.1. Графический метод решения задачи ЛП удобен для иллюстрации основных положений ЛП. Рассматривается задача с двумя переменными x1, x (или x, y), в которой все ограничения имеют вид неравенств. Алгоритм метода состоит из следующих шагов.

Шаг 1. Строится область допустимых планов. Проводится анализ области (ограниченная, неограниченная).

Шаг 2. Чертится какая-либо линия уровня целевой функции и градиент целевой функции (начало этого вектора удобно поместить на линию уровня).

Градиент и линия уровня должны быть перпендикулярны друг другу.

Шаг 3. Перемещая параллельно линию уровня, находим ее опорные положения по отношению к области допустимых планов.

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

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

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

Шаг 7. Вычисляется оптимальное значение целевой функции.

5.2. Пример ограниченной области. Из методических соображений будем рассматривать сразу две задачи ЛП – на максимум и на минимум.

Найдем оптимальные значения целевой функции f ( x, y) x 2 y 11 при следующих ограничениях на переменные:

Шаг 1. Построение области допустимых планов. Номера прямых соответствуют номерам ограничений. Стрелки у прямых показывают полуплоскости, определяемые неравенствами. В данном случае ни одна из прямых не проходит через начало координат и полуплоскость можно определить, проверяя положение точки (0;0) относительно прямой. Если координаты этой точки удовлетворяют неравенству, то она лежит в нужной полуплоскости. В результате получаем четырехугольник (выделен цветом). Область допустимых планов ограниченная. И задача на максимум, и задача на минимум будут иметь решения.

Шаг 2. Строим линию уровня целевой функции. Удобно рассмотреть уравнение x 2 y 11 11. После упрощений получаем уравнение x 2 y 0.

На рисунке эта линия уровня отмечена буквой L. Градиент целевой функции таточно нарисовать вектор (1;2). Любой из этих векторов определяет направление, в котором целевая функция возрастает быстрее всего.

Рассматриваем задачу на максимум.

Шаг 4. Нужное положение опорной линии уровня – прямая L2.

Шаг 5. Наибольшее значение целевой функции достигается в вершине C, решение единственное. Эта точка пересечения граничных прямых с номерами (1) и (3).

Рассмотрим задачу на минимум.

Шаг 4. Нужное положение опорной линии уровня – прямая L1.

Шаг 5. Наименьшее значение целевой функции достигается во всех точках ребра (отрезка) AB прямой (4). Действительно, посмотрев на уравнение прямой L: x + 2y = 0 и на уравнение прямой (4): x + 2y = 5, убеждаемся в параллельности этих прямых. Имеем альтернативный минимум. Для ответа придется искать координаты точки A, в которой пересекаются прямые с номерами (2) и (4), и координаты точки B, в которой пересекаются прямые с номерами (1) и (4).

мальные планы, лежащие на ребре AB, могут быть записаны как выпуклая линейная комбинация его концов:

5.3. Пример неограниченной области.

Пусть область допустимых планов задается следующей системой ограничений:

Рассмотрим обе задачи ЛП – на максимум и на минимум.

Шаг 1. Построение области допустимых планов. Номера прямых соответствуют номерам ограничений. Стрелки у прямых показывают полуплоскости, определяемые неравенствами. И в данном случае нужные полуплоскости можно определить, проверяя положение точки (0;0) относительно прямых.

Без особых проблем рисуются прямые с номерами (1), (2), (3) и (5). Однако при проведении четвертой прямой неточности рисунка могут привести к серьезным затруднениям. Дело в том, что если на плоскости проведены две пересекающиеся прямые, то при проведении третьей прямой надо точно знать, проходит она или не проходит через точку пересечения первых двух. При наличии сомнений для ответа на этот вопрос придется найти координаты точки пересечения и подставить их в уравнение третьей прямой.

В данном случае прямые с номерами (1) и (3) пересекаются в точке A (2; 2), а четвертая прямая имеет уравнение x = 2. Следовательно, четвертая прямая проходит через точку A.

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

Анализ полученной области показывает, что имеется два бесконечных ребра – AP и BQ. На всякий случай, можно (нужно, если прямые почти параллельные) проверить, что точка пересечения прямых (2) и (3) лежит в третьей четверти. В результате имеем неограниченную область допустимых планов (она выделена цветом). Ответ на вопрос, какая из задач (на максимум или на минимум) имеет решение, зависит от целевой функции.

Шаг 2. Строим линию уровня целевой функции. Удобно рассмотреть 2x y 0. На рисунке эта линия уровня отмечена буквой L. Грауравнение диент данной целевой функции равен f ( x, y) ( 2;1) (или 2i j ). На рисунке изображен вектор с координатами ( 1;1 2), сонаправленный с вектором ( 2;1). В направлении этого вектора целевая функция возрастает.

Шаг 3. Имеется единственное опорное положение линии уровня – прямая L1.

На рисунке проведена еще одна линия уровня – прямая L*. Видно, что при смещении вправо линия уровня никогда не станет опорной.

Рассматриваем задачу на максимум.

Шаг 4. Нужное положение опорной линии уровня – прямая L1. На этой прямой целевая функция принимает самое большое значение.

Шаг 5. Наибольшее значение целевой функции достигается в вершине A, решение единственное.

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

Теперь рассмотрим задачу на минимум.

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

Ответ задачи на минимум: решения нет.

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

Пример 1. Решить задачу ЛП:

Так как система ограничений задачи содержит одно уравнение, то число переменных можно уменьшить на единицу. Используя уравнение, выразим, например, переменную x2 через остальные переменные: x2 1 x1 x3. Полученное выражение подставляем в первое неравенство, в целевую функцию и в неравенство x2 0. В результате получаем новую задачу ЛП с двумя переменными:

2, а f Opt 15. Следовательно, решением исходной задачи ЛП является пара Пример 2. Решить задачу ЛП:

Так как система ограничений задачи содержит три уравнения с пятью неизвестными, то число переменных можно понизить до двух, выразив, например, переменные x3, x4, x5 через x1 и x2:

Подставив найденные выражения для переменных x4, x3, x5 в целевую двумя переменными:

Решая эту задачу графическим методом (см. Рис. 2), найдем 2, а f Opt 7. Следовательно, решением исходной задачи ЛП является пара X 6. Симплекс-метод решения задач ЛП 6.1. Табличный симплекс-метод применяется для решения задач ЛП в канонической базисной форме. Для таких задач выполняются следующие условия:

Все переменные x1, x2,..., xn неотрицательные.

Все m ограничений имеют вид уравнений, и m n.

Правые части ограничений b1, b2,..., bm неотрицательные.

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

Целевая функция f ( X ) содержит только небазисные (свободные) переменные.

Рассматривается задача на максимум: f ( X ) Max.

Алгоритм решения состоит из нескольких шагов.

Шаг 1. Составление и анализ (первой) симплексной таблицы. Данные задачи заносятся в первую симплекс-таблицу. Рассматриваемый вариант симплекс-таблицы имеет вид расширенной матрицы системы ограничений, дополненной так называемой индексной строкой, в которой записываются коэффициенты (с противоположными знаками) и значение целевой функции.

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

Столбцы матрицы с номерами 4, 2 и 6 (именно в этом порядке) образуют единичную матрицу, поэтому x4, x2, x6 – базисные переменные, а x1, x3, x5 – свободные переменные. Первая симплексная таблица имеет вид:

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

Сформулируем правило заполнения индексной строки.

Индексная строка начинается с краткого обозначения целевой функции (в данном случае – буква f ), далее записываются коэффициенты при переменных целевой функции с противоположным знаком и ноль в столбце B.

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

Коэффициенты полученного равенства помещаются в индексную строку.

6.3. Анализ полученной симплексной таблицы. Для получения первого базисного плана полагаем свободные переменные равными нулю. Система ограничений принимает вид Из этой системы немедленно получаем значения базисных переменных.

В симплекс-таблице значения базисных переменных расположены в столбце, озаглавленном буквой B.

В результате имеем первый базисный план X (0;1;0;2;0; 0). Этот план оказался вырожденным, так как значение базисной переменной x6 0. Значение целевой функции f ( X ) 2 0 3 0 4 0 0. Это число находится в последней ячейке столбца B.

Числа, стоящие в индексной строке (исключая последнее), называются оценками (переменных) базисного плана. При этом все оценки базисных переменных в симплекс-таблице равны нулю (целевая функция выражается только через свободные переменные). Обозначим оценки базисного плана символом j, здесь j – номер переменной. В типичной задаче ЛП имеются ненулевые оценки первого базисного плана. Оценки базисного плана позволяют делать вывод об оптимальности полученного базисного плана. Сформулируем достаточный признак оптимальности базисного плана Если все оценки базисного плана неотрицательные, то базисный план является оптимальным.

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

Наличие отрицательной оценки требует продолжения исследования.

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

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

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

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

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

6.5. Шаг 2 – улучшение базисного плана. Любую из свободных переменных с отрицательной оценкой можно сделать базисной переменной. Применительно к столбцам таблицы говорят о переводе соответствующего столбца в базис Традиционно выбирают столбец, отвечающий свободной переменной с наибольшей по модулю отрицательной оценкой. Если таких переменных несколько, то рекомендуется выбирать первый столбец слева. Выбираемый столбец называется разрешающим (ведущим или ключевым) столбцом, а описанная процедура называется выбором разрешающего столбца.

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

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

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

6.6. Приступаем к выбору базисной переменной, которая в следующей таблице станет свободной. С этой целью рассматриваем отношения i ij, где bi 0 – правая часть ограничения с номером i (последний элемент строки с номером i ), а ij – соответствующий элемент разрешающего столбца. Отношеa ния рассматриваются только для тех строк, в которых элемент ij (строго положительный). В таблице эти отношения можно разместить в дополнительном столбце справа. Выбирается строка, для которой это отношение наименьшее. Выбранная строка также называется разрешающей строкой. Если строк с наименьшим отношением несколько, то рекомендуется выбирать первую сверху (или снизу) строку. Сформулируем правило выбора разрешающей строки.

В качестве разрешающей строки выбирается строка с наименьшим отноb /a a шением i ij, где ij. Если таких строк несколько, то рекомендуется выбирать первую строку сверху.

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

В рассматриваемом примере имеется единственное положительное отношение b1 / a15 2, поэтому разрешающей является строка с номером 1. В следующей симплекс-таблице переменная x4 станет свободной. В таблице 1 разрешающая строка выделена цветом. Первая симплексная таблица принимает следующий вид:

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

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

Если в разрешающей строке bi 0, то при переходе к новому базисному bi 0, то при переходе к новому базисному плану значение целевой функции не изменится.

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

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

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

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

6.8. Повторяем первый шаг. Анализ полученной симплекс-таблицы приX2 (0;5;0;0;2;2) не- водит к следующим результатам. Новый базисный план вырожденный и неоптимальный, так как имеется отрицательная оценка Значение целевой функции f ( X ) 8.

6.9. Повторяем второй шаг. Переменную x3 можно сделать базисной (в столбце имеются положительные элементы). Сравнивая отношения b2 / a23 5 / 2 и b3 / a33 1/ 2, заключаем, что базисная переменная x6 в новом плане становится свободной. При этом значение целевой функции возрастет на ( 1) (2 / 4) 1/ 2. Очередная симплекс-таблица имеет вид:

величину 6.10. Третий базисный план оптимальный (нет отрицательных оценок). Оптимальное значение целевой функции f f ( X ) 17 / 2. Остается ответить на вопрос, является ли полученный оптимальный план единственным.

Шаг 3. Следующее правило дает ответ на поставленный вопрос.

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

Так как в последней таблице нет нулевых оценок свободных переменных, то найденное оптимальное решение единственное. Решение задачи закончено:

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

6.12. Выпишем первую и последнюю симплекс-таблицы рассматриваемой задачи:

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

Обозначим буквой S матрицу, образованную базисными столбцами. В данном случае Оптимальный план однозначно определяется значением базисных переOpt менных (все свободные переменные равны нулю). Обозначим X B вектор, образованный из базисных переменных оптимального плана. Порядок компонент этого вектора определяется порядком базисных переменных в столбце Б поOpt следней симплексной таблицы. В рассматриваемой задаче Полагая в системе ограничений свободные переменные нулями, получаем уравнение (систему уравнений) для базисных переменных: S X B B, где B – вектор правых частей исходной системы ограничений. Матрица S обратимая, Матрицу Q можно найти в последней симплексной таблице. Четвертый, второй и шестой столбцы матрицы ограничений первой симплексной таблицы образуют единичную матрицу. Матрица, образованная такими же столбцами в последней таблице, и есть матрица Q. В данном случае Рассмотрим новую задачу, которая отличается от исходной только вектором правых частей системы ограничений. Пусть B – новый вектор. В следующей ситуации матрица Q позволяет сразу найти оптимальное решение новой задачи.

Если выполняется условие Q B 0, то план, в котором базисные переOpt менные определяются формулой планом измененной задачи.

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

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

Вычислим Все компоненты полученного вектора положительные, следовательно, план X (0;3;1;0;3) является оптимальным планом новой задачи. Оптимальное значение целевой функции равно f f (X ) 2 0 3 1 4 3 9.

Если условие Q B 0 не выполняется, то новую задачу придется решать с самого начала.

6.13. Выпишем еще раз первую и последнюю симплекс-таблицы рассматриваемой задачи:

Четвертый, второй и шестой столбцы матрицы ограничений в первой таблице образуют единичную матрицу E. Оценки соответствующих этим столбцам переменных в последней таблице называются двойственными оценками оптимального базисного плана задачи ЛП в канонической базисной форме. Название связано с так называемой двойственной задачей ЛП, оптимальное решение которой совпадает с этими оценками. Двойственные оценки имеют специальное обозначение yi, причем номер двойственной оценки совпадает с номером ограничения в первой симплексной таблице.

Из первой таблицы видно, что двойственные оценки образованы оценками переменных x4, x2 и x6 (именно в этом порядке расположены столбцы единичной матрицы в первой таблице). Из последней таблицы следует, что 6.14. Двойственные оценки обладают следующими важными свойствами.

Двойственные оценки задачи ЛП в канонической базисной форме неотрицательные.

Утверждение является следствием условия оптимальности базисного плана.

Сумма произведений двойственных оценок и правых частей системы ограничений исходной задачи равна оптимальному значению целевой функции: y1 b1 y2 b2... ym bm f.

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

В частности, с помощью этого свойства можно проверять правильность Из формулы f y1 b1 y2b2... ymbm немедленно следует, что при изменении правой части ограничения с номером i на единицу оптимальное значение целевой функции изменится на величину двойственной оценки yi (конечно, при условии, что найденный базис остается оптимальным).

В рассматриваемом примере увеличение изменение b1 на единицу привеа изменение b2 не менядет к изменению оптимального значения на y ет оптимального значения, так как Произведение двойственной оценки yi и значения соответствующей оценка yi сматриваемый план базисный, то. k (i ) 7. Решение задачи производственного планирования симплексметодом 7.1. Предприятие может выпускать 3 вида продукции П1 П3, используя для этого 4 вида сырья М 1 М 4. Количество сырья каждого вида, необходимое для производства единицы продукции, запасы сырья и прибыль от реализации единицы продукции приведены в следующей таблице.

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

Математическая модель этой задачи имеет следующий вид:

С помощью дополнительных (балансовых) переменных x4, x5, x6, x7 преобразуем стандартную задачу к канонической базисной форме:

Здесь дополнительные переменные x4, x5, x6, x7 играют роль базисных переменных, целевая функция имеет приведенный вид. Составляем первую симплексную таблицу.

Базисные переменные x4, x5, x6, x7. Свободные переменные x1, x2, x3.

Первый базисный план X (0;0;0;30;66;50;48) невырожденный и неоптии 3 20.

мальный, так как есть отрицательные оценки Значение целевой функции В качестве разрешающего выбираем третий столбец. В следующем плане переменная x3 будет базисной. Минимальное отношение для элементов третьего столбца равно b2 / a23 66 / 5. В следующем плане переменная x2 станет свободb2 / a23 ) ( 20) 66 / Получаем вторую симплекс-таблицу:

Базисные переменные x3, x4, x6, x7. Свободные переменные x1, x2, x5. Второй базисный план X (0;0;66 / 5;18 / 5;0;118 / 5;174 / 5) невырожденный и неи 2 2. Значение оптимальный, так как есть отрицательные оценки целевой функции f ( X ) 264.

В качестве разрешающего столбца выбираем первый. В следующем плане переменная x1 будет базисной. Минимальное отношение для элементов первого столбца равно b1 / a Целевая функция увеличится на Переходим к третьей симплекс-таблице:

Базисные переменные x1, x3, x6, x7. Свободные переменные x2, x4, x5. Третий базисный план X (9;0;6;0;0;20;24) невырожденный и неоптимальный, так как есть отрицательная оценка В качестве разрешающего выбираем второй столбец. В следующем плане переменная x2 будет базисной. Минимальное отношение для элементов второго столбца равно b2 / a428. В следующем плане переменная x7 станет свободной.

Значение целевой функции увеличится на Переходим к четвертой таблице:

Базисные переменные x1, x2, x3, x6. Свободные переменные x4, x5, x7. Четвертый базисный план X (5;8;6;0;0;4;0) невырожденный, оптимальный и единственный, так как оценки всех свободных переменных положительные.

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

Максимальная прибыль от реализации возникнет при производстве пяти единиц первой, восьми – второй и шести единиц третьей продукции и составит 290 условных единиц.

7.2. В оптимальном плане преобразованной задачи дополнительные переменные x4 x5 x7 0. Следовательно, на оптимальном плане исходной задачи первое, второе и четвертое ограничения выполняются как равенства.

Дополнительная переменная x6 = 4 – положительная. На оптимальном плане третье ограничение исходной задачи выполняется как строгое неравенство.

При выполнении оптимального плана ресурсы (запасы) первого, второго и четвертого сырья расходуются полностью. Такие ресурсы называются дефицитными. Третий ресурс оказывается недефицитным, так как после выполнения оптимального плана останется его запас в количестве x6 = 4 единиц.

y3 0, y4 1/ 3 однозначно соответствует нумерации ресурсов. В оптимальном плане преобразованной задачи дополнительная переменная x6 4 – базисная и ее оценка (третья двойственная оценка) равна нулю. При этом третий ресурс является недефицитным.

В оптимальном плане недефицитным ресурсам отвечают нулевые двойственные оценки. Положительным двойственным оценкам отвечают дефицитные ресурсы.

Отметим, что дефицитному ресурсу может отвечать нулевая двойственная оценка. В рассматриваемом примере двойственные оценки y1, y2, y4, отвечающие дефицитным ресурсам, оказались положительными. Это обстоятельство позволяет рассматривать двойственные оценки как некоторую ценность ресурсов, используемых в производстве. При этом ценность недефицитных ресурсов нулевая – они и так имеются в избыточном количестве.

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

Для примера рассмотрим задачу (I) в стандартной форме:

С помощью неотрицательных балансовых переменных x5, x6, x7 неравенства преобразуются в уравнения. Получаем новую задачу (I I) в канонической форме следующего вида:

уравнений не удовлетворяют условию неотрицательности.

После умножения первого и третьего уравнений на минус единицу правые части системы ограничений становятся положительными и задача (II) принимает вид:

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

В этой матрице имеется только один единичный столбец, а именно A6.

Введем в первое и третье уравнения неотрицательные искусственные переменные x8 x9 и так, чтобы появились дополнительные единичные столбцы:

Расширенная матрица получившейся системы ограничений имеет следующий вид:

Она содержит единичную матрицу E = (A8 A6 A9) и неотрицательный вектор правых частей. Базис {A8 A6 A9}, построенный с помощью искусственных переменных x8 и x9, называется искусственным базисом. Полученная система ограничений соответствует канонической базисной форме.

8.2. В отличие от балансовых переменных, которые вводятся в целевую функцию с нулевыми коэффициентами, использование искусственных переменных (искусственного базиса) предполагает построение вспомогательной целевой функции f ( X ) и решение вспомогательной задачи f ( X ) Max для построенной системы ограничений. В результате решения вспомогательной задачи либо возникает первый опорный план канонической задачи (II), либо выясняется, что исходная задача не имеет ни одного опорного плана.

Существует два способа построения вспомогательной целевой функции.

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

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

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

Для метода искусственной функции приведенное условие означает, что найден оптимальный план вспомогательной задачи вида O (0,...,0) вектор искусственных переменных, а вспомогательная целевая функция достигает своего оптимального значения этом план X является базисным для исходной задачи, а значение исходной целевой функции равно f ( X ).

Для M - задачи возникает базисный план такого же вида ( X, O), где план X * является базисным для исходной задачи, а значения исходной и вспомогаf ( X *, O).

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

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

8.3. Пример построения канонической базисной формы методом искусственной функции. После введения балансовых и искусственных переменных задача (I) из 8.1 принимает вид:

Базисные переменные x8, x6 и x9. Вспомогательную целевую функцию f (X, X ) x8 x9 выражаем через свободные переменные. Из первого и третьего уравнений системы ограничений находим x8 7 2 x1 x2 x3 2 x4 x5, Получаем вспомогательную задачу в канонической базисной форме:

8.4. Симплексная таблица для вспомогательной задачи дополняется еще одной индексной строкой – для исходной целевой функции. Этот прием позволяет автоматически получать значения исходной целевой функции в процессе решения вспомогательной задачи.

Оценки вспомогательной задачи находятся в последней строке. Первый базисный план X (0,0,0,0,0,3,0,7, 2) невырожденный и неоптимальный, так как оценка третья. Искусственная базисная переменная х9 в следующей таблице становится свободной, поэтому элементы девятого столбца можно не вычислять. Индексная (предпоследняя) строка исходной задачи преобразуется при переходе к следующему базисному плану по стандартному правилу. При этом происходит пересчет целевой функции исходной задачи. Получаем следующую симплексную таблицу.

План X (1,0,0,0,0, 2,0,5,0) не является оптимальным, так как есть отрицательные оценки элементов для второго и четвертого столбца показывает, что в любом случае разрешающей строкой будет первая, искусственная базисная переменная х становится свободной, а приращение искусственной целевой функции будет равно 5. В качестве разрешающего столбца выбираем четвертый (переменная х становится базисной). Искусственная переменная х8 на следующем шаге становится свободной, поэтому вычисления в восьмом столбце и в нижней индексной строке можно не делать. Нулевые значения искусственных переменных означают, что получено оптимальное решение вспомогательной задачи. Переходим к следующей симплексной таблице.

Решение вспомогательной задачи закончено. Получен ее оптимальный X3 (5 / 2,0,0,1,0,3 / 2,0,0,0), в котором все искусственные переменные план стали свободными. Удаляя ненужные больше столбцы с искусственными переменными и индексную строку для искусственной целевой функции, получаем План X неоптимальный, так как есть три отрицательных оценки их элементов показывает, что если сделать базисной переменную х3, то свободной становится переменная х6, при этом приращение целевой функции будет ременную х5, то свободной также становится х6, а приращение целевой функции (b2 / a25 ) ( 2 / 5) ((3 / 2) (1/10)) 6. Если сделать базисной переменную х7, то целевая функция увеличится на 9 / 4. Поэтому выбираем в качестве разрешающих пятый столбец и вторую строку. Следующая таблица оказывается последней.

План X (7,0,0, 4,15,0,0) оптимальный, невырожденный и единственf Opt f ( X 2 ) 10. Решение канонической задачи ный. Оптимальное значение из пункта 8.1 закончено. Отбрасывая балансовые переменные х5, х6, и х7, полуOpt 8.5. Пример построения M - задачи. После введения балансовых и искусственных переменных задача (I I) из 8.1 принимает вид:

Базисные переменные х6, х8 и х9. Целевая функция вспомогательной M - задачи f ( X, X ) 2 x1 3x2 x3 x4 M x8 M x9. Вспомогательную целевую функцию выражаем через свободные переменные. Из первого и третьего уравнений системы ограничений находим Получаем каноническую базисную форму M - задачи:

8.6. Целью решения M - задачи является перевод в процессе улучшения опорных планов всех искусственных переменных в свободные. Составляем первую симплексную таблицу для M - задачи.

Опорный план X (0,0,0,0,0,3,0,7, 2) неоптимальный, его можно улучшить. Единственная отрицательная оценка x1 становится базисной, а искусственная переменная x9 свободной. При построении следующей таблицы элементы девятого столбца можно не вычислять.

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

Удалив столбцы с искусственными переменными и знак вспомогательной целевой функции, получаем первую таблицу и первый базисный план X1 (5 / 2,0,0,1,0,3 / 2,0) для задачи (II) (такие же, как и в методе искусственной целевой функции):

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

8.7. Задача (II) в канонической форме из 8.1 имеет вид:

Составим для нее таблицу с расширенной матрицей и сравним ее с последней симплексной таблицей 4.2 из 8.4.

Столбцы A, A и A матрицы A системы ограничений в таблице 4-2 образуют единичную матрицу. Соответствующие столбцы в матрице A исходной мере базисные столбцы образуют матрицу. Значения базисных переменных в оптимальном плане удовлетворяют уравнению Пятый, шестой и седьмой столбцы матрицы A системы ограничений заI I) образуют единичную матрицу. Столбцы матрицы Q Q Q Q расдачи положены на соответствующих местах в таблице 4.2: Q A, Q Q3 A7.

Матрица Q позволяет ответить на вопрос, останется ли найденный базис оптимальным при изменении вектора B правых частей системы ограничений, и получить оптимальное решение измененной задачи.

8.8. Двойственные оценки оптимального плана канонической задачи (II) и стандартной задачи (I) равны оценкам переменных, отвечающих единичным y3 1. С помощью двойственных оценок можно оценить изменение оптимального значения целевой функции при изменении правой части какого-либо ограничения. В частности, можно проверить выполнение равенства Пусть в условиях рассматриваемой задачи (I I) правая часть третьего решение новой задачи (II ) X (8,0,0,5,19,0,0), приращение целевой функции равно y3 1, и f 11. Применительно к задаче (I) новый оптиOpt мальный план X 8.9. С помощью симплекс-метода можно искать двойственные оценки оптимального плана задачи ЛП в канонической форме. Рассмотрим следующую задачу:

После введения искусственных неотрицательных переменных х6, х7 и х система ограничений принимает вид:

Составляем первую симплекс-таблицу.

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

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

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

Разрешающий столбец пятый, а разрешающая строка третья. Переходим к следующей таблице.

Все оценки переменных, исключая искусственные, неотрицательные, поOpt лучен оптимальный план X (5;0;4;0;15) и оптимальное значение целевой Двойственные оценки оптимального плана задачи в канонической форме равны оценкам искусственных переменных.

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

Из таблицы 5-1 видно, что оптимальный базис образован третьим, первым и пятым столбцами матрицы системы ограничений. Пусть S матрица, столбцами которой являются базисные столбцы, C вектор из коэффициентов целевой функции при базисных переменных (в соответствующем порядке).

Вектор Y, составленный из двойственных оценок оптимального плана, являетC Б (буква T означает операцию транспонироT вания). В данном случае и уравнение для двойственных оценок имеет вид:

Решив это уравнение, получаем двойственные оценки оптимального плана: y 21 25, y2 2 75, y3 1 15.

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

Используя метод M - задачи, преобразуем вспомогательную целевую функцию к приведенному виду и составим первую симплекс-таблицу.

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

Разрешающий столбец второй, разрешающая строка вторая. Переходим к следующей таблице.

В этой таблице разрешающим столбцом является третий, а разрешающей строкой первая. Переходим к следующей таблице.

Так как все искусственные переменные стали свободными, то, полагая 0, получим новую таблицу.

Здесь разрешающий столбец пятый, а разрешающая строка первая.

Переходим к следующей таблице.

Все оценки переменных, исключая искусственные, неотрицательные. ТаOpt 9. Задания для самостоятельного решения Задание I. Рассмотрим систему неравенств Справедливо ли утверждение?

– множество решений данной системы неравенств.

– множество решений данной системы неравенств.

– множество решений данной системы неравенств.

множеством решений (допустимых планов).

множеством решений (допустимых планов).

8. Существует система линейных неравенств, для которой 1 4 является множеством решений (допустимых планов).

Задание II. Пусть ABCDE – множество допустимых решений некоторой системы линейных неравенств, Справедливо ли утверждение?

9. Направление, в котором целевая функция убывает быстрее всего, определяется вектором (c2 ; c1 ).

10. Линии уровня функции f ( X ) параллельны вектору ( c2 ; c1 ).

11. Существует целевая функция f ( X ), для которой X G.

ществует такая целевая функция f ( X ), что f ( F ) f ( H ) f ( A).

16. Существует целевая функция Задание III. Дана система ограничений Справедливо ли утверждение?

17. Прямая 3x1 2 x2 24 0 является опорной прямой для множества допустимых решений системы ограничений.

18. План X (1;1) является точкой максимума при некотором выборе коэффициентов целевой функции f ( X ).

19. План X (5; 4) является единственной точкой минимума при некотором выборе коэффициентов целевой функции f ( X ).

X 1 (2;1 2) и X 2 (6; 2) одновременно являются оптимальными 20. Планы при некотором выборе коэффициентов целевой функции f ( X ).

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

22. Для любого значения t [0,1] план X t X4 (4; 6), является оптимальным планом при некотором выборе коэффициентов целевой функции f ( X ).

Справедливо ли утверждение?

прямой 4 x1 6 x2 11 0.

вующее приращениям переменных x1 5 и x2 4, больше нуля.

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

28. Первое условие системы ограничений можно записать в виде:

29. Второе условие системы ограничений можно записать в виде:

30. Целевая функция f ( X ) задачи ЛП в канонической форме имеет вид:

31. Преобразованная задача ЛП является канонической базисной:

А. Является, так как ранг матрицы коэффициентов системы ограничений равен числу уравнений.

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

Г. Является, ибо систему ограничений можно выбрать так, чтобы матрица условий содержала единичную матрицу.

Задание VI. Рассмотрим каноническую задачу ЛП Справедливо ли утверждение?

32. Три переменные, взятые в определенном порядке, являются базисными в том смысле, что соответствующие им столбцы матрицы коэффициентов образуют единичную матрицу; остальные переменные – свободные:

А. x3, x5, x6 базисные переменные;

33. Допустимым базисным решением (опорным планом) является вектор:

34. Целевая функция в приведенной форме имеет вид:

Задание VII. На некотором этапе решения задачи ЛП симплекс-методом получена таблица:

Справедливо ли утверждение?

37. Если 38. Ограничение, соответствующее второй строке симплекс-таблицы, имеет вид 7 x3 x4 3x5 4 x6 7.

39. Если 3 2, 5 3, 6 1, то соответствующий таблице опорный план является единственным оптимальным опорным планом задачи ЛП.

40. Если 3 1, 5 2, 6 3, то соответствующий таблице опорный план можно улучшить, введя в базис свободную переменную х6 вместо базисной переменной х4.

41. Если 3 0, 5 2, 6 3, то кроме соответствующего таблице оптимального опорного плана существует, по крайней мере, еще один оптимальный опорный план.

42. Если 3 2, 5 0, 6 1, то множество оптимальных планов задачи ЛП является неограниченным.

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

приращение целевой функции 46. Если 3 2, 5 1, 6 3, то целевая функция является неограниченной на множестве допустимых планов.

Задание VIII. Используя метод искусственного базиса, привести каноническую задачу ЛП к канонической базисной форме.

Справедливо ли утверждение?

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

А. Прибавить к левым частям уравнений неотрицательные искусственные переменные х6, х7, х8 соответственно.

Б. Умножив первое уравнение на –1, прибавить к левым частям уравнений неотрицательные искусственные переменные х6, х7, х8 соответственно.

В. Умножив первое уравнение на –1, прибавить неотрицательную искусственную переменную х6 к левой части третьего уравнения.

Г. Умножив первое уравнение на –1, прибавить неотрицательные искусственные переменные х6, х7, к левой части первого и третьего уравнений соответственно.

48. Вспомогательная целевая функция f ( X, X ) будет иметь вид:

49. При заполнении первой симплекс-таблицы индексная строка для приведенной целевой функции f ( X ) будет иметь вид:

50. Вторая индексная строка для приведенной вспомогательной целевой функции f ( X, X ) будет иметь вид:

51. В случае использования метода искусственного базиса в форме М - задачи, вспомогательная целевая функция f ( X, X ) будет иметь вид:

52. Индексная строка первой симплекс-таблицы для М - задачи имеет вид:

Задание IX. На некотором этапе решения задачи ЛП с искусственными переменными х5 и х6 получена симплекс-таблица:

Справедливо ли утверждение?

ную x2 вместо искусственной переменной x5, получим оптимальный опорный план X (18; 4; 0; 0; 0; 0) вспомогательной задачи ЛП. В этом случае X (18; 4; 0; 0) является неоптимальным опорным планом исходной задачи ЛП.

54. Если 3 ( f ) 6 а 2 ( f ) 4( f ) 1, то, вводя в базис свободную переменную x4 вместо искусственной переменной x5, получим оптимальный опорный план X (10; 0; 0; 4) является неединственным оптимальным опорным планом исходной задачи ЛП.

55. Если 3 ( f ) 5 а 2 ( f ) 4( f ) 1, то, вводя в базис свободную переменную х4 вместо искусственной переменной х5, получим оптимальный опорный план X (10; 4; 0; 0; 0; 0) вспомогательной задачи ЛП. В этом случае исходная задача ЛП не имеет решения из-за неограниченности целевой функции f ( X ) на множестве допустимых планов.

56. Если 3 ( f ) 3 а 2 ( f ) 4 ( f ) 1, то соответствующий таблице опорный план X (2; 0; 0; 0; 4; 0) является оптимальным опорным планом вспомогательной задачи ЛП. В этом случае исходная задача ЛП не имеет решения из-за несовместности системы ограничений.

Задание X. На некотором этапе решения М - задачи ЛП с искусственными переменными х5 и х6 получена симплекс-таблица:

Справедливо ли утверждение?

57. Если переменную х1 вместо искусственной базисной переменной х6, получим единственный оптимальный план X (2;9;0;0) исходной задачи ЛП, так как план X (2; 9; 0; 0; 0; 0) является единственным оптимальным планом М - задачи.

58. Если 1 1 M, 3 4 2M, 4 2 M, то, вводя в базис свободную переменную х4 вместо искусственной базисной переменной х6, получим, что множество оптимальных планов исходной задачи ЛП является неограниченным, ибо неограниченным является множество оптимальных планов М - задачи.

59. Если 1 2 M, 3 2 M 5, 4 3 M, то, вводя в базис свободную переменную х1 вместо искусственной переменной х6, получим, что исходная задача ЛП не имеет решения из-за неограниченности целевой функции f ( X ) на множестве допустимых планов, так как целевая функция М - задачи является неограниченной на множестве допустимых планов.

60. Если 1 M 2, 3 2 M 1, 4 M 3, то исходная задача ЛП не имеет решения из-за несовместности системы ограничений, так как М – задача Задание XI. Найти оптимальный план и оптимальное значение целевой функции следующих задач ЛП:

61. Найти максимальное и минимальное значения f ( X ) 1 3x1 6 x2 при ограничениях 62. Решить графическим методом задачу ЛП 63. Решить графическим методом задачу ЛП 64. Решить симплексным методом задачу ЛП 65. Решить симплексным методом задачу ЛП 66. Решить симплексным методом задачу ЛП 67. Предприятие может выпускать 3 вида продукции П1 П3, используя для этого вида сырья M1 M 3. Количество сырья каждого вида, необходимое для производства единицы продукции, запасы сырья и прибыль от реализации единицы продукции (в некоторых условных единицах) приведены в следующей таблице:

Составить план производства, при выполнении которого прибыль от реализации произведенной продукции будет наибольшей.

68. Решить методом искусственного базиса задачу ЛП 69. Решить методом искусственного базиса задачу ЛП 70. Решить симплексным методом задачу ЛП 1. Нет; 2. Да; 3. Нет; 4. Да; 5. Нет; 6. Да; 7. Нет; 8. Нет.

9. Нет; 10. Да; 11. Нет; 12. Да; 13. Да; 14. Да; 15. Нет; 16. Нет.

II.

III. 17. Да; 18. Да; 19. Нет; 20. Нет; 21. Да; 22. Да.



Pages:   || 2 |
 
Похожие работы:

«Федеральное агентство по образованию ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) Кафедра автоматизации обработки информации (АОИ) А.А. Сидоров ИССЛЕДОВАНИЯ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ И ПОЛИТИЧЕСКИХ ПРОЦЕССОВ ЧАСТЬ II Учебное пособие 2006 Корректор: Осипова Е.А. Сидоров А.А. Исследования социально-экономических и политических процессов: Учебное пособие. В 2-х частях. — Томск: Томский межвузовский центр дистанционного образования, 2006. — Ч.2. — 197 с. В учебном...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И ФИНАНСОВ КАФЕДРА ХОЗЯЙСТВЕННОГО ПРАВА РАБОЧАЯ ПРОГРАММА, МЕТОДИЧЕСКИЕ УКАЗАНИЯ И КОНТРОЛЬНЫЕ ЗАДАНИЯ ПО КУРСУ ХОЗЯЙСТВЕННОЕ ПРАВО ДЛЯ СТУДЕНТОВ ЗАОЧНОГО ОТДЕЛЕНИЯ ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ЭКОНОМИКИ И ФИНАНСОВ...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И ФИНАНСОВ КАФЕДРА СИСТЕМ ТЕХНОЛОГИЙ И ТОВАРОВЕДЕНИЯ КОНЦЕПЦИИ СОВРЕМЕННОГО ЕСТЕСТВОЗНАНИЯ РАБОЧАЯ ПРОГРАММА, ТЕМЫ КОНТРОЛЬНЫХ РАБОТ И МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ИХ ВЫПОЛНЕНИЮ (для студентов заочной формы обучения) ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ ИНФОРМАТИКА МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО В Ы П О Л Н Е Н И Ю КУРСОВОЙ РАБОТЫ Учетно-статистический факультет Кафедра автоматизированной обработки экономической информации Для самостоятельной работы студентов II курса всех специальностей (первое высшее образование) Москва ВУЗОВСКИЙ УЧЕБНИК Б Б К 65. Введение Методические указания...»

«ЦЕНТРОСОЮЗ РОССИЙСКОЙ ФЕДЕРАЦИИ СИБИРСКИЙ УНИВЕРСИТЕТ ПОТРЕБИТЕЛЬСКОЙ КООПЕРАЦИИ ЦЕНООБРАЗОВАНИЕ Программа, методические указания и задания контрольных работ для студентов заочной формы обучения Новосибирск 2000 Кафедра экономики потребительской кооперации Ценообразование: Программа, методические указания и задания контрольных работ / Сост. А.Р. Бернвальд, Л.А. Ефимовская. – Новосибирск: СибУПК, 2000. – 64 с. Рецензенты: профессор А.С. Новоселов, доцент М.В. Хайруллина Утверждены к изданию...»

«Министерство образования РФ Сибирская государственная автомобильно-дорожная академия (СибАДИ) В.В. Максимов, В.И. Подгурский МАСЛА. ТОПЛИВА (классификация, ассортимент) Учебное пособие Омск Издательство СибАДИ 2003 3 УДК 662.7+621.892 ББК 39.33-082 М 17 Рецензенты д-р техн. наук, проф. Омского государственного университета путей сообщения В.Р. Ведрученко, доцент СибАДИ В.Я. Авдюков Работа одобрена редакционно-издательским советом академии в качестве учебного пособия для студентов специальностей...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное образовательное учреждение высшего профессионального образования Воронежский государственный аграрный университет имени К.Д. Глинки Кафедра Налогов и права МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ по изучению дисциплины История отечественного государства и права для студентов, обучающихся по специальностям: 030501 Юриспруденция, 080107 Налоги и налогообложение Воронеж 2009 М.В. Пыльцина. Методические рекомендации по изучению...»

«АВТОНОМНАЯ НЕКОММЕРЧЕСКАЯ ОРГАНИЗАЦИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ЦЕНТРОСОЮЗА РОССИЙСКОЙ ФЕДЕРАЦИИ РОССИЙСКИЙ УНИВЕРСИТЕТ КООПЕРАЦИИ БАШКИРСКИЙ КООПЕРАТИВНЫЙ ИНСТИТУТ (ФИЛИАЛ) Кафедра общенаучных дисциплин, коммерции и менеджмента РЕКЛАМНАЯ ДЕЯТЕЛЬНОСТЬ МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ УФА - 2007 Брусенцова Л.С. Рекламная деятельность: Методические рекомендации для самостоятельной работы студентов. – Уфа: АНО ВПО ЦС РФ Российский университет кооперации...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И ФИНАНСОВ КАФЕДРА КОММЕРЦИИ И ЛОГИСТИКИ МЕТОДИЧЕСКИЕ УКАЗАНИЯ И ТЕСТЫ ПО ИЗУЧЕНИЮ УЧЕБНОЙ ДИСЦИПЛИНЫ РИСКИ В КОММЕРЧЕСКОЙ ДЕЯТЕЛЬНОСТИ (специальность 061400 – Коммерция, V курс, дневная и вечерняя формы обучения) ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ЭКОНОМИКИ И ФИНАНСОВ Рекомендовано...»

«Методическое обеспечение образовательной программы 031900.62 Международные отношения Минакова И. В. Макроэкономика [Текст] : учебно-методическое пособие / Ирина 1. Вячеславовна Минакова, Мария Федоровна Зозулич. - Курск : АПЛИТ, 2012. - 152 с. Программа практик [Текст] : учебно-методическое пособие / И. В. Минакова [и др.] ; 2. ЮЗГУ. - Курск : ЮЗГУ, 2012. - 43 с. : табл., прил. - Имеется электрон. аналог. Социология международных отношений [Электронный ресурс] : методические указания 3. для...»

«Допущено Cоветом Учебно методического объединения вузов России по образованию в области менеджмента в качестве учебного пособия по специальности Государственное и муниципальное управление Третье издание, переработанное МОСКВА 2010 УДК 351/354(075.8) ББК 60.561.32я73 П18 Рецензенты: Т.Т. Авдеева, заведующая кафедрой Организация и планирование местного развития Кубанского государственного университета, д р экон. наук, проф., В.Н. Попов, заведующий кафедрой Экономика и менеджмент Ставрополь ского...»

«Министерство образования Российской Федерации Югорский государственный университет Кафедра общей и теоретической экологии ПРОИЗВОДСТВЕННАЯ ПРАКТИКА Методические указания для студентов факультета природопользования специальность 013400 Природопользование Ханты-Мансийск 2003 Методические указания рекомендованы студентам 3 курса дневного отделения факультета природопользования, обучающимся по специальности 013400 Природопользование. Составители: доцент Н.В.Кокорина ст.преподаватель С.Б. Кузнецова...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И ФИНАНСОВ КАФЕДРА ЭКОНОМИЧЕСКОГО АНАЛИЗА ЭФФЕКТИВНОСТИ ХОЗЯЙСТВЕННОЙ ДЕЯТЕЛЬНОСТИ РАБОЧАЯ ПРОГРАММА, ЗАДАНИЯ И МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ ПО ДИСЦИПЛИНЕ КОМПЛЕКСНЫЙ ЭКОНОМИЧЕСКИЙ АНАЛИЗ ХОЗЯЙСТВЕННОЙ ДЕЯТЕЛЬНОСТИ для студентов заочного факультета специальности Бухгалтерский учет,...»

«ВЫСШЕЕ ФИНАНСОВОЕ ОБРАЗОВАНИЕ АНАЛИЗ ХОЗЯЙСТВЕННОЙ ДЕЯТЕЛЬНОСТИ учебное пособие Под редакцией В.И. Бариленко Омега-Л Москва, 2009 УДК ББК А 64 Публикуется с разрешения ООО Ай Пи Эр Медиа Авторы: Бариленко В.И. — доктор экономических наук, профессор, заведующий кафедрой Анализ хозяйственной деятельности и аудита Саратовского государственного социально-экономического университета. Плотникова Л.К. — к.э.н., доцент кафедры Анализ хозяйственной деятельности и аудита Саратовского государственного...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И ФИНАНСОВ КАФЕДРА КОММЕРЦИИ И ЛОГИСТИКИ МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ИЗУЧЕНИЮ УЧЕБНОЙ ДИСЦИПЛИНЫ УПРАВЛЕНИЕ ПРОЕКТАМИ В ЛОГИСТИКЕ для студентов 5 курса специальности 08.05.06 Логистика и управление цепями поставок ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ЭКОНОМИКИ И ФИНАНСОВ...»

«Федеральное агентство по образованию АМУРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Экономический факультет И.В. Новикова, Л.Я. Полянская ЭКОНОМИКА ГОРОДА Учебное пособие Рекомендовано ДВ РУМЦ в качестве учебного пособия для студентов вузов региона Благовещенск 2010 Печатается по решению Учебно-методического совета Амурского государственного университета Новикова И.В., Полянская Л.Я. Экономика города : учебное пособие. – Благовещенск: Изд-во Амур. гос. ун-та, 2010.- 134 с. Пособие предназначено студента...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И ФИНАНСОВ КАФЕДРА ЭКОНОМИКИ ПРЕДПРИЯТИЯ И ПРОИЗВОДСТВЕННОГО МЕНЕДЖМЕНТА С.Г. ОВЧИННИКОВА, О.В. ЯГИРСКАЯ ПРОМЫШЛЕННО-ФИНАНСОВАЯ ИНТЕГРАЦИЯ Ч.2 ЗОНЫ СВОБОДНОГО ПРЕДПРИНИМАТЕЛЬСТВА Под редакцией д-ра экон. наук, проф. А.Е. Карлика 4-е издание, переработанное и дополненное ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО...»

«Министерство образования Республики Беларусь УО ПОЛОЦКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МЕТОДИЧЕСКИЕ УКАЗАНИЯ к выполнению курсовой работы по дисциплине Анализ хозяйственной деятельности для студентов специальности 1-25 01 08 очной (заочной) формы обучения г. Новополоцк, ПГУ, 2010 УДК 657(075.8) ББК 65.052 (4 БЕИ) я 73 Одобрено и рекомендовано к изданию Методической комиссией финансово-экономического факультета в качестве методических указаний (протокол № от 20_г.) кафедра бухгалтерского учета и...»

«ПРИОРИТЕТНЫЙ НАЦИОНАЛЬНЫЙ ПРОЕКТ ОБРАЗОВАНИЕ РОССИЙСКИЙ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ В.И. ПРОНИН, А.С. ПЕТРОВ ОСНОВЫ ПРЕДПРИНИМАТЕЛЬСКОЙ ДЕЯТЕЛЬНОСТИ ПРИ НЕДРОПОЛЬЗОВАНИИ Учебное пособие Москва 2008 Инновационная образовательная программа Российского университета дружбы народов Создание комплекса инновационных образовательных программ и формирование инновационной образовательной среды, позволяющих эффективно реализовывать государственные интересы РФ через систему экспорта образовательных услуг...»

«Федеральное агентство по образованию Российской Федерации Государственное образовательное учреждение высшего профессионального образования АМУРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ (ГОУ ВПО АмГУ) УТВЕРЖДАЮ Зав.кафедрой КиТ Е.С. Новопашина _2007 г. УЧЕБНО- МЕТОДИЧЕСКИЙ КОМЛЕКС ДИСЦИПЛИНЫ Управление качеством для специальностей 08.05.07 Менеджмент организации 08.05.02 Экономика и управление на предприятии ( по отраслям) (дневная, заочная и заочно-сокращенная формы обучения) Составитель: к.т.н., доцент...»






 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

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