Методические указания к задаче № 9

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

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

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

В общем виде математическая модель задачи ЛП:

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

Математическая модель в более краткой записи имеет вид:

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

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

Множество допустимых решений образует область допустимых значений (ОДР).

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

Базисное допустимое решение является опорным решением, где r – ранг системы ограничений.

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

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

Чтобы составить математическую модель задачи ЛП, необходимо:

1) ввести обозначения переменных;

2) исходя из цели экономических исследований, составить целевую функцию;

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

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

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

Алгоритм симплексного метода.

1.Математическая модель задачи должна быть канонической. Если она неканоническая, то ее надо привести к каноническому виду.

2.Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу. Все строки таблицы 1-го шага, за исключением индексной строки, заполняются по данным системы ограничений и целевой функции.

Таблица 1.

ci	БП	c1	c2	…	cm	cm+1	…	cn	F(x)
x1	x2	…	xm	xm+1	…	xn	bi
c1	x1			…		h1,m+1	…	h1,n	b1
c2	x2			…		h2,m+1	…	h2n	b2
…	…	…	…	…	…	…	…	…	…
cm	xm			…		hm,m+1	…	hmn	bm
∆j			…	0	∆m+1	…	∆n

Индексная строка для переменных находится по формуле

и по формуле для свободного члена.

Возможны следующие случаи при решении задачи на максимум:

· Если все оценки , то найденное решение оптимальное.

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

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

· Если отрицательных оценок в индексной строке несколько, то в столбец БП вводят ту переменную, которой соответствует наибольшая по модулю отрицательная оценка.

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

3.Заполняем симплексную таблицу 2-го шага:

– переписываем ключевую строку, разделив ее на ключевой элемент;

– заполняем базисные столбцы;

– находим остальные коэффициенты таблицы и оценки.

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

Пример. Для производства продукции двух типов предприятие использует два вида сырья. Данные об условиях приведены в таблице.

Сырье	Расход сырья на единиц продукции, кг/ед.	Количество сырья, кг
1 тип	2 тип
1 вида
2 вида
Прибыль, тыс.руб./ед. продукции

Составить план производства по критерию «максимум прибыли».

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

Обозначим: x₁ – единиц продукции 1 типа должно выпускать предприятие; x₂ – единиц продукции 2 типа должно выпускать предприятие.

Целевая функция строится на максимум прибыли: .

Ограничения по запасам сырья: .

Неизвестные должны быть неотрицательны: .

Модель неканоническая, приведем ее к каноническому виду, для этого в левую часть первого неравенства введем балансовую переменную x₃, а второго неравенства – x₄. Получим каноническую модель:

Составим симплексную таблицу первого шага.

ci	БП					f
x1	x2	x3	x4	bi
	x3
	x4
∆j	-2	-3

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

Таблица 1

ci	БП					f
x1	x2	x3	x4	bi
	x3
	x4
∆j	-2	-3

Ключевой элемент 3, соответствующий второму столбцу, т.е. – x₂. Значит, чтобы построить таблицу 2-го шага необходимо из базисного столбца вывести x₃, а ввести в него x₂. При этом всю первую строку разделим на ключевой элемент, т.е на 3. И заполняем базисные столбцы.

ci	БП					f
x1	x2	x3	x4	bi
	x2	1/3		1/3
	x4
∆j

Найдем оставшиеся коэффициенты. Во втором столбце 1 таблицы стоит 1, а во второй таблице – 0. 0 = 1 – 1, т.е. из второй строки 1 таблицы нужно вычесть первую строку 2 таблицы. Оценки найдем по формулам: , .

ci	БП					f
x1	x2	x3	x4	bi
	x2	1/3		1/3
	x4	2/3		- 1/3
∆j	-1

Получили F = 300, т.е. план улучшился.

Отрицательная оценка одна, она соответствует 1 столбцу. Найдем ключевую строку: . Ключевой элемент 2/3.

Таблица 2

ci	БП					f
x1	x2	x3	x4	bi
	x3	1/3		1/3
	x4	2/3		- 1/3
∆j	-1

Строим таблицу 3 шага. Вместо x₄ в базисный столбец вводим x₁. вторую строку 2 таблицы делим на 2/3 и заполняем базисные столбцы.

ci	БП					f
x1	x2	x3	x4	bi
	x2
	x1			- 1/2	3/2
∆j

В первой строке 2 таблицы стоит 1/3, а в третьей таблице 0. .

Т.е. надо из элементов 1 строки 2 таблицы вычесть элементы 2 строки 2 таблицы, разделенные на 2.

Таблица 3.

ci	БП					f
x1	x2	x3	x4	bi
	x2			1/2	- 1/2
	x1			- 1/2	3/2
∆j			1/2	3/2

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

Ответ. Предприятие должно выпускать 75 единиц продукции 1 типа и 75 единиц продукции 2 типа, получая при этом максимальную прибыль 375 тыс. р.

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

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

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

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

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

Пример.

Пример. Фирма выпускает три вида изделий А, Б, В. Все данные для одной смены приведены в таблице.

Ресурсы, ед.	Изделие А	Изделие Б	Изделие В	Объем ресурсов.
Оборудование Сырье Электроэнергия
Прибыль, у.е.

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

Решение. Пусть – необходимо выпускать изделий A, Б, B соответственно.

Составим математическую модель задачи.

Найдем симплексным методом оптимальное решение.

Таблица 1.

ci	БП							f
x1	x2	x3	x4	x5	x6	bi
	x4
	x5
	x6
	-40	-50	-10
0	x4	2,5				-0,5
	x2	0,25				0,25
	x6	2,25				-0,75
	-27,5		-10		12,5
	x1				0,4	-0,2		10,8
	x2				-0,1	0,3		9,3
	x6				-0,9	-0,3		6,7
			-10
40	x1				0,4	-0,2		10,8
	x2				-0,1	0,3		9,3
	x3				-0,9	-0,3		6,7
∆j

Отрицательных оценок нет. Получили оптимальное решение , но оно не является целочисленным.

Найдем дробные части значений :

Наибольшее значение , что соответствует первой строке. Дробные части не целочисленных коэффициентов в этой строке:

Составим дополнительное ограничение по целочисленности:

или

и введем его в таблицу 2.

Таблица 2.

Ci	БП								f
x1	x2	x3	x4	x5	x6	x7	bi
	x1				0,4	-0,2			10,8
	x2				-0,1	0,3			9,3
	x3				-0,9	-0,3			6,7
					0,4	0,8		-1	0,8
40	x1					-1
	x2					0,5		-0,25	9,5
	x3					1,5		-2,25	8,5
	x4							-2,5
∆j

Отрицательных оценок нет. Получили оптимальное решение , но оно не является целочисленным.

Найдем дробные части значений :

Дробные части одинаковы, что соответствует второй и третьей строкам. Дробные части не целочисленных коэффициентов во второй строке:

Составим новое ограничение по целочисленности: или .

Введем его в симплексную таблицу 3.

Таблица 3.

ci	БП									f
x1	x2	x3	x4	x5	x6	x7	x8	bi
	x1					-1
	x2					0,5		-0,25		9,5
	x3					1,5		-2,25		8,5
	x4							-2,5
∆j					0,5	0,75		-1	0,5
40	x1						1,5		-2
	x2						-0,75	-0,25
	x3						-1,25	-2,25
	x4
	x5						1,5		-2
∆j

Отрицательных оценок нет. Получили оптимальное решение , оно является целочисленным.

Ответ. Чтобы получить максимальную прибыль 960 у.е. при имеющихся ресурсах, необходимо выпускать 11 изделий вида А, 9 изделий вида Б, 7 изделий вида В.

ВОПРОСЫ ДЛЯ ИТОГОВОГО КОНТРОЛЯ

1. Что называется матрицей? Как определяются линейные операции над матрицами, и каковы их свойства?

2. Как сложить две матрицы и всегда ли это можно сделать?

3. Как умножить матрицу на число?

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

5. Что называется минором и алгебраическим дополнением?

6. Что называется определителем (детерминантом) второго и третьего порядков, каковы их свойства?

7. Каковы способы вычисления определителей?

8. Что называется произведением двух матриц? Каковы свойства произведения матриц?

9. Как умножить матрицу на матрицу? Всегда ли это выполнимо?

10. Какая матрица называется единичной, квадратной и транспонированной?

11. Что называется матрицей и расширенной матрицей системы линейных уравнений?

12. Что называется решением системы линейных уравнений? Какие системы называются совместными, а какие несовместными?

13. Сформулируйте теорему Кронекера-Капелли.

14. Напишите формулы Крамера. В каком случае они применимы?

15. При каком условии система линейных уравнений имеет единственное решение?

16. Что можно сказать о системе линейных уравнений, если ее определитель равен нулю?

17. При каком условии однородная система n линейных уравнений с n неизвестными имеет ненулевое решение?

18. Опишите метод Гаусса решения и исследования систем линейных уравнений.

19. Какие разновидности метода Гаусса вы знаете?

20. Что называется рангом системы линейных уравнений? Как, используя метод Гаусса, можно найти ранг системы линейных уравнений?

21. Какие неизвестные в системе линейных уравнений, и в каком случае называют свободными, а какие базисными?

22. Что называется рангом матрицы? Как его можно найти?

23. Какая матрица называется обратной для данной матрицы? Всегда ли существует обратная матрица? Как можно найти обратную матрицу?

24. Запишите систему линейных уравнений с помощью матриц.

25. В чем состоит матричный способ решения систем линейных уравнений?

26. Что называется вектором и модулем вектора?

27. Какие векторы называются коллинеарными, компланарными, равными?

28. Могут ли два вектора, имеющих равные модули, быть не равными? Если да, то чем они могут различаться?

29. Все векторы, имеющие один и тот же модуль, отложены из одной точки A пространства. Где находятся концы этих векторов?

30. Какие операции над векторами называются линейными, и каковы свойства этих операций?

31. Что называется базисом на прямой линии, на плоскости и в пространстве?

32. В каком случае векторы называются линейно зависимыми, и в каком – линейно независимыми?

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

34. Какой базис называется ортонормированным?

35. Как определяется, декартова система координат?

36. Как выражаются координаты вектора через координаты его начальной и конечной точек?

37. Что называется скалярным произведением двух векторов, каковы его свойства и как оно выражается через координаты векторов-сомножителей в ортонормированном базисе?

38. Какие свойства скалярного произведения совпадают, а какие отличаются от произведения чисел?

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

40. Каков физический смысл скалярного произведения?

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

42. Что называется векторным произведением двух векторов, каковы его свойства и как оно выражается через координаты векторов-сомножителей в ортонормированном базисе?

43. Что называется смешанным произведением трех векторов, каковы его свойства и как оно выражается через координаты векторов-сомножителей в ортонормированном базисе?

44. Какому условию должны удовлетворять координаты трех векторов, чтобы их можно было принять за базис пространства?

45. Выведите формулы деления отрезка в данном отношении.

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

47. Как определяются в аналитической геометрии линии, поверхности, и другие множества точек?

48. Что называется направляющим вектором прямой и направляющими векторами плоскости?

49. Как записываются параметрические уравнения прямой и плоскости?

50. Какое уравнение плоскости называется уравнением в отрезках?

51. Что называется угловым коэффициентом прямой линии на плоскости, и каков его геометрический смысл в декартовой прямоугольной системе координат?

52. Как записываются уравнения прямой, проходящей через две точки, в пространстве и на плоскости?

53. Какое уравнение плоскости называется нормальным?

54. Как записывается уравнение плоскости, проходящей через три заданные точки?

55. Как построить плоскость по ее уравнению?

56. Как вычисляются углы между двумя прямыми (на плоскости и в пространстве), между двумя плоскостями, между плоскостью и прямой?

57. Каковы условия параллельности и перпендикулярности двух прямых (на плоскости и в пространстве), двух плоскостей, прямой и плоскости?

58. Как найти расстояние от точки до плоскости?

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

60. Дать определение допустимого решения задачи ЛП и области допустимых решений (ОДР).

61. Виды математических моделей.

62. Алгоритм графического метода решения задач ЛП.

63. Алгоритм симплексного метода.

64. Общая формулировка задачи целочисленного программирования.

65. Метод Гомори.

1. Рекомендуемая литература

Основная

1. М.С. Красс, Б.П. Чупрынов. Основы математики и ее приложение в экономическом образовании: Учебник. – 4-е изд., исп. – М.: Дело, 2003.

2. М.С. Красс, Б.П. Чупрынов. Математика для экономических специальностей: Учебник. – 4-е изд., исп. – М.: Дело, 2003.

3. М.С. Красс, Б.П. Чупрынов. Математика для экономического бакалавриата. Учебник. – 4-е изд., исп. – М.: Дело, 2005.

4. Высшая математика для экономистов. Учебник для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера, - 2-е изд., перераб. и доп. – М: ЮНИТИ, 2003.

5. Кремер Н.Ш, Путко Б.А., Тришин И.М., Фридман М.Н.. Высшая математика для экономических специальностей. Учебник и Практикум (части I и II) / Под ред. проф. Н.Ш. Кремера, - 2-е изд., перераб. и доп. – М: Высшее образование, 2007. – 893с. – (Основы наук)

6. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах. М. высшая школа. 1999.

Дополнительная

1. И.И. Баврин, В.Л. Матросов. Высшая математика. «Гуманитарный издательский центр Владос», 2002.

2. И.А. Зайцев. Высшая математика. «Высшая школа», 1998.

3. А.С. Солодовников, В.А. Бабайцев, А.В. Браилов, И.Г. Шандра. Математика в экономике / в двух частях/. М. Финансы и статистика. 1999.