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

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

кроме третьего уравнения. Укажем разрешающий элемент а32=7.

Теперь мы будем преобразовывать вспомогательную систему (16), по формулам исключения.

a`ij=aij – (ais/ars)*arj

a`iq=aiq – (ais/ars)*arq

b`i=bi - (ais/ars)*br

b`r=br/ars


s=1, r=2


a`11=0

a`13=4-2/7*7=2

a`14=0+2/7 *1=2/7

a`15=1

a`16= -5/14

a`17=0-2/7*1=-2/7

a`21=1

a`23= -1/2

a`24=4/7

a`25=0

a`26=2/7

a`27= -1/14

a`31= a31/a32=0

a`32=1

a`33= a33/a32=1

a`34= -1/7

a`35= 0

a`36=-1/14

a`37=1/7

a`41= 0

a`42= -14+2*7=0

a`43= 4

a`44=3

a`45=0

a`46=8

a`47=2

a`12=a`22=0

b`1=29-84/7*2=5

b`2=37-84/7*1/2=31

b`3=84/7=12


Эта система преобразуется к виду

                            2 x3  + 2/7 x4 + x5 – 5/14 x6 – 2/7 x7  = 5

                 x1   - Ѕ x3  +   x4           + 2/7 x6 – 1/14 x7  = 31                    (18)

                     x2  +  x3  - 1/7 x4          – 1/14 x6  + 1/7 x7 = 12

                             4 x3 +  3 x4           +     8 x6 +     2 x7 = 1500 - z


Первые три уравнения системы (18) представляют некоторый предпочитаемый эквивалент системы уравнений (5) и определяют базисное неотрицательное решение системы условий рассматриваемой задачи

x1=37, x2=0, x3=0, x4=0, x5=29, x6=0, x7=84                                  (19)

т.е. определяют производственную программу x1=37, x2=0, x3=0, x4=0        (20)

и остатки ресурсов:      

первого вида х5=5

второго вида       х6=0                                                                (21)

третьего вида х7=0

Последнее уравнение системы (18) мы получаем, исключая х2. В последнем уравнении системы (18) среди коэффициентов при неизвестных в левой части уравнения нет ни одного отрицательного. Если из этого уравнения выразить функцию цели z через остальные неотрицательные переменные  

z = 1500 - 4 x3 -  3 x4 - 8 x6 - 2x7                                   (22)

то становится совершенно очевидным (в силу того, что все xj³0), что прибыль будет наибольшей тогда, когда

x3=0, x4=0, x6=0, x7=0                                                       (23)

Это означает, что производственная программа (20) является наилучшей и обеспечивает предприятию наибольшую прибыль zmax = 1500                                                               (24)

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

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

Воспользуемся тем, что в оптимальной производственной программе x3=0, x4=0. Предположим, что четвертую и третью продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:             

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

                                                         

Следует при этом обратить внимание на то, что последовательное улучшение производственной программы  (x1=0, x2=0) ® (x1=37, x2=0) ® (x1=31, x2=12) на графике означает движение от одной вершины многогранника допустимых решений к другой вершине по связывающей их стороне многоугольника.

  ДВОЙСТВЕННАЯ ЗАДАЧА

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

Теперь представим себе, что знакомый предприниматель П, занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у нас, предлагает нам "уступить" по определенным ценам все имеющиеся у нас ресурсы и обещает платить у1 рублей за каждую единицу первого ресурса, у2 руб – второго, у3 руб – третьего. Возникает вопрос: при каких ценах у1, у2, у3 мы можем согласиться с предложением П.

5 различных задач по программированиюВеличины у1, у2, у3 принято называть расчетными, или двойственными, оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие.

Напомним, что в нашей задаче технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С имели вид 

Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А, 2 единицы ресурса первого вида, 4 единицы ресурса второго вида и 2 единицы третьего (элементы первого столбца матрицы). В ценах у1, у2, у3 наши затраты составят 2у1 + 4у2 + 2у3, т.е. столько заплатит предприниматель П за все ресурсы, идущие на производство единицы продукции первого вида. На рынке за единицу первой продукции мы получили бы прибыль 36 руб. Следовательно, мы можем согласиться с предложением П только в том случае, если он заплатит не меньше 2у1 + 4у2 + 2у3 ³ 36.

Аналогично, для трех оставшихся видов продукции:

3у1 + 2у2 + 8у3³32

4у1 +          7у3³10

 у1 + 2у2          ³13

Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить   103у1 + 148у2 + 158у3 рублей. При поставленных нами условиях предприниматель П будет искать такие значения величин у1, у2, у3, чтобы эта сумма была как можно меньше. Подчеркнем, что здесь речь идет не о ценах,  по которым мы когда-то приобретали эти ресурсы, а об этих ценах, которые существенно зависят от применяемых нами технологий, объемов ресурсов и от ситуации на рынке.

Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок  у(у1, y2, y3) минимизирующий общую оценку всех ресурсов                       f =  103у1 + 148у2 + 158у3                      (1)

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

2у1 + 4у2 + 2у3 ³ 36

3у1 + 2у2 + 8у3³32                                          (2)

4у1 +          7у3³10

 у1 + 2у2          ³13

причем оценки  ресурсов не могут быть отрицательными  y10,  y25 различных задач по программированию0,  y30.       (3)

Решение полученной задачи легко найти с помощью второй основной теоремы    двойственности,  согласно     которой     для     оптимальных решений   5 различных задач по программированию(х1, х2, х3, х4)    и   5 различных задач по программированию(y1, y2, y3) пары двойственных задач необходимо и достаточно выполнение условий

5 различных задач по программированию5 различных задач по программированию       x 1 (2у1 + 4у2 + 2у3 - 36) = 0                          y1 (2x1 +3x2 + 4x3 + x4 - 103) = 0

       x 2 (3у1 + 2у2 + 8у3 - 32) = 0                       y2 (4x1 +2x2           + 2x4 - 148) = 0

  x 3  (4у1 +          7у3-  10) = 0                             y3 (2x1 +8x2 + 7x3              - 158) = 0         .

       x 4  (у1   + 2у2          -  13) = 0             

Ранее было найдено, что в решении исходной задачи х1>0,  x2>0.  Поэтому

5 различных задач по программированию                                                          2y1 + 4y2 + 2y3 - 36 = 0

                                                                   3y1 + 2y2 + 8y3  - 32 = 0

Если же учесть, что первый ресурс был избыточным и, согласно той же теореме двойственности, ее двойственная оценка равна нулю  у1=0,

то приходим к системе уравнений

5 различных задач по программированию                                                             4y2 + 2y3 - 36 = 0

                                                            2y2 + 8y3  - 32 = 0

откуда следует     у2=8,  у3=2.

Таким образом, получили двойственные оценки ресурсов              у1=0;  у2=8;   у3=2,    (4)

причем общая оценка всех ресурсов равна 1500.

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

ЗАДАЧА О "РАСШИВКЕ УЗКИХ МЕСТ ПРОИЗВОДСТВА"

При выполнении оптимальной производственной программы второй и третий ресурсы используются полностью, т.е. образуют ²узкие места производства². Будем их заказывать дополнительно. Пусть T(t1,t2,t3)- вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие            H + Q-1T  0.

Задача состоит в том, чтобы найти вектор    T (0, t2, t3),  максимизирующий суммарный прирост прибыли             W = 8t2 + 2t3                                       (1)     при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)

(2)
                                         

предполагая,     что      можно       надеяться       получить      дополнительно не более 1/3 первоначального объема ресурса каждого вида                              5 различных задач по программированию         5 различных задач по программированию          (3)   

причем по смыслу задачи                                  t2  0,   t3  5 различных задач по программированию 0.     (4)                                                                            

Переписав неравенства (2) и (3) в виде:

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

      из  условия (3) следует t2£148/3, t3£158/3   (6)

приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).

Эту задачу легко решить графически: см. рис. 2. Программа ²расшивки² имеет вид

                           t1=0, t2=14, t3=0  и прирост прибыли составит 112.

Сводка результатов приведена в  таблицe 2.

сj 36 32 10 13 b x4+i yi ti
2 3 4 1 103 5 0 0
aij 4 2 0 2 148 0 8 14
2 8 7 0 158 0 2 0
xj 31 12 0 0 1500 112
Dj 0 0 4 3
ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Однородный продукт, сосредоточенный в 3 пунктах производства (хранения) в количествах 40; 60; 70 единиц, необходимо распределить между 4 пунктами потребления, которым необходимо соответственно 36; 32; 40; 53 единиц. Стоимость перевозки единицы продукта из пункта отправления в пункт назначения известна для всех маршрутов и равна С =   5 различных задач по программированию   5 различных задач по программированию. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы  по доставке продуктов были минимальными.

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

Общий объем производства åаi =40+60+70=170 больше, чем требуется всем потребителям åbi = 36+32 +40 +53

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

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

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

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