Разработка программы на языке Pascal, позволяющей определить оптимальный выпуск изделий методом потенциалов (Практическая часть курсовой работы)

2. ПРАКТИЧЕСКАЯ ЧАСТЬ

          2.1 Постановка задачи

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

 Мясокомбинат имеет в своем составе четыре завода, на каждом из которых может изготовляться три вида колбасных изделий. Мощности каждого из заводов соответственно равны 320, 280, 270 и 350 т/сут. Ежедневные потребности в колбасных изделиях каждого вида так же известны и соответственно равны 450, 370 и 400 т. Зная себестоимость 1 т каждого вида колбасных изделий на каждом заводе, который определяется матрицей

                                       2  3  4

         С =    1  5  3

6  4  2

7  8  5

Найти такое распределение выпуска колбасных изделий между

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

Опорный план необходимо построить методом северо-западного угла и методом аппроксимации Фогеля. Решить задачу методом потенциалов, принимая за опорный план, план полученный методом северо-западного угла. 

          2.2 Математическая модель

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

          Запасы:               320  280  270  350

Потребности:     450  370  400 

          Матрица стоимости:

                    2  3  4

                      С=   1  5  3

6  4  2

7  8  5

2.3 Нахождение опорного плана методом северо-западного угла

Начинаем строить опорный план с проверки выполнения условия

баланса. Сумма всех заявок должна быть равна сумме всех запасов.

                                       _{m                    n}

                                       S a_i   =   S b_j                                        (6)

                                        ^{i=1                 j=1}

 

           320+280+270+350 = 450+370+400

                                 1220 = 1220

           Находится количество базисных клеток:

                    r = m+n-1                                           (7)

                    r = 4+3-1 = 6

          Таблица 1 Опорный план, составленный методом северо-западного

        угла

ПН ПО	В1	В2	В3	Запасы ai
A1	2 320	3	4	320
A2	1 130	5 150	3	280
A3	6	4 220	2 50	270
A4	7	8	5 350	350
Потребности bj	450	370	400	1220

          Пункту В1 требуется 320 единиц груза. Удовлетворим эту заявку

за счет запаса в А1 (там 320 ед. груза) запишем перевозки в объеме 320 единиц в клетке (1,1). Запасы в А1 исчерпаны. Потребность В1 удовлетворим за счет запаса А2 (там 280 ед. груза). Запишем в клетку (2,1)  130 ед. груза. Оставшиеся 150 ед. назначим пункту В2. Запишем их в клетке (2,2). Но в В2 мы еще не удовлетворили всю потребность, еще нужны 220 ед., их мы возьмем из пункта А3 и это запишем в клетке (3,2). Теперь потребности В2 полностью удовлетворены. В А3 осталось еще 50 ед. груза, выделим их пункту В3. Чтобы удовлетворить полностью потребность В3 350 ед. груза возьмем из запаса А4. На этом распределение запасов закончим. Каждый пункт получил груз согласно

своим потребностям.

          Полученный план является опорным планом ТЗ, так как  число

клеток, в которых есть перевозки  ř = 6.

          Найдем общую стоимость составленного плана как сумму

произведений объемов перевозок на соответствующие стоимости в этих же клетках:

                                     _{m n}

                              L = S  S x_ij C_ij                                               (8)

                                    ^{i=1  j=1}     

    L=320x2 + 130x1 + 150x5 + 220x4 + 50x2 + 350x5 =4250

2.4 Нахождение опорного плана методом аппроксимации Фогеля

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

аппроксимации Фогеля  находим разности между двумя записанными в столбцах и строках минимальными тарифами. Разности записываем в специально отведенные для этого строке или столбце таблицы 2.

          Таблица 2 Опорный план, составленный методом аппроксимации

       Фогеля

         

ПН ПО	В1	В2	В3	ai	Разности по строкам
A1	2 170	3 150	4	320	3-2=1	1	1	1	1	3
A2	1 280	5	3	280	3-1=2	-	-	-	-	-
A3	6	4 220	2 50	270	4-2=2	2	2	2	4	-

Продолжение таблицы 2

ПН ПО	В1	В2	В3	ai	Разности по строкам
A4	7	8	5 350	350	7-5=2	2	3	-	-	-
bj	450	370	400	1220
Разности по столбцам	1	1	1
	4	1	2
	-	1	2
	-	1	2
	-	1	-
	-	3	-

          Количество базисных клеток ř=6. Найденный план является опорным.

          Находим значение целевой функции.

          L=170х2 + 150х3 + 280х1 + 220х4 + 50х2 + 350х5 = 3800

          2.5 Нахождение оптимального плана методом потенциалов

          За опорный план принимаем план, полученный методом северо-западного угла, таблица 1, раздел 2.3.

          Вычисляем величины u_{i ,}v_j по формуле (3), тогда

             C_ij=u_i+v_j                                                          (9)

          Принимаем u₁=0.

С₁₁=u₁+v₁        v₁= 2

С₂₁=u₂+v₁       u₂= -1

С₂₂=u₂+v₂        v₂= 6

С₃₂=u₃+v₂       u₃= -2

С₃₃=u₃+v₃        v₃= 4

С₄₃=u₄+v₃       u₄=   1

По формуле

                              Δ_ij= u_i+v_j-C_ij                                                           (10)

вычисляется Δ_ij для клетки с индексом ij. Эта операция сводится к сложению двух потенциалов u_i и v_j , находящихся с ней на одной строке и в одном столбце и вычитанию из суммы чисел стоимости C_ij,          находящейся в данной клетке.

Δ₁₂ = u₁+v₂-C₁₂ =3                                       

Δ₁₃ = u₁+v₃-C₁₃ = 0

Δ₂₃ = u₂+v₃-C₂₃ =0

Δ₃₁ = u₃+v₁-C₃₁ = - 6

Δ₄₁ = u₄+v₁-C₄₁ = - 4

Δ₄₂ = u₄+v₂-C₄₂ = - 1

Δ₁₂ =3 является максимальной. В  клетку с  индексом 12 перебрасываем груз из ближайшей заполненной клетки с индексом 22. В результате получаем новый опорный план, который показан в таблице 3.

          Таблица 3 Вторая итерация для метода потенциалов