Xreferat.com » Рефераты по информатике и программированию » 5 различных задач по программированию

5 различных задач по программированию

=161, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 170-161 = 9 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

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

5 различных задач по программированию      Потребление b1  =36 b2  =32 b3  =40 b4  =53 b5  =9
5 различных задач по программированиюПроизводство
 а1  =40 36 4 p1 =0
  a2  =60 28 32   p2 =
  a3 =70     * 8 53 9   p3 =
q1 = q2 = q3 = q4 = q5 =

Общая стоимость всех перевозок для первого базисного допустимого решения:

L= 36* 2 + 4 *3 + 28 *2 + 32 + 8* 7+ 53 =281

Один из потенциалов можно выбрать произвольно, так как в системе (3), (4) одно уравнение линейно зависит от остальных. Положим, что р1 = 0. Остальные потенциалы находим из условия, что для базисных клеток . В данном случае получаем

                  D11 = 0,            p1 + q1 - c11 = 0,          0+q1 -2 = 0,     q1 = 2

                  D12 = 0,            p1 + q2 - c12 = 0,          0+q2 -3 = 0,     q2 = 3

D22 = 0,      p2 + q2 - c22 = 0,          р2 +3-2 = 0,     р2 = -1

и т.д., получим: q3=2, p3=5, q4= -4, q5= -5.

Затем по формуле (6) вычисляем оценки всех свободных клеток:

                  D21 =    p2 + q5 - c21 = -1+2-4 = -3

                  D31 =    p3 + q1 - c31 = 5+2-2 = 5

                  D32 = 1;  D13 = -2;  D14 = -5;  D24 = 0;  D15 = -5;  D25 = -6.

Находим наибольшую положительную оценку  max (5 различных задач по программированию) = 5 =

Для найденной свободной клетки 31 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 31-11-12-22-23-33. Производим перераспределение поставок вдоль цикла пересчета

36 4 36-r 4+r 28 12
5 различных задач по программированию5 различных задач по программированию 28 32 28-r 32+r 20 40
8 r 8-r 8

5 различных задач по программированию= 8

Получаем второе базисное допустимое решение:

5 различных задач по программированию         bj b1  =36  b2  =32 b3  =40 b4  =53   b5=9
    ai
5 различных задач по программированию а1  =40      28 12     * p1 =0
  a2  =60 20 40 p2 = -1
  a3 =70  8 53 9 p3 =0
q1 =2 q2 = 3 q3 = 2 q4 = 1 q5=0

Находим новые потенциалы, новые оценки.

5 различных задач по программированию5 различных задач по программированиюD13 = -2;  D14 = 0;  D15 = 0;  D21 = -3;  D24 = -2;  D25 = -1; D32 = -4;  D33 = -5,

т.е. все Dij £ 0       i = 1,m; j = 1,n

5 различных задач по программированию      5 различных задач по программированию   

 Общая стоимость всех перевозок для второго базисного допустимого решения:

L= 28* 2 + 12 *3 + 20 *2 + 40 + 8* 2+ 53 =241 – минимальная стоимость.

 

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. РАСПРЕДЕЛЕНИЕ КАПИТАЛЬНЫХ ВЛОЖЕНИЙ Пусть производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций fj(xj) приведены в таблице 1, где, например, число 50 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 50 тыс. руб.                                                                                   Таблица I   Прежде всего заполняем табл. 2. Значения f2(x2) складываем со значениями F1(x - x2) = f1(x- x2) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение  . Заполняем таблицу 3. Продолжая процесс, табулируем функции F3(x),     (x)  и т.д. В табл. 6 заполняем только одну диагональ для значения x= 700. Таблица 2 x - x2            0    100    200    300    400    500    600    700 x2   F1(x - x2) f2(x2)             0      15      24      30      36      40      43      45 0 0        0      15      24      30      36      40      43      45 100            18           18*   33*     42*   48      54      58      61 200            26           26     41      50*    56      62      66 300            34           34     49      58*   64*    70* 400            39           39     54       63     69 500            42           42     57       66 600            44           44     59 700            46           46                                                                                                                        Таблица 3 x        0     100     200     300     400     500     600     700 F2(x)              0       18       33       42       50       58       64       70 ` (x)      0         0     100     100     200     300     300     300 Таблица 4       x - x3      0    100    200    300    400    500    600    700 x3   F2(x - x3) f3(x3)             0     18       33      42      50      58      64      70 0 0        0     18*     33      42      50      58      64      70 100            16           16    34*     49*    58      66      74      80 200            27           27    45       60*    69      77      85 300            37           37     55      70*    79*    87* 400            44           44     62      77      86 500            48           48     66      81 600            50           50     68 700            56           56                                                                         Таблица 5 x        0     100     200     300     400     500     600     700 F3(x)              0       18       34       49       60       70       79      87  (x)      0        0     100     100     200      300     300     300 Таблица 6 x - x4            0    100    200    300    400    500    600    700 x4   F3(x - x4) f4(x4)             0      18      34      49      60      70      79     87 0    0                                                                                87 100            10                                                                      89* 200            17                                                            87 300            23                                                    83 400            29                                         78 500            34                               68 600            38                     56 700            41           41                                                            . Наибольшее число на этой диагонали:   Zmax = 89 тыс. руб., причем четвертому предприятию должно быть выделено   х*4  =  4 (700) = 100 тыс. руб. На долю остальных трех предприятий остается 600 тыс. руб. Из табл. 5 видно, что третьему предприятию должно быть выделено      x*3 =  3 (700-x*4) =  3 (600) = 300 тыс. руб. Продолжая обратный процесс, находим          x*2 =  2 (700 - x*4 - x*3) =  2 (300) = 100 тыс. руб. На долю первого предприятия остается   x*1 = 700 - x*4 - x*3 - x*2 = 200 тыс. руб. Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям: x*1 =200; x*2 =100; x*3 = 300; x*4 = 100. Оно обеспечивает производственному объединению наибольший воможный прирост прибыли 89 тыс. руб. выполнение равенства:   f1(x*1) + f2(x*2) + f3(x*3) + f4(x*4) = z max                                                                 24+18+37+10=89 ДИНАМИЧЕСКАЯ ЗАДАЧА УПРАВЛЕНИЯ ПРОИЗВОДСТВОМ И  ЗАПАСАМИ Рассмотрим трехэтапную систему управления запасами с дискретной продукцией и динамическим детерминированным спросом. Пусть спрос (заявки) потребителей на нашу продукцию составляют: на первый этап d1=3 единицы, на второй –  d2=2, на третий -  d3=3 единицы. К началу первого этапа на складе имеется 3 единицы продукции, т.е. начальный уровень запаса равен y1=3. Затраты на хранение единицы продукции на разных этапах различны  и составляют соответственно h1=4, h2=3, h3=2. Затраты на производство xj единиц продукции на j-м этапе определяются функцией    jj(xj) = xj2 + 2xj + 2                                                                         т.е. а=1; b=5; с=2. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими. Исходные данные задачи можно кратко записать одной строкой:       d1        d2        d3                    a          b          c                      h1        h2        h3                    y1       3          2          3                      1          2          2                      4          3          2                      3 Воспользовавшись рекуррентными соотношениями, последовательно вычисляем  F1 (x = y2),  F2 (x = y3), ...,  Fk (x = yk+1), ...   и  соответственно  находим        1 (x= y2),  2 (x = y3 ), ..., ` k (x = yk+1), ... Положим k = 1.
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: