WWW.DISS.SELUK.RU

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

 

Саратовский государственный университет им. Н.Г. Чернышевского

С.И. Дудов, А.П. Хромов

ЛИНЕЙНОЕ

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

ТЕОРИЯ, ПРИМЕРЫ, ЗАДАЧИ

Учебное пособие

для студентов экономико-математических специальностей

ИЗДАТЕЛЬСТВО САРАТОВСКОГО УНИВЕРСИТЕТА

2

ОГЛАВЛЕНИЕ

Введение………………………………………………………………. 4 1. Примеры задач линейного программирования………………. 5 2. Постановка и формы записи задач ЛП………………………… 7 3. Геометрическая интерпретация задачи ЛП 9 4. Симплекс-метод…………………………………………………… 10 4.1. Понятие базисного плана и его базиса……………………... 4.2. Описание итерации симплекс-метода…………………….... 4.3. Доказательство теорем Данцига…………………….……… 4.4. Возможные ситуации перехода к очередному базисному плану……………………...……………………...…………… 4.5. Симплекс-таблица……………………...……………………. 4.6. Построение исходного базисного плана…………………… 5. Двойственная задача ЛП……………………...…………………. 5.1. Теоремы двойственности……………………...…………….. 5.2. Экономическая интерпретация двойственной задачи ЛП 6. Задачи и упражнения……………………...…………………….... 6.1.Приведение задачи ЛП к заданной форме………………….. 6.2. Геометрическое решение задач ЛП…………………….…... 6.3. Отыскание базиса заданного базисного плана…………….. 6.4. Решение задач ЛП симплекс-методом……………………... 6.5. Отыскание исходного базисного плана……………………. 6.6. Использование теории двойственности при решении задач ЛП……………………...…………………….………... Ответы и решения……………………...…………………….……… Список литературы……………………...…………………….…….

ВВЕДЕНИЕ

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

Такие задачи находят обширные приложения в различных сферах человеческой деятельности. Систематическое изучение задач такого типа началось в 1939 – 1940 гг. в работах Л.В. Канторовича.

В данном пособии приводятся основные факты теории решения задач линейного программирования. Основное внимание уделено изложению симплекс-метода как численного метода решения. Этот метод, являющийся доныне основным методом решения задач ЛП, был предложен американским математиком Дж. Данцигом в 1946 году. Отметим, что в 1979 – 1980 гг. появились новые идеи в построении численных методов решения задач ЛП, так называемые полиномиальные алгоритмы (см., например, [8, 9]).

Изложение материала в значительной мере использует книгу С.А. Ашманова и А.В. Тимохова [1]. Для углублённого изучения линейного программирования читатель может воспользоваться списком литературы, указанным в конце пособия.

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

1. ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Приведём три примера, ставшие классическими.

Пример 1. (Задача планирования производства). Пусть некоторое предприятие производит n типов товаров, затрачивая при этом m типов ресурсов. Известны следующие параметры:

aij — количество i-го ресурса, необходимое для производства единицы товара j-го вида, aij 0 ( i = 1, m, j = 1, n );

bi — запас i-го ресурса на предприятии, bi > 0 ;

c j — прибыль от реализации единицы товара j-го вида на рынке, c j 0.

Предполагается, что технология производства линейна, т.е. затраты ресурсов растут прямо пропорционально объему производства. Пусть x j показывает планируемый объем производства j-го товара. Тогда допустимым является только такой набор производимых товаров (план производства) x = ( x1,..., xn ), при котором суммарные затраты ресурса не превосходят его запаса:

n a bi, i = 1, m. (1.1) ij x j j = Кроме того, имеем естественное ограничение xj 0, j = 1, n. (1.2) Прибыль от продажи набора товаров выражается величиной n c x. (1.3) j j j = Задача планирования производства ставится следующим образом: среди всех векторов x, удовлетворяющих ограничениям (1.1)-(1.2), найти такой, при котором величина (1.3) принимает наибольшее значение.

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

aij — содержание i-го вещества в единице j-го продукта, aij 0 ( i = 1, m, j = 1, n );

bi — минимальное количество i-го вещества, которое должно потребляться индивидуумом в расчете, скажем, на месяц, bi > 0 ( i = 1, m );

c j — цена единицы j-го продукта, c j 0 ( j = 1, n ).

Задача о рационе формулируется следующим образом:

где x j — обозначает количество j-го продукта, потребляемого индивидуумом в течение месяца. Иными словами, среди всех рационов питания x = ( x1,..., xn ), покрывающих минимальные потребности индивидуума в полезных веществах, необходимо выбрать наиболее дешевый.



Пример 3. (Транспортная задача). Пусть некоторый однородный продукт (уголь, кирпич, картофель и т.п.) хранится на m складах и потребляется в n пунктах. Известны следующие параметры:

a i — запас продукта на i-м складе, ai > 0 ( i = 1, m );

b j — потребность в продукте в j-м пункте потребления, b j > 0 ( j = 1, n );

cij — стоимость перевозки единицы продукта с i-го склада в j-й пункт, При этом суммарные запасы равны суммарным потребностям:

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

где xij — показывает количество продукта, перевозимого с i-го склада в j-й пункт. Иными словами, требуется так организовать перевозки продукта со складов в пункты потребления, чтобы при полном удовлетворении потребностей минимизировать суммарные транспортные расходы. Заметим, что условие (1.4) является необходимым и достаточным для существования по крайней мере одной матрицы перевозок X = ( xij ), i = 1, m, j = 1, n, удовлетворяющей ограничениям задачи (1.5).

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

2. ПОСТАНОВКА И ФОРМЫ ЗАПИСИ ЗАДАЧ ЛП

Как известно, множество где a R n, a On, b R, называется гиперплоскостью в R n, а множества полупространствами, порожденными этой гиперплоскостью. Вектор a называется нормалью к гиперплоскости. Он ортогонален к и направлен в сторону полупространства +.

Определение 1. Множество R n называется полиэдром, если его можно представить как множество решений системы конечного числа линейных неравенств или ( что то же самое) как пересечение конечного числа полупространств, т.е. если где b = (b1,..., bm )T R m, x = ( x1,..., xn )T R n, А — матрица размерности mn, составленная из компонент векторов ai R n, i = 1, m.

Определение 2. Пусть c = (c1,..., cn ) R n — фиксированный вектор.

Задачей линейного программирования (ЛП) называется задача максимизации или минимизации линейной функции Z ( x) = c, x на полиэдре, т.е. задачу ЛП можно записать в виде Задачу ЛП вида (2.1) называют основной. Укажем другие распространенные формы записи задачи ЛП на максимум, различающиеся способами представления допустимого множества.

Стандартная задача ЛП:

где On = (0,...,0) R n.

Каноническая задача ЛП:

Формально говоря, каждая из задач (2.1)–(2.3) является частным случаем общей задачи (2.4):

при k = m и s = 0 получаем задачу (2.1), при k = m и s = n получаем задачу (2.2), при k = 0 и s = n получаем задачу (2.3).

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

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

3. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ ЛП

Рассмотрим задачу ЛП в основной форме (2.1). Ее допустимым множеством является полиэдр, а множества уровня (одного и того же значения) целевой функции представляют собой систему гиперплоскостей с общей нормалью с, направленной в сторону возрастания c, x. Поэтому, чтобы решить задачу геометрически, надо "переходить" с одного множества уровня на другое в направлении вектора с до тех пор, пока полиэдр не останется от множества уровня по одну сторону от него (в отделяемом полупространстве), но при этом имеет с ним хотя бы одну общую точку. Эта точка, или любая из них, дает решение задачи. Этот способ достаточно эффективен при n = 2 и небольшом m.

Геометрически наглядно, что решение может быть как единственным, так и неединственным (рис.1 пересечение гиперплоскости ( ) = {x R n / c, x = } с полиэдром не пусто (рис. 3), то значение целевой Рис. функции на допустимом множестве может быть сколь угодно большим и, следовательно, задача ЛП в этом случае не имеет решения. Ясно также, что если решение задачи существует, а у полиэдра есть вершины, то, по крайней мере, одна из них является решением задачи.

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

где x = ( x1,..., xn )T R n, c = (c1,..., cn )T R n, b = (b1,..., bm )T R m, матрица А размерности mn. Это не ограничивает общность метода, так как любая задача ЛП может быть представлена в форме (4.1) (см. п.2). Будем считать, что m < n и rank A = m, т.е. все строки матрицы А линейно независимы.

К этому можно прийти, исключив из системы Ax = b линейно зависимые уравнения. Кроме того, естественно считать b Om, так как иначе задача (4.1) становится тривиальной.

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

Определение 3. Допустимый план x = ( x1,..., xn )T называется базисным планом задачи (4.1), если у него найдется n m нулевых компонент и при этом остальным компонентам x j1,..., x jm будут соответствовать линейно независимые столбцы матрицы А: A j1,..., A j m. Набор этих столбцов называется базисом этого базисного плана. Если у базисного плана m положительных компонент, т.е. x j1 > 0,..., x j m > 0, то он называется невырожденным. В противном случае, т.е. если у него положительных компонент меньше m, его называют вырожденным.

Можно доказать, что, в геометрическом смысле, базисный план является вершиной полиэдра (4.2). Известно, что если полиэдр (4.2) не пуст, то у него имеется, по крайней мере, одна вершина. Кроме того, как следует из геометрической интерпретации задачи ЛП, если задача (4.1) разрешима, то одна из вершин полиэдра является оптимальным планом. Следовательно, если мы найдем все базисные планы и подсчитаем на них значение целевой функции, то мы найдем оптимальный план.

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

A j1,..., A jm. Поскольку rank A = m, то хотя бы один такой набор столбцов существует. Они образуют квадратную матрицу Б = ( A j1,..., A jm ) размерности mm, определитель которой det Б 0. Далее решаем систему линейных уравнений Бy = b, y = ( y1,..., y m ) R m. Эта система имеет единственное решение. Если все компоненты решения неотрицательны: yi 0, i = 1, m, то возьмем в качестве x R n вектор, у которого компоненты x ji = yi, i = 1, m, а остальные n m компонент равны нулю. В соответствии с построением и определением 3 такой вектор будет не только допустимым планом, т.е. удовлетворяющим Ax = b, x On, но и базисным планом. Из этой процедуры, в частности, следует, что невырожденному базисному плану может соответствовать только один базис, в то время как вырожденному базисному плану может соответствовать несколько базисов.

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

Предложен этот метод был американским математиком Дж. Данцигом в 1946 году. Из других специалистов, внесших фундаментальный вклад в линейное программирование, отметим советского математика и экономиста Л.В.Канторовича (1912-1986 г.г.), лауреата Нобелевской премии года. Именно он положил начало систематическому изучению задач ЛП в 1939-1940 гг.

Симплекс-метод представляет собой вычислительную процедуру, которая по заданному исходному базисному плану x 0 генерирует последовательность базисных планов x1, x 2,..., x p вместе с их базисами. На очередной р-й итерации в зависимости от текущего значения параметров делается один из выводов:

1) либо x p — решение задачи (4.1), 2) либо задача (4.1) не имеет решения (неограничена), 3) либо строится следующий базисный план x p +1. Если при этом базисный план x p невырожден, то Если же x p — вырожденный базисный план, то либо выполняется (4.3), либо x p+1 = x p, а итогом итерации является замена одного базиса плана x p на другой. Перебор базисов может продолжаться несколько итераций, но обязательно появляется базис, при котором осуществляется переход на новый базисный план с бльшим значением целевой функции.

Эта процедура за конечное число шагов итераций обязательно приводит либо к выводу 1) либо к выводу 2), поскольку число базисных планов конечно.

Пусть уже получен базисный план x p и его базис — столбцы A j1,..., A jm. Обозначим x = x p, J = { j1, j2,..., jm }, то есть { A j / j J } — базис базисного плана х.

Поскольку столбцы { A j / j J } линейно независимы, то они образуют базис в R m. Поэтому все столбцы матрицы А можно однозначным образом представить, как линейные комбинации столбцов этого базиса:

где числа jk — соответствующие коэффициенты разложения столбцов по базису. Вычислим величины Параметры jk принято называть коэффициентами замещения, а параметры k — оценками замещения. Для любого kJ, очевидно, имеем Выводы 1), 2), 3), описанные в предыдущем пункте 4.1, делаются в зависимости от знаков коэффициентов и оценок замещения. Обязательно выполняется хотя бы одно из трех условий:

I. Для любого номера k [1 : n] выполняется k 0.

II. Существует номер sJ такой, что s < 0 и js 0 для всех jJ.

III. Существует номер sJ такой, что s < 0 и js > 0 при некотором jJ.

Каждому из этих условий соответствует одно из следующих трех правил симплекс-метода.

Теорема 1 (1-я теорема Данцига, правило оптимальности).

Если выполняется условие I, то базисный план х является оптимальным, т.е. решением задачи (4.1).

Теорема 2 (2-я теорема Данцига, правило отсутствия решения).

Если выполняется условие II, то задача (4.1) не имеет решения.

Ясно, что если выполняется условие I или условие II, то решение задачи на этом заканчивается. Пусть теперь выполняется условие III. Для указанного там номера s положим Пусть минимум в (4.7) достигается на номере r, т.е.

Введем множество индексов и точку x R n с компонентами Теорема 3 (3-я теорема Данцига, правило перехода к новому базисному плану). Если выполняется условие III, то x является базисным планом задачи (4.1), а { A j / j J } его базисом, причем Этот базисный план x и его базис берутся для расчетов на следующей ( p + 1) -й итерации: x p+1 = x. При этом говорят, что столбец Ar выводится из базиса, а столбец As вводится в базис. Элемент rs называется ведущим.

Для упрощения выкладок, но без потери общности рассуждений в доказательствах, будем считать, что для базисного плана x = x p задачи (4.1) множество т.е. столбцы A1, A2,..., Am образуют базис базисного плана х.

Обозначим через Б = ( Ai ) i =1,m – матрицу размерности mm образованную компонентами столбцов базиса;

x 0 = ( x1,..., xm )T R m — вектор, составленный их первых m компонент вектора х. Так что c 0 = (c1,..., cm )T R m — вектор, составленный из первых m компонент вектора с;

= Б 1 A — матрица размерности mn и следовательно т.е. столбец k матрицы составлен из коэффициентов замещения (см.

(4.4)):

вектор оценок замещения = (1,..., n ) (см.(4.5)) можно в нашей ситуации записать в виде Легко видеть, что вектор x удовлетворяет равенству Докажем вспомогательный факт.

Лемма 1. Если x допустимый план задачи (4.1), то Доказательство. То, что x является допустимым планом задачи (4.1), в частности, означает Используя (4.13), (4.16) и (4.18) получаем 1-я теорема Данцига. Если базисный план х таков, что On, то х является оптимальным планом.

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

Сопоставим нашему базисному плану х, индексу sJ (т.е., учитывая (4.12), s [m + 1: n] ), и числу вектор x следующей структуры Докажем, что справедлива Лемма 2. Если s [m + 1: n], то для вектора x выполняется соотношения (4.14)-(4.16), получаем Учитывая (4.12) и принятые обозначения, теорема 2 принимает вид:

2-я теорема Данцига. Если при некотором s [m + 1: n] компонента s < 0, а все компоненты столбца s неположительны, то задача (4.1) не имеет решения.

Доказательство. Из условий теоремы и леммы 2 следует, что для любого > 0 выполняется Ax = b и x On, т.е. x — допустимый план.

С другой стороны, в силу той же леммы 2, т.е. задача (4.1) неограниченна сверху на допустимом множестве.

Рассмотрим теперь случай выполнения условий теоремы 3, т.е. когда существует индекс s [m + 1: n] такой, что s < 0 и при этом среди компонент столбца s есть положительные. Пусть в соответствии с (4.7)-(4.8) При таком компоненты вектора x из (4.19) выражаются формулой (4.10).

3-я теорема Данцига. Пусть существует индекс s [m + 1: n] такой, что s < 0 и при этом среди компонент столбца s есть положительные. Тогда план x, определяемый (4.19)-(4.20) является базисным, а { A j / j J }, где J определяется (4.9) и (4.20), его базисом, причем Доказательство. Из выбора числа в соответствии с (4.20) и (4.19) следует x On. Кроме того, в силу леммы 2, имеет место равенство Ax = b. Таким образом x, является допустимым планом.

Покажем, что x является базисным планом с базисом { A j / j J }, где J = ({1 : m} \ {r})U{s}. Действительно, во-первых, поскольку компонента вектора x с номером r, как следует из (4.19)-(4.20), равна нулю, то у x не более m ненулевых компонент. В соответствии с определением 3 нам осталось показать, что система столбцов { A j / j J } является линейно независимой. Допустим противное, т.е. существуют числа { i }, i = 1, m, не все равные нулю и такие, что Очевидно, что так как иначе получаем противоречие с линейной независимостью столбцов базиса { A j / j J }, где по предположению (см. (4.12)) J = [1 : m]. В силу (4.14) имеем разложение столбца As по базису { A j / j J } :

Подставив его в (4.22) получим нулевую линейную комбинацию столбцов базиса { A j / j J }, причем коэффициент при Ar будет равен r rs.

В силу (4.20) и (4.23), он не равен нулю и, таким образом, получаем противоречие с линейной независимостью столбцов базиса { A j / j J }. Тем самым мы показали, что набор столбцов { A j / j J } является базисом базисного плана x. Для завершения доказательства теоремы осталось заметить, что формула (4.21) следует непосредственно из леммы 2.

4.4. Возможные ситуации перехода к очередному базисному плану Если число из (4.7) является положительным, то из (4.11) и условия s < 0 следует, что c, x p+1 > c, x p. Неравенство > 0 заведомо выполнено, если базисный план x p невырожден. Если же он вырожден, то не исключено, что найдется rJ, для которого rs > 0 и x r = 0. Тогда (см.

(4.7)) окажется, что = 0 и x p+1 = x p, т.е. итогом вычислений по формулам (4.7)-(4.11) будет лишь замена базиса { A j / j J } на базис { A j / j J }.

Процедура вычислений (4.7)-(4.10) содержит некоторую неопределенность. Там не уточняется, как выбирать номер s из условия III и номер r их условий (4.8)-(4.9), если таких s и r несколько. Существуют примеры, показывающие, что, при определенном выборе этих номеров, описанная процедура может привести к циклическому перебору базисов одного и того же базисного плана. В таком случае говорят, что произошло зацикливание симплекс-метода. Существуют особые правила выбора r и s, устраняющие явление зацикливания. Простейшее правило такого сорта заключается в следующем.

Теорема 4 (правило Блэнда устранения зацикливания). Пусть при выполнении условия III выбирается «первое подходящее» s, а затем «первое подходящее» r, т.е.

где определено в (4.7)-(4.8). Тогда зацикливание симплекс-метода невозможно.

На очередной ( p + 1) -й итерации необходимо опять считать коэффициенты jk и оценки замещения для нового базиса. Это, вообще говоk ря, требует решения соответствующих систем линейных уравнений и является достаточно трудоемкой операцией. Но оказывается, что jk и k можно легко рассчитать по известным нам jk и k.

Теорема 5 (связь между старыми и новыми параметрами замещения). При любом k = 1, 2,..., n выполняются соотношения При организации вычислений по симплекс-методу основной конструкцией является так называемая симплекс-таблица Т, соответствующая данному базисному плану х и его базису { A j / j J }. Эта таблица представляет собой матрицу размера (m+1)(n+1).

Над столбцами таблицы записываются буквенные обозначения A1,..., An, x, столбцов матрицы А и очередного базисного плана задачи (4.1), а с левой стороны таблицы – обозначения { A j / j J } столбцов, образующих базис, и обозначение вектора. На указанные места таблицы заносятся численные значения параметров jk, x j, k, c, x.

После заполнения таблицы Т проводится ее анализ на основе правил симплекс-метода. Если выполняется условие I или II, то расчеты заканчиваются. Если же выполняется условие III, то осуществляется переход к симплекс-таблице Т, соответствующей новому базисному плану x и его Для этого выбираются номера s и r, удовлетворяющие условиям III и (4.7)А в случае неопределенности выбора используется еще и правило Блэнда. Ведущий элемент rs в таблице Т помечается для наглядного указания на то, что столбец Ar должен быть выведен из базиса, а столбец As введен в него. В таблице Т вместо Ar ставится As, а остальные буквенные обозначения остаются неизменными. Из формул (4.7)-(4.11), (4.24)-(4.25) ясно, что вычисление параметров таблицы Т сводится к следующим элементарным операциям над строками таблицы Т:

1) для получения строки A j таблицы Т при j J \ {r} из строки A j таблицы Т вычитается ее строка Ar, умноженная на коэффициент 2) для получения строки As таблицы Т строка Ar таблицы Т делится 3) для получения строки таблицы Т из строки таблицы Т вычитается ее строка Ar, умноженная на коэффициент s / rs.

При этом естественно (в соответствии с (4.4)) элемент столбца As таблицы Т, стоящий на пересечении со строкой As, оказывается равным единице, а все остальные его элементы равны нулю. Затем проводится анализ таблицы Т. Если выполняется условие III, то осуществляется переход к следующей таблице Т и т.д.

4.6. Построение исходного базисного плана При описании симплекс-метода мы предполагали, что уже известен некоторый начальный базисный план задачи. Здесь рассмотрен один из общих способов его построения — метод искусственного базиса.

Пусть дана задача (4.1). Без потери общности будем считать, что b Om. Рассмотрим задачу где u = (u1,..., um ) R m. Эта задача имеет решение, так как целевая функция является линейной и ограниченной на допустимом множестве. Причем вектор z 0 = (on, b) R m + n является базисным планом задачи (4.26) с базисом {e1,..., e m }, где e i — i-й единичный орт в R m. Применим к задаче (4.26) симплекс-метод, используя в качестве начального базисный план z 0.

В результате найдем оптимальный базисный план z* = ( x*, u* ) R m + n задачи (4.26). Теперь вопрос о начальном базисном плане для исходной задачи (4.1) решается в соответствии со следующим утверждением.

Теорема 6. Если u * Om, то допустимое множество в задаче (4.1) пусто. Если же u * = Om, то х* является базисным планом задачи (4.1).

Доказательство. Предположим, что, т.е. существует хотя бы один допустимый план х. Тогда легко проверить, что план ( x *, Om ) R m + n является не только допустимым, но и оптимальным для задачи (4.26), причем оптимальное значение целевой функции равно нулю.

Поэтому, если только предположить, что u * Om, что говорит о наличии хотя бы одной положительной компоненты у вектора u*, то получается, что значение целевой функции задачи (4.26) на плане ( x *, u * ) является положительным. Это противоречит его оптимальности. Тем самым первое утверждение теоремы доказано.

Легко видеть, что Ax* = b, x * On, т.е. план х* является допустимым для задачи (4.1). Из базисности плана ( x *, u * ) для задачи (4.26) и условия (4.27) следует, что у вектора х* не более m положительных компонент, и им соответствуют линейно независимые столбцы матрицы А. Если этих положительных компонент меньше чем m, то их можно дополнить до m штук за счет нулевых так, чтобы в целом выделенным компонентам соответствовали линейно независимые столбцы матрицы А. Это всегда можно сделать, так как rank A = m. Это говорит о том, что х* — базисный план задачи (4.1).

5. ДВОЙСТВЕННАЯ ЗАДАЧА ЛП

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

Рассмотрим задачу ЛП в канонической форме где c, x R n, b R m, А — матрица размерности mn, m < n, rankA = m.

Двойственной к ней назовем следующую задачу ЛП где y R m, AT — транспонированная матрица А.

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

Лемма 3. Если х и у допустимые планы задач (5.1) и (5.2) соответственно, то При этом, если для некоторых допустимых планов х и у в (5.3) выполняется равенство, то х* и у* являются оптимальными планами соответствующих задач.

Доказательство. Непосредственно используя допустимость планов, получаем (5.3):

Второе утверждение леммы легко следует из (5.3).

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

Теорема 7 (1-я теорема двойственности). Пусть. Если одна из задач двойственной пары (5.1)-(5.2) имеет решение, то и другая задача разрешима. При этом для любых оптимальных планов х* и у* задач (5.1) и (5.2) имеет место равенство а) Пусть задача (5.1) является разрешимой. Из теорем 3 и 4 следует, что найдется оптимальный базисный план х*, для которого все компоненты вектора, определяемые формулой (4.5), являются неотрицательными Как и в п. 4.3, без потери общности, примем предположение о том, что { A j / j J }, где J = [1 : m], является базисом для х*, и те же обозначения.

Тогда (5.5) эквивалентно неравенству Обозначим через y = ( Б ) c. Тогда, используя (5.6), имеем т.е. вектор у* является допустимым планом задачи (5.2). Кроме того, получаем Следовательно, в силу леммы 3, вектор у* является оптимальным планом задачи (5.2) и имеет место равенство (5.4).

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

Теорема 8 (2-я теорема двойственности). Для того, чтобы допустимые планы х* и у* пары двойственных задач (5.1) и (5.2) были оптимальными необходимо и достаточно, чтобы они удовлетворяли системе уравнений Доказательство.

Необходимость. Если x* и y * — оптимальные планы, то, по теореме 7, выполняется равенство (5.4). Учитывая, что Ax* = b, легко увидеть, что оно эквивалентно (5.8). Выполнение равенства (5.7) следует из допустимости плана x*.

Достаточность. Из (5.8) следует (5.4), что, по лемме 3, означает оптимальность допустимых планов x* и y *.

Замечание 1. Особенно эффективность теории двойственности проявляется в тех случаях, когда двойственная задача решается проще, чем прямая. Если ее решение y * найдено, то, учитывая, что AT y * c и x* 0, из (5.8) получаем систему уравнений для решения прямой задачи (5.1):

Замечание 2. Укажем соответствующие пары двойственных задач еще в двух наиболее важных частных случаях а) Если прямая задача записана в основной форме то двойственная ей задача имеет каноническую форму б) Если прямая задача записана в стандартной форме то двойственная ей задача также имеет стандартную форму Отметим, что и для этих пар двойственных задач, приведённые выше утверждения (лемма 3 и теоремы 7-8) также справедливы.

5.2. Экономическая интерпретация двойственной задачи ЛП Предположим, что мы рассматриваем задачу планирования производства из §1. То есть задача (5.9) соответствует задаче определения оптимального плана производства товаров, обеспечивающего максимальную прибыль. Пусть предприятие решило прекратить производство товаров и продать ресурсы, идущие на их изготовление. Обозначим через yi цены на единицу ресурсов i-го вида, i = 1, m. Эти цены должны удовлетворять двум условиям: во-первых, они не должны быть слишком высокими, иначе ресурсы трудно продать; а во-вторых, цены должны быть такими, чтобы прибыль от их реализации была бы не меньше прибыли от реализации готовой продукции. Первое условие выражается в минимизации линейной формы bT y, где y = ( y1,..., y m )T, а второе условие неравенством AT y c. Учитывая, что все компоненты вектора у неотрицательны, получаем задачу (5.10).

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

6. ЗАДАЧИ И УПРАЖНЕНИЯ

1. Привести к канонической форме задачу Решение. Начнем с преобразования смешанной системы ограничений в систему уравнений. Для того, чтобы первое ограничение записать в форме равенства, введем неотрицательную переменную x3. В результате система ограничений запишется в виде Перейдем к преобразованию условий неотрицательности. Неравенствами (6.2) не охвачена только переменная x2. Можно воспользоваться двумя приемами.

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

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

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

3. Преобразовать задачу ЛП к канонической форме так, чтобы число переменных в новой задаче не превышало трех:

Привести задачи 4–7 к канонической форме двумя приемами (см. задачу 1) и сравнить результаты.

8. Привести следующую задачу ЛП к стандартной форме:

9. Привести следующую задачу ЛП к канонической форме:

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

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

12. Найти все значения параметра а, при которых указанные точки x являются решениями соответствующих задач ЛП:

13. Используя геометрические построения, найти решение следующей задачи ЛП:

14. Используя геометрические построения, найти решение следующей задачи ЛП:

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

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

17. Привести примеры таких значений параметров p и q, при которых задача а) имеет пустое допустимое множество;

б) имеет оптимальное значение целевой функции равное + ;

в) имеет единственное решение; г) имеет бесконечно много решений:

18. Найти все значения параметра k, при которых точка x * = (b, a ) является решением задачи 6.3. Отыскание базиса заданного базисного плана 19. Пусть полиэдр в R 6 задается системой Найти все базисы его вершины x 0 = (0, 1, 0, 1, 0, 0).

Решение. Из вида базисного плана и определения 3 следует, что индексы 2 и 4 входят в соответствующее множество индексов столбцов матрицы условий, которые образуют базис. Осталось выяснить, какие из систем столбцов { A j, A2, A4 }, где индекс j {1, 3, 5, 6}, линейно независимы.

С этой целью вычислим четыре определителя Отсюда заключаем, что базисами плана x 0 служат системы { A3, A2, A4 } и 20. Пусть полиэдр в R 5 задается системой Найти все базисы его вершины x 0 = (0, 0, 1, 0, 0) в зависимости от параметра k.

21. Пусть полиэдр в R 6 задается системой Найти все базисы его вершины x 0 = (0, 0, 1, 1, 0, 0).

22. Сформулируем три утверждения относительно задачи ЛП и ее базисного плана x 0 :

А. x 0 — решение задачи.

Б. Задача не имеет решения.

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

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

Решение. Единственным базисом базисного плана x 0 является система столбцов { A1, A4 }. Выразим через этот базис столбцы A2, A3, A5. Составляем систему т.е.

Находим 12 = 1, 42 = 1.

Аналогично из систем находим 13 = 2, 43 = 3, 15 = 4, 45 = 6. Вычислим оценки замещения Поскольку 5 < 0, 15 < 0, 45 < 0, то, согласно теореме 2, имеет место утверждение Б.

23. Используя правила симплекс-метода, выяснить, какое из утверждений А, Б или В (см. задачу 22) имеет место в следующих задачах:

24. Используя правила симплекс-метода, выяснить, какое из утверждений А, Б или В (см. задачу 22) имеет место в следующих случаях:

25. Используя теорию симплекс-метода, найти все значения параметра k, при которых точка x* является решением соответствующей задачи:

26. Используя симплекс-метод, найти все значения параметра k, при которых точка x* = (1, 2, 0, 1, 0) T является решением задачи:

27. Решить симплекс-методом задачу ЛП, используя начальный базисный план x 0 = (0, 0, 1, 5)T :

Легко убедиться, что x является базисным планом, а столбцы, A3 = (1, 0)T, A4 = (0, 1)T — его базисом. Эти столбцы образуют естественный базис в R 2 и поэтому коэффициенты разложения по нему столбцов A и A2 совпадают с их компонентами Поскольку для x 0 множество индексов J = {3; 4}, то, в соответствии с формулой (4.5):

Для построенной таблицы выполнено условие III п.4.2, причем в качестве столбца, вводимого в базис, можно взять A1 или A2. Следуя правиx лу Блэнда, выберем A1, т.е. полагаем s = 1. Поскольку 3 = 1, 4 =, то из базиса надо вывести A3, т.е. положить r = 3. Таким образом, ведущим является элемент 31, а новый набор индексов J = {1; 4}.

Теперь осуществим переход к следующей таблице T1 в соответствии с формулами (4.24) - (4.25), т.е. операциями 1) - 3) п.4.5.

1) Для получения строки A4 таблицы T1, поскольку j = 4 J \ {r}, из строки A4 таблицы T0 вычитаем ее строку A3, умноженную на коэффициjs 2) Для получения строки A1 таблицы T1 строку A3 таблицы T0 делим на rs = 1 ;

3) Для получения строки таблицы T1 из строки таблицы T0 вычитаем ее строку A3, умноженную на s = 1 = Для таблицы T1 выполнено условие III, причем ведущим является элемент 42, т.е. r = 4, s = 2. Переходим к следующей симплекс-таблице T2. При этом, в соответствии с операциями 1) - 3) из п.4.5:

1) Строка A1 новой таблицы получается вычитанием из строки A 2) Строка A2 новой таблицы получается из строки A4 таблицы T1 , деленной на rs = 3 ;

3) Строка новой таблицы получается из строки таблицы T1 вычитанием из нее строки A4, умноженной на s = 2 = 1.

Для таблицы T2 ведущим является элемент 13 = 1/ 3. Строим очередную симплекс-таблицу.

Здесь выполняется условие I. Следовательно, x* = (0, 5, 6, 0)T — решение задачи, а c, x * = 17 максимальное значение целевой функции.

28. Решить симплекс-методом следующие задачи ЛП, начав с указанных базисных планов:

29. Решить симплекс-методом следующие задачи ЛП, начав с указанных базисных планов:

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

Решение. В соответствии с методом искусственного базиса, требуется решить симплекс-методом задачу начав с базисного плана x = (0, 0, 0, 0, 1, 1) T. Процесс вычисления показан в следующей таблице Таким образом, x * = (1, 0, 0, 0, 0, 0)T — оптимальный базисный план вспомогательной задачи. А поскольку значение целевой функции в ней равно нулю, то, в соответствии с теоремой 6, x 0 = (1, 0, 0, 0)T — базисный план исходной задачи. В базис этого плана, кроме столбца A1 войдет один из столбцов A j, j = 2, 3;

31. Найти методом искусственного базиса исходный базисный план и его базис для задач ЛП, допустимое множество которых задается системой:

6.6. Использование теории двойственности при решении задач ЛП 32. Построить задачи, двойственные к следующим задачам ЛП:

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

Решение. Перейдем к двойственной задаче:

С помощью геометрических построений находим ее решение y * = (9/5,13/5). Учитывая неотрицательность компонент допустимых планов данной пары двойственных задач, из теоремы 8 имеем Поскольку второе и четвертое неравенства из ограничений для двойственной задачи для y * выполняются строго, то из первого равенства следует x2 = x4 = 0. А так как y1 > 0 и y 2 > 0, то из второго следует, что компоненты x1 и x3 удовлетворяют системе Отсюда x1 = 4 / 5, x3 = 13 / 5. Следовательно, x * = (4 / 5, 0, 13/5, 0)T.

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

ОТВЕТЫ И РЕШЕНИЯ

2. Основная форма:

стандартная форма:

каноническая форма:

В (I), (II) сделана замена переменной x3 = u3 v3, u3 0, v3 0, а в (II), кроме того, введены переменные w2 0, w3 0 для приведения неравенств к равенствам.

3. Вводя дополнительную переменную x5 0, запишем первое ограничение в виде равенства Выразим из этого и второго ограничения переменные x1 и x2 не связанные условием неотрицательности Подставляя данные выражения в целевую функцию и в третье ограничение, приходим к задаче 10. а) x* = (2, 3); б) x* = (3, 2); в) x* = (1, 2); г) x* = (1, –2).

11. а) Из третьего ограничения имеем Подставляя это выражение в целевую функцию и первые два ограничения, а также учитывая, что x3 0, приходим к задаче Геометрическим путем получаем ее решение: x1 = 4, x2 = 0. Подставляя эти числа в (I), получаем x3 = 6. Следовательно, x * = (4, 0, 6)T — решение исходной задачи.

б) Выразим из системы уравнений переменные x1, x2, x3 :

Подставляя их в целевую функцию и учитывая условия неотрицательности, приходим к задаче Ее решение x4 = 0, x5 = 5. Подставляя в (II), получаем x1 = 3, x2 = 0, x3 = 6.

Следовательно, x* = (3, 0, 6, 0, 5) — решение исходной задачи.

{ A1, A 4, A3 }, { A2, A 4, A3 } ; если k = 15, то базисами будут только первая и третья из указанных систем. При k = 4 базисы отсутствуют (в этом случае ранг матрицы равен 2).

23. а) Как и при решении задачи 22, проводя аналогичные вычисления, получаем 4 = 6 < 0, 34 = 3 > 0. Тогда по теореме 3 имеет место утверждение B.

справедливо утверждение А.

в) Утверждения Б и В одновременно.

25. Нетрудно видеть, что x* — невырожденная вершина. Решая системы находим Вычислим оценки замещения:

Из теорем 1-3 следует, что невырожденная вершина x* является решением задачи при данном k в том и только в том случае, если 1 0, 5 0, 6 0. Решая эту систему неравенств, получаем ответ:

в) Таких k не существует.

б) Начальная и последующая симплекс-таблицы связаны воедино в следующею таблицу Отсюда заключаем, что решением служит точка x* = (3, 0, 0, 0, 0, 2)T.

в) x * = (0, 1, 0, 1, 1)T. Перейти к задаче максимизации.

г) Выберем в качестве базиса вершины x 0 систему { A1, A 2, A3 }. Процесс вычислений показан в таблице Таким образом, решением является x * = (0, 0, 1, 0, 1)T.

д) Процедура симплекс-метода (с правилом Блэнда) приводит к перебору базисов вершины x 0 :

Для третьего базиса оказывается выполненным условие теоремы 3. Следовательно x 0 — решение задачи.

30. б) Вычисления, аналогичные варианту а), приведены в таблице x 0 = (2, 0, 1, 0)T — базисный план исходной задачи.

33. б) x* = (0, 0, 11, 0, 27)T ; в) x* = (0, 3 / 19, 1/19, 0, 0)T.

СПИСОК ЛИТЕРАТУРЫ

1. Ашманов С.А., Тихонов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991.

2. Ашманов С.А. Линейное программирование. М.: Наука, 1981.

3. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1988.

4. Гольштейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. М.:

Сов. радио, 1966.

5. Зуховицкий С.И., Авдеева Л.И.Линейное и выпуклое программирование. М.: Наука, 1967.

6. Карманов В.Г. Математическое программирование. М.: Наука, 1986.

7. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. М.: Наука, 1969.

8. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании // Докл.АН СССР. 1979. Т.244, № 5.

9. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании // ЖВМ и МФ. 1980. Т.20, №1.

МЕТОДЫ ОПТИМИЗАЦИИ

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

для студентов экономико-математических специальностей Изд. лиц. ЛР № 020305 от 19.02.1997. Подписано в печать 16.01.2002.

Формат 60x84 1/16.Бумага офсетная. Гарнитура Таймс. Печать офсетная.

Усл. печ. л. 2,79(3). Уч.-изд. л. 2,3. Тираж 200 экз. Заказ № Издательство Саратовского университета.

Отпечатано с готового оригинал-макета 410600, Саратов, ул. Московская, д.152.





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

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

«Уважаемые выпускники! В перечисленных ниже изданиях содержатся методические рекомендации, которые помогут должным образом подготовить, оформить и успешно защитить выпускную квалификационную работу. Рыжков, И. Б. Основы научных исследований и изобретательства [Электронный ресурс] : [учебное пособие для студентов вузов, обучающихся по направлению подготовки (специальностям) 280400 — Природообустройство, 280300 — Водные ресурсы и водопользование] / И. Б. Рыжков.— Санкт-Петербург [и др.] : Лань,...»

«Введение 1. Организационно-правовое обеспечение образовательной деятельности 2. Структура вуза и система управления 2.1 Структура и система управления вуза 2.2 Информационное обеспечение системы управления 3. Структура подготовки специалистов 3.1 Динамика приема студентов 3.2 Контингент обучающихся 3.3.1 Профориентационная работа довузовского образования 3.3.2 Довузовская подготовка 3.3.3 Высшее профессиональное образование 3.3.4 Дополнительное профессиональное образование 4. Содержание...»

«Dr. univ. PhD Kovcs Ilona Julianna* РЕКОМЕНДАЦИЯ НЕКОТОРЫХ НОВЕЙШИХ РУССКОЯЗЫЧНЫХ УЧЕБНЫХ ПОСОБИЙ Чем привлекает к себе внимание всех исследователей языковых явлений русская и русскоязычная литература? Она богатая, детализированная и охватывает все области дидактики, методики, лингвистики по общему и деловому языку. В названной сфере науки самым авторитетным является Анатолий Николаевич Щукин. Он один из известнейших методистов в области преподавания языков, научные труды которого невероятно...»

«1 СОДЕРЖАНИЕ 1 ОБЩИЕ ПОЛОЖЕНИЯ..4 1.1 Нормативные документы для разработки ООП ВПО.4 1.2 Общая характеристика ООП ВПО.4 1.2.1 Цель (миссия) ООП ВПО..4 1.2.2 Срок освоения ООП ВПО.5 1.2.3 Трудоемкость ООП ВПО..5 1.3Требования к уровню подготовки, необходимому для освоения ООП ВПО..5 2 ХАРАКТЕРИСТИКА ПРОФЕССИОНАЛЬНОЙ ДЕЯТЕЛЬНОСТИ ВЫПУСКНИКА.. 6 2.1 Область профессиональной деятельности выпускника.6 2.2 Объекты профессиональной деятельности выпускника.6 2.3 Виды профессиональной деятельности...»

«ИЗБИРАТЕЛЬНАЯ КОМИССИЯ ОРЕНБУРГСКОЙ ОБЛАСТИ Участие средств массовой информации при проведении выборов Губернатора Оренбургской области в единый день голосования 14 сентября 2014 года МЕТОДИЧЕСКОЕ ПОСОБИЕ г. Оренбург 2014 год Избирательная комиссия Оренбургской области ул. 9 Января, д.64, г. Оренбург, 460046 тел. (3532) 77-70-74, факс (3532) 77-48-68 E-mail: orbelect@gmail.com Используемые сокращения: Закон Оренбургской области от 25 июня – Закон области 2012 года № 883/250-V-ЗО О выборах...»

«А.Е. Сушбов Б.Т. Жарылгасова БУХГАЛТЕРСКИЙ УЧЕТ И АУДИТ Допущено УМО по образованию в области коммерции в качестве учебного пособия для студентов высших учебных заведений МОСКВА 2005 УДК 657.1 ББК 65.431я75 С89 Рецензенты: И.М. Дмитриева, доктор экономических наук, профессор, зав. кафедрой бухгал¬ терского учета Российского государственного торгово-экономического универ¬ ситета, Е.И. Семенова, доктор экон омических наук, профессор, декан экономического факультета Российского государственного...»

«Издания на электронных носителях, поступившие в справочноинформационный фонд в 3 квартале 2013 года БОРЬБА С ПРЕСТУПНОСТЬЮ Авдеев В.Н. 1 Реализация органами дознания процессуальных мер, направленных на устранение причин и условий, способствующих совершению преступлений [Электронный ресурс]: Методические рекомендации / d\Винчестер\сиф ЦИиНМОКП\Авдеев. - Калининград: Калининградский филиал СПбу МВД России, 2012. Алтуфьев Д.Ю. 2. Ксенофобия в современном российском обществе [Электронный ресурс]:...»

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

«В. А. Максимов, Ф. Р. Карибуллина РОТОРНЫЕ КОМПРЕССОРЫ Учебное пособие 2005 Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Казанский государственный технологический университет В. А. Максимов, Ф. Р. Карибуллина РОТОРНЫЕ КОМПРЕССОРЫ Учебное пособие Казань 2005 ББК 31.77 УДК 621.514.6 Роторные компрессоры: Учебное пособие/ В.А. Максимов, Ф.Р. Карибуллина; Казан.гос.технол.ун-т. Казань, 2005. 76с. ISBN 0-0000-0. Учебное пособие...»

«Министерство образования и науки Российской Федерации Негосударственное образовательное учреждение высшего профессионального образования Томский экономико-юридический институт УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС по дисциплине История экономики для направления подготовки 030500.62 Юриспруденция Томск - 2010 СОДЕРЖАНИЕ РАЗДЕЛ 1. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ 1.1 Выписка из государственного образовательного стандарта 1.2 Цели и задачи учебной дисциплины 1.3 Требования к уровню освоения дисциплины 1.4 Виды...»

«УТВЕРЖДАЮ Председатель Контрольно-счтной комиссии Мошенского муниципального района Т.В.Трофимова __ 2013 г. ОТЧЕТ о результатах контрольного мероприятия по вопросу целевого и эффективного использования средств бюджета, выделенных на благоустройство территории Ореховского сельского поселения Основание для проведения проверки: план работы Контрольно-счтной комиссии Мошенского муниципального района. Цель проверки: целевое и эффективное использование средств бюджета, выделенных на благоустройство...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Московский государственный университет экономики статистики и информатики Московский международный институт эконометрики, информатики, финансов и права А.А. Андреев Педагогика высшей школы (Новый курс) Москва, 2002 УДК 378 ББК 74.00 А 49 Андреев А.А. Педагогика высшей школы. Новый курс – М.: Московский международный институт эконометрики, информатики, финансов и права, 2002. - 264 с.ил. В учебном пособии показывается роль образования в современном...»

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

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА Химический факультет Кафедра общей химии О. В. Архангельская, И. А. Тюльков Методическое пособие по курсу общей и неорганической химии для студентов первого курса факультета фундаментальной медицины Москва – 2004 МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА Химический факультет Кафедра общей химии Утверждено Учебно-методической комиссией кафедры общей химии О. В. Архангельская, И. А. Тюльков Методическое пособие по...»

«УДК 528.281 Гиенко Е.Г., Канушин В.Ф. Геодезическая астрономия: Учебное пособие.Новосибирск: СГГА, 2003.-.с. ISBN 5-87693 – 0 Учебное пособие составлено в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования и программой курса “Геодезическая астрономия” для геодезических специальностей, содержит основные сведения по сферической астрономии, теоретические понятия, положения и выводы, составляющие математический аппарат для решения задач...»

«Муниципальное бюджетное образовательное учреждение Новосолянская средняя общеобразовательная школа №1 Рассмотрено: Рассмотрено Согласовано Утверждаю зам. директора по УВР Директор МБОУ СОШ №! на заседании кафедры (методического объединения) Учителей гуманитарного цикла _ _ Протокол № сентября _ сентября 2013г. 2013г. __2013г. Руководитель кафедры (методического объединения) _ РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА История России и Всемирная история 8 класс Составитель: учитель истории МБОУ СОШ № Рыбинского...»

«Министерство образования и науки Российской Федерации Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Чувашский государственный педагогический университет им. И.Я. Яковлева Концепции современного естествознания Учебно-методический комплекс для студентов вузов Чебоксары 2007 ББК 20я73 К 652 Тихонов А.С., Петров Г.А. Концепции современного естествознания: Учебно-методический комплекс для студентов вузов. Чебоксары:...»

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

«Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Ивановская государственная текстильная академия (ИГТА) Кафедра материаловедения и товароведения МАТЕРИАЛЫ ДЛЯ ОДЕЖДЫ И КОНФЕКЦИОНИРОВАНИЕ МЕТОДИЧЕСКИЕ УКАЗАНИЯ к выполнению контрольных работ для студентов специальности 260901 (280800) Технология швейных изделий заочной формы обучения Иваново 2009 Методические указания предназначены для студентов заочного факультета специальности...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

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