Линейная производственная задача

 Перепишем неравенства (2) и  (3) в виде. Получим:

- t₂ + t₃  18               -t₂ +   6t₃  £ 162

- t₂   30      Þ     -t₂            £ 90 (5)

t₂   - t₃   46               2t₂ -  3t₃   £ 414

  t₂ £ 30, t₃ £ 66        (6)

Задача оказалась с 3-мя переменными, поэтому, согласно с заданием, мы решим её графически (рис.2).

 

 

 

 

 

W=7t₂ + 9t₃ ® max             

-t₂  + 6t₃ £ 162 (1)

-t₂           £ 90 (2)

2t₂ - 3t₃  £ 414 (3)

t₂ £ 30  (4)

t₃ £ 66  (5)

t₂ ³ 0, t₃ ³ 0

Рисунок 2

 

(1)	t2	0	-162
	t3	27	0

 

(2)	t2	0	0
	t3	-90	-90

 

(3)	t2	0	207
	t3	-138	0

 

По графику на рисунке 2 видно, что  решение данной задачи находится  в точке А(30; 32). Таким образом, программа «Расшивки узких мест производства» имеет вид: t₁=0, t₂=30, t₃=32 и прирост прибыли составит W= 7*30 + 9*32 = 498

 

Сводная таблица результатов по пунктам 1-5

Cj	27	39	18	20	Bi	X4+i	Yi	Ti
	2	1	6	5	140	18	0	0
aij	0	3	0	4	90	0	7	30
	3	2	4	0	198	0	9	32
Xj	46	30	0	0	2412			498
Dj	0	0	18	8

 

 

 

 

 

 

 

 

 

Динамическое программирование. Распределение  капитальных вложений.

Пусть производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. руб. (b=700), выделяемые предприятиям суммы кратны 100 тыс.руб. Значения функций f_j(x_j) приведены в табл. 1.

Прежде всего заполняем табл.3. Значения f₂(x₂) складываем со значениями F₁(x-x₂)=f₁(x-x₂) и на каждой побочной диагонали находим наибольшее число, которое помечаем звёздочкой. Заполняем табл .3.

Продолжая процесс табулируем функции  F₃(x), x₃(x) и т.д. В табл.6 заполняем только одну диагональ для значения x=700.

Таблица 1

Xj	0	100	200	300	400	500	600	700
f1(xj)	0	15	26	38	45	52	58	63
f2(xj)	0	10	17	23	29	34	38	41
f3(xj)	0	11	19	26	30	33	35	36
f4(xj)	0	25	34	41	46	50	53	56

Таблица 2

	x-х2	0	100	200	300	400	500	600	700
х2		0	15	26	38	45	52	58	63
0	0	0*	15*	26*	38*	45	52	58	63
100	10	10	25	36	48*	55*	62*	68	---
200	17	17	32	43	55*	62*	69*	---	---
300	23	23	38	49	61	68	---	---	---
400	29	29	44	55	67	---	---	---	---
500	34	34	49	60	---	---	---	---	---
600	38	38	53	---	---	---	---	---	---
700	41	41	---	---	---	---	---	---	---

Таблица 3

x	0	100	200	300	400	500	600	700
F2(x)	0	15	26	38	48	55	63	69
x2(x)	0	0	0	0	100	200	200	200

Таблица 4

	x-x3	0	100	200	300	400	500	600	700
x3		0	15	26	38	48	55	62	69
0	0	0*	15*	26*	38*	48	55	62	69
100	11	11	25	37	49*	59*	66	73	---
200	19	19	34	45	57	67*	74*	---	---
300	26	26	41	52	64	74*	---	---	---
400	30	30	45	56	68	---	---	---	---
500	33	33	48	59	---	---	---	---	---
600	35	35	50	---	---	---	---	---	---
700	36	36	---	---	---	---	---	---	---

Таблица 5.

x	0	100	200	300	400	500	600	700
F3(x)	0	15	26	38	49	59	67	74
x3(x)	0	0	0	0	100	100	200	300

Таблица 6.

	x-x4	0	100	200	300	400	500	600	700
x4		0	15	26	38	49	59	67	74
0	0								74
100	25							92
200	34						93*
300	41					90
400	46				84
500	50			76
600	53		68
700	56	56

Наибольшее число диагонали  в табл.6 :

Z_max = 93 тыс. рублей

X₄* =  X₄(700) = 200 тыс. рублей      

X₃*+X₂*+X₁*=700–200=500 тыс. рублей

 

В табл.5.     

Х₃* = X₃(700- X₄*) = X₃(500) =100  тыс. рублей                             

Х₂*= X₂(700- X₄*- Х₃*) = X₂(400) =100  тыс. рублей                             

 

В табл.3.   

Х₁*=700- X₄*- Х₃*- Х₂*= 700–200-100-100=300 тыс. рублей                             

 

Самопроверка:

f₁(X*₁)+f₂(X*₂)+f₃(X*₃)+f₄(X*₄)=Z_max    

38+10+11+34=93 тыс. рублей                                  

 

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

Х₁* = 300 ;     Х₂* = 100 ;   Х₃* = 100 ;  Х₄* = 200 , при этом максимальная прибыль составляет 93 тыс. руб.

 

 

 

 

 

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

Транспортная задача формулируется  следующим образом. Однородный продукт, сосредоточенный в m пунктах производства (хранения) в количествах   а₁, а₂, ... а_m единиц, необходимо распределить между n пунктами потребления, которым необходимо соответственно   b₁, b₂, ... b_n единиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна с_ij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы  по доставке продуктов были минимальными.

Для решения транспортной задачи чаще всего применяется метод потенциалов.

 

Пусть исходные данные задачи имеют вид

А(а₁, а₂, а₃) = (70; 40; 60);    В(b₁, b₂, b₃, b₄) = (27; 39; 48; 40);

 

           2   1   6   5

 C =     5   3   7   6

           3   2   4   2

Общий объем производства åа_i = 70+40+60= 170 больше, требуется всем потребителям åb_i = 37+39+48+40=164, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 170-164 = 6 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

 

 

Первое базисное допустимое решение  легко построить по правилу ²северо-западного угла².