Применение методов линейного программирования для решения экономических задач

Ячейка а₃,b₂, транспортной таблицы, должна загрузиться.

	b1= 15	b2= 30	b3= 65	b4= 20	b5= 10
a1= 50		5     -	45     +
a2= 20			10		10
a3= 30		+	10     -	20
a4= 40	15	25

Ячейка а₁,b₂ становится свободной.

M =

5

 

	b1= 15	b2= 30	b3= 65	b4= 20	b5= 10
a1= 50			50
a2= 20			10		10
a3= 30		5	5	20
a4= 40	15	25

 

Итерация: 6 
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.

	b1	b2	b3	b4	b5
a1	19	12	2	14	9	u1= 1
a2	14	5	4	18	3	u2= 3
a3	4	8	12	1	7	u3= 11
a4	1	4	1	20	11	u4= 7
	v1= -6	v2= -3	v3= 1	v4= -10	v5= 0

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

	b1= 15	b2= 30	b3= 65	b4= 20	b5= 10
a1= 50			50     2
a2= 20			10     4		10     3
a3= 30		5     8	5     12	20     1
a4= 40	15     1	25     4

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

50*2+10*4+10*3+5*8+5*12+20*1+15*1+25*4=  100+40+30+40+60+20+15+100= (100+100)+(40+60)+(30+20)+40+15=200+100+50+55=405   Vопт= 405   Ответ:  Оптимальный план содержит 8 перевозок: от 1 поставщика – 50 ед. к третьему потребителю; от 2 поставщика – 10 ед. к третьему и 10 ед. к пятому; от 3 поставщика –   5 ед. ко второму, 5 ед. к третьему и 20 ед. к четвёртому; от 4 поставщика – 15 ед. первому и 25 ед. второму потребителям. При этом общая сумма транспортных расходов минимальна и составляет 405 ден. ед.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.2 Решение двойственной задачи графическим методом.

 

 

Дана задача:

 

V(X) = 5x₁+5x₂+x₃+x₄ → max

 

А так же ограничения:

 
        -2x₂ -3x₃+x₄ = 1 
2x₁+3x₂+2x₃+x₄ = 6

 

 

 x_i≥0, i = 1,2,3,4

 

 

Составить и решить задачу, двойственную данной задаче.

 

1. Составим расширенную матрицу системы

 
              0  -2  -3  1   1

 

A₁ =       2    3   2  1   6

 

              5    5   1  1   V   
 
 
2. Найдём матрицу A₁^T, транспонированную к A₁: 

                 0  2     5

                -2   3      5

A₁^T  =      -3   2      1

                1   1      1

                1   6      Z

 

3. Далее, сформулируем двойственную  задачу:

 

Z = y₁ + 6y₂ → min

           2y₂ ≥ 5

-2y₁ + 3y₂ ≥ 5

-3y₁ + 2y₂ ≥ 1

   y₁  +   y₂ ≥ 1

 

y_i≥0, i = 1,2

 

Далее, находим минимальное значение целевой функции 

Z = y₁+6y₂ → min

 

Найдём точки ограничений:

 

(1) 2y₂ = 5  
        y₂ = 5/2 = 2.5

 

(2) 2y₁ + 3y₂ = 5

      При y₁ = 0: y₂ = 5/3 ≈ 1.6

      При y₂ = 0: y₁ = 2.5

 

(3) -3y₁ + 2y₂ ≥ 1

      При y₁ = 0: y₂ = 0.5

      При y₂ = 0: y₁ ≈ -0.3

 

(4)  y₁ + y₂ = 1

      При y₁ = 0: y₂ = 1

      При y₂ = 0: y₁ = 1

 

Или:

 

 

 

Это границы области допустимых решений.

 

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

 
Обозначим границы области многоугольника решений.

 

Рассмотрим целевую функцию задачи:

 

F = x₁+6x₂ → min.

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

 

F = 0: F = x₁+6x₂ = 0.

 

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

 

Равный масштаб

 

 

Область допустимых решений представляет собой линию F(x) = const.

Данная прямая F(x) = const пересекает область в точке A.  
 
Координаты этой точки  можно получить из уравнения  (1):

 
0y₁ + 2y₂ = 5 
0*y₁ = 0 
2y₂ = 5 
y₂ = 5/2 = 2.5

 
Далее  найдем минимальное значение целевой функции: 
F(X) = 0 + 6*2.5 = 15

 

 

 

 

 

 

 

 

Заключение

 

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

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

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

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