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

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

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

КУРСОВАЯ РАБОТА

по дисциплине "Прикладная математика"

Москва 2001

ОГЛАВЛЕНИЕ

ЛИНЕЙНАЯ ПРОИЗВОДСТВЕННАЯ ЗАДАЧА

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

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

ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. РАСПРЕДЕЛЕНИЕ КАПИТАЛЬНЫХ ВЛОЖЕНИЙ

ДИНАМИЧЕСКАЯ ЗАДАЧА УПРАВЛЕНИЯ ПРОИЗВОДСТВОМ И  ЗАПАСАМИ...

МАТРИЧНАЯ МОДЕЛЬ ПРОИЗВОДСТВЕННОЙ  ПРОГРАММЫ ПРЕДПРИЯТИЯ

МАТРИЧНАЯ ИГРА КАК МОДЕЛЬ КОНКУРЕНЦИИ  И СОТРУДНИЧЕСТВА

АНАЛИЗ ДОХОДНОСТИ И РИСКА ФИНАНСОВЫХ ОПЕРАЦИЙ

ЗАДАЧА ФОРМИРОВАНИЯ ОПТИМАЛЬНОГО ПОРТФЕЛЯ ЦЕННЫХ БУМАГ

ЛИТЕРАТура

ЛИНЕЙНАЯ ПРОИЗВОДСТВЕННАЯ ЗАДАЧА

Предприятие может выпускать четыре вида продукции, используя для этого три вида ресурсов. Известна технологическая матрица А затрат любого ресурса на единицу каждой продукции, вектор В объемов ресурсов и вектор С удельной прибыли

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

Требуется составить производственную программу (x1, x2, x3, x4), максимизирующую прибыль

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

при ограничениях по ресурсам:                                                  (3)

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

Получили задачу на условный экстремум. Для ее решения систему неравенств (3) при помощи дополнительных неотрицательных неизвестных х5, х6, х7 заменим системой линейных алгебраических

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

где дополнительные переменные имеют смысл остатков соответствующих ресурсов. Среди всех решений системы уравнений (5), удовлетворяющих условию неотрицательности  х1³0, х2³0,… ,х5³0,…, х7³0.  (6)

надо найти то решение, при котором функция (2) примет наибольшее значение.

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

     x1=0, x2=0, x3=0, x4=0, x5=103, x6=148, x7=158                          (7)

первые четыре компоненты которого определяют производственную программу x1=0, x2=0, x3=0, x4=0(8)

по которой мы пока ничего не производим. Из выражения (2) видно, что наиболее выгодно начинать производить продукцию первого вида, так как прибыль на единицу продукции здесь наибольшая. Чем больше выпуск в этой продукции, тем больше прибыль. Выясним, до каких пор наши ресурсы позволяют увеличить выпуск этой продукции. Для этого придется записать для системы уравнений (5) общее решение

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

Мы пока сохраняем в общем решении х2=х3=х4=0 и увеличиваем только х1. При этом значения базисных переменных должны оставаться неотрицательными, что приводит к системе неравенств

5 различных задач по программированию    или             т.е.        0 £ х1 £ 37

Дадим х1 наибольшее значение х1 =37, которое она может принять при нулевых значениях других свободных неизвестных, и подставим его в (9). Получаем для системы уравнений (5) частное неотрицательное решение      х1=37, х2=0, х3=0, х4=0; x5=29; x6=0; x7=84             (10)

Нетрудно убедиться, что это решение является новым базисным неотрицательным решением системы линейных алгебраических уравнений (5), для получения которого достаточно было принять в системе (5) неизвестную х1 за разрешающую и перейти к новому предпочитаемому виду этой системы, сохранив правые части уравнений неотрицательными, для чего за разрешающее уравнение мы обязаны принять второе, так как                                 

            5 различных задач по программированию,  а разрешающим элементом будет а21=4.

Остается заметить, что процесс решения обычно записывается в виде некоторой таблицы 1.

~
C
И

  36   32    10    13     0       0           0
Базис Н    x1    x2    x3    x4     x5       x6          x7 Пояснения
0 Х5 103    2     3      4      1       1       0           0 z0 = 5 различных задач по программированиюH
0 Х6 148    4     2      0      2       0       1           0 5 различных задач по программированию
0 Х7 158    2     8      7      0       0       0           1 5 различных задач по программированию
z0  -z 0 - z  -36  -32  -10   -13      0       0           0 5 различных задач по программированию
0 Х5 29    0     2      4     0        1      -1/2        0
0 Х1 37   1    1/2     0    1/2      0        ј         0
36 Х7 84   0      7      7    -1        0       -1/2       1 min (29/2; 64;12)=12
z0  -z 1332-z   0    -14  -10     5        0         9         0 min (-14;-10) = -14
36 Х5 5   0      0     2      2/7      1     -5/14    -2/7
0 Х1 31   1      0  -1/2     4/7     0      2/7     -1/14
14 Х2 12   0      1     1     -1/7     0      -1/14    1/7
z0  -z 1500-z   0      0     4       3       0        8           2 все  Dj ³0

Применим известные формулы исключения

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`12=3-2/4 *2= 2

a`13=4

a`14=1-2/4 *2=0

a`15=1

a`16=0-2/4*1= -2/4

a`17=0

a`32=8-2/4* 2= 7

a`33=7

a`34=0-2/4* 2= -1

a`35= 0

a`36=0-2/4 *1= -2/4

a`37=1

a`21=a21/a21=1

a`22=a22/a21=1/2

a`23=0

a`24=1/2

a`25=0

a`26=1/4

a`27=0

a`41= 0

a`42= -14

a`43= -10

a`44=5

a`45=0

a`46=9

a`47=0

a`11=a`31=0

b`1=103-148/4*2=29

b`2=148/4=37

b`3=158-148/4*2=84


Получаем для системы уравнений (5) новый предпочитаемый эквивалент

5 различных задач по программированию           2x2 + 4x3         + x5  -  1/2x6         = 29

x1 + 1/2x2 +       1/2x4 +         1/4x6         = 37                 (11)

           7x2 + 7x3  -   x4                 -1/2x6  + x7  = 84

Приравняв к нулю свободные переменные х2, х3, х4, х6, получаем базисное неотрицательное решение, совпадающее с (10), причем первые четыре компоненты его определяют новую производственную программу                           х1=37, х2=0, х3=0, х4=0.             (12)

Представим соотношение (2) в виде уравнения -36х1 - 14х2 - 10х3 - 13х4 = 0 – z                 (13)

и припишем его к системе (5). Получается вспомогательная система уравнений


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

Напомним, что разрешающую неизвестную в системе (5) мы выбрали х1. Этой переменной в последнем уравнении системы (14) отвечает наименьший отрицательный коэффициент D1= -36. Затем мы нашли разрешающий элемент а21=4 и исключили неизвестную х1 из всех уравнений системы (5), кроме второго. Далее нам пришлось х1 исключать и из функции (2). Теперь это можно сделать очень просто, если посмотреть на систему уравнений (14). Очевидно, достаточно умножить второе уравнение системы (14) на 9 и прибавить к четвертому; получим       

  -14х2 - 10х3 + 5х4 - 9х6 = 1332 – z                                                          (15)

Таким образом, мы преобразовывали вспомогательную систему уравнений (14) к виду

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

Первые три уравнения этой системы представляют некоторый предпочитаемый эквивалент (11) системы уравнений (5) и определяют базисное неотрицательное решение (10) и производственную программу (12), а из последнего уравнения системы (16) получается выражение функции цели через свободные переменные. Получим следующий предпочитаемый эквивалент системы условий, который определит для системы (5) новое базисное неотрицательное решение и уже третью производственную программу, для исследования которого нам придется выразить функцию z=1332+14x2+10x3-5x4-9x6 через новые свободные переменные, удалив оттуда переменную х2, ставшую базисной.

Очевидно, если имеется хотя бы один отрицательный коэффициент Dj при какой-нибудь переменной xj в последнем уравнении системы (16), то производственная программа не является наилучшей и можно далее продолжать процесс ее улучшения. Мы нашли в последнем уравнении системы (16) наименьший отрицательный коэффициент     min(Dj<0) = min(-14,-10) = -14 = D2. Поэтому принимаем х2 в системе (11) за разрешающую неизвестную, находим разрешающее уравнение по                  5 различных задач по программированию   (17)

и исключаем х2 из всех уравнений системы (11),

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

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

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

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