Линейное программирование

 

Федеральное государственное  бюджетное образовательное учреждение

высшего профессионального  образования

 

РОССИЙСКАЯ  АКАДЕМИЯ НАРОДНОГО ХОЗЯЙСТВА И  ГОСУДАРСТВЕННОЙ СЛУЖБЫ при ПРЕЗИДЕНТЕ РОССИЙСКОЙ ФЕДЕРАЦИИ

 

ОРЛОВСКИЙ ФИЛИАЛ

 

 

ФАКУЛЬТЕТ <Государственное и муниципальное управление>

Кафедра < Кафедра математики и математических методов в управлении>

 

 

 

 

ТИПОВОЙ РАСЧЕТ

 

 

По  дисциплине: <ЭММ в управлении>

 

Тема: <Линейное программирование >

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Орел-2012

1. ИСХОДНЫЕ  ДАННЫЕ 

Вариант № 33

 

Задача 1

Трудоемкость  производства, чел.-час			Стоимость производства, тыс. руб.
а11	а21	d1	а12	а22	d2
9,5	7,5	500	5,5	3,5	260

 

Прибыль, тыс. руб.		Минимальное число  изделий
c1	c2	d3	d4
1,8	1,5	10	15

 

 

Задача может  быть сформулирована как стандартная  задача линейного программирования с максимизируемой целевой функцией. Обозначим через х₁ — число изделий 1, а через х₂ — число изделий 2, выпускаемых еженедельно.

Имеем следующие  ограничения:

1. Все х_i , i = 1, 2 — целые числа. По смыслу данной задачи х₁ и х₂ — целые числа.
2. , j = 1, 2, ..., m. В данной задаче имеется j = 4 линейных ограничений-неравенств с двумя неизвестными х₁ и х₂ (n = 2), которые имеют следующий стандартный вид:

а₁₁х₁ + а₂₁х₂ £ d₁;

а₁₂х₁ + а₂₂х₂ £ d₂;

а₁₃х₁ + а₂₃х₂ £ d₃;

а₁₄х₁ + а₂₄х₂ £ d₄.

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

9,5х₁ + 7,5х₂ £ 500;

5,5х₁ + 5х₂ £ 260.

Следующие два  ограничения, исходя из условия задачи, формулируются так:

х₁ ³ 10;

х₂ ³ 15.

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

-1х₁ + 0х₂ £ -10;

0х₁ + (-1)х₂ £ -15.

Целевая функция — недельная прибыль фирмы — выразится в виде линейного уравнения

Ц = 1,8х₁ + 1,50х₂ ® max.

Формулируем стандартные  задачи линейного программирования (табл.1).

Таблиц а  1

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

Первая задача	Вторая задача
Ограничения
Все хi ³ 0, i = 1, 2	Все yj ³ 0, j = 1, 2, 3, 4
, j = 1, 2, 3, 4:	, i = 1, 2:
9,5х1 + 7,5х2 £ 520; 5,5х1 + 3,5х2 £ 260; -1х1 + 0х2 £ -10; 0х1 + (-1)х2 £ -15	9,5y1 + 5,5y2 + (-1)y3 + 0y4 ³ 1,8 7,5y1 + 3,5y2 + 0y3 + (-1)y4 ³ 1,50
Целевая функция
Ц = , n = 2:	D = , m = 4:
Ц = 1,8х1 + 1,50х2	D = 500y1 + 260y2 - 10y3 - 15y4
Задача
Максимизировать Ц	Минимизировать D

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

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

 

График строим в следующей последовательности.

Вначале наносим  линии (пунктирные прямые на рис. 1), уравнения  которых заданы равенствами, получаемыми  из соответствующих неравенств-ограничений:

9,5х₁ +7,5х₂ = 500;

5,5х₁ + 3,5х₂ = 260;

 

х₁ = 10;

х₂ = 15.

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

9,5х₁ + 7,5х₂ £ 500;

5,5х₁ + 3,5х₂ £ 260;

х₁ ³ 10;

х₂ ³ 15.

Из неравенств и геометрических соображений ясно, что это область  ограничена многоугольником ABCD, т.е. точки внутри и на границах этого многоугольника имеют координаты х₁ и х₂, смысл которых — число изделий 1 и 2 соответственно, удовлетворяющих ограничениям задачи.

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

Так, для координат вершины А имеем непосредственно значения:

х₁ = 10; х₂ = 15.

Для расчета координат  вершины В необходимо решить систему уравнений:

х₁ = 10;

9,5х₁ + 7,5х₂ = 500.

Получаем координаты вершины В: х₁ = 10; х₂ =54.

Для расчета координат  вершины С необходимо решить систему уравнений:

5,5х₁ + 3,5х₂ = 260;

9,5х₁ + 7,5х₂ = 500.

Сформируем расширенную матрицу :

5,5     3,5     260

9,5     7,5     500

 

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

Разделим строку 1 на а₁₁=5,5

Получим матрицу:

1      0,636363      47,272727

9,5     7,5                 500

 

Вычтем из строки 2 строку 1 умноженную на a₂₁=9,5

Вычитаемая строка:

9,5    6,045454       449,090909

 

Модифицированная матрица:

1      0,636363      47,272727

0      1,454545      50,909090

 

 

Разделим строку 2 на  a₂₂ =4,454545

Получим матрицу:

1      0,636363      47,272727

0           1               35

 

Вычитаем из строки 1 строку 2 умноженную на а₁₂=0,636363

Вычитаемая строка:

0      0,636363      22,272727

 

Модифицированная матрица:

1        0         25

0        1         35

 

 

Выпишем систему  уравнений по последней расширенной  матрице:

х₁ = 25;

х₂ = 35.

Отсюда координаты вершины С: х₁ = 25; х₂ = 35.

 

Для расчета  координат вершины D имеем систему уравнений:

5,5х₁ +3,5х₂ = 260;

х₂ = 15.

Координаты вершины D: х₁»37,727=37; х₂ = 15.

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

 

Таблица  2

Координаты  вершин многоугольника допустимых решений  и значения целевой функции

Порядковый	Вершина	Координаты  вершины		Целевая,
номер плана	(точка)	Число изделий 1	Число изделий 2	функция,                тыс. руб.
1	А	10	15	40,5
2	В	10	54	99,0
3	С	25	35	97,5
4	D	37	15	89,1

 

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

Способ решения  №2

Построение  касательных в вершинах А,В,С,В  параллельных Ц, отвечающей нулевому значению целевой функции Ц = 0.

 Ц = 1,8х₁ + 1,50х₂, получаем:

х₂ = –(1,8/1,5)* х₁=-1,2 х₁

Наиболее удаленная  касательная, параллельная Ц = 0- в точке В,

Ц® max при х1=10,  х2=54.    Ц=99,00 (тыс.руб).

Оптимальным является план производства 10 изделий вида 1 и 54 изделий вида 2. Ему отвечает наибольшая прогнозируемая прибыль 99,0тыс. руб.

 

Задача 2

Потребности строек, машин			Возможности поставок, машин
w1	w2	w3	f1	f2
5	9	8	11	11

 

Издержки перевозок, тыс. руб
c11	c12	c13	c21	c22	c23
3	2	2	1	4	3

 

 

 

Таблица  3

Исходные  данные задачи

(издержки  перевозок c_ij, потребности w_j, мощности поставок f_i)

	Издержки перевозок  с i-го завода на j-ю стройку,               тыс. руб на машину			Возможности  поставок заводов,
Кирпичные		Стройки		автомашин в
заводы	W1	W2	W3	неделю
F1	с11 = 3	с12 = 2	с13 = 2	f1 = 11
F2	с21 = 1	с22 = 4	с23 = 3	f2 = 11
Потребность строек,            автомашин в неделю	w1 = 5	w2 = 9	w3 = 8	= = 22