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

Страницы работы

12 страниц (Word-файл)

Содержание работы

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 ai   =   S bj                                        (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 xij Cij                                               (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.

          Вычисляем величины ui ,vj по формуле (3), тогда

             Cij=ui+vj                                                          (9)

          Принимаем u1=0.

С11=u1+v1        v1= 2

С21=u2+v1       u2= -1

С22=u2+v2        v2= 6

С32=u3+v2       u3= -2

С33=u3+v3        v3= 4

С43=u4+v3       u4=   1

По формуле

                              Δij= ui+vj-Cij                                                           (10)

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

Δ12 = u1+v2-C12 =3                                       

Δ13 = u1+v3-C13 = 0

Δ23 = u2+v3-C23 =0

Δ31 = u3+v1-C31 = - 6

Δ41 = u4+v1-C41 = - 4

Δ42 = u4+v2-C42 = - 1

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

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

Похожие материалы

Информация о работе