Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету new!
по каталогу
в рефератах

Динамическое и линейное программирование



 Другие рефераты
Дедукция Десятичные дроби Динамическое программирование (задача о загрузке) Дифференциальные уравнения

1. Линейная производственная задача

   Линейная  производственная  задача   –   это   задача   о   рациональном
использовании имеющихся  ресурсов,  для  решения  которой  применяют  методы
линейного программирования. В общем виде задача  может  быть  сформулирована
следующим образом:
   Предположим, предприятие или цех может выпускать [pic] видов  продукции,
используя [pic] видов ресурсов. При этом известно  количество  каждого  вида
ресурса, расход каждого вида  ресурса  на  выпуск  каждого  вида  продукции,
прибыль, получаемая с  единицы  выпущенной  продукции.  Требуется  составить
такой  план  производства  продукции,  при   котором   прибыль,   получаемая
предприятием, была бы наибольшей.
   Примем следующие обозначения:

|[pic]|Номер ресурса (i=1,2,…,m)                        |
|[pic]|Номер продукции (j=1,2,…,n)                      |
|[pic]|Расход i-го ресурса на единицу j-ой продукции    |
|[pic]|Имеющееся количество i-го ресурса                |
|[pic]|Прибыль на единицу j-ой продукции                |
|[pic]|Планируемое количество единиц j-ой продукции     |
|[pic]      |Искомый план производства                   |


   Таким образом, математическая модель задачи состоит в том,  чтобы  найти
производственную программу [pic] максимизирующую прибыль:
                                    [pic]
   При этом,  какова  бы  ни  была  производственная  программа  [pic],  ее
компоненты  должны  удовлетворять  условию,  что   суммарное   использование
данного вида ресурса,  при  производстве  всех  видов  продукции  не  должно
превышать имеющееся количество данного вида ресурса, т.е.
                              [pic], где [pic]
   А так как компоненты программы – количество изделий,  то  они  не  могут
быть выражены отрицательными числами,  следовательно  добавляется  еще  одно
условие:
                              [pic], где [pic]

   Предположим, что  предприятие  может  выпускать  четыре  вида  продукции
([pic]),  используя  для  этого  три   вида   ресурсов   ([pic]).   Известна
технологическая матрица  [pic]  затрат  любого  ресурса  на  единицу  каждой
продукции, вектор [pic] объемов ресурсов и вектор [pic] удельной прибыли:

                             [pic]  [pic]  [pic]

   Тогда математическая модель задачи будет иметь вид:
  Найти производственную программу [pic] максимизирующую прибыль:
|[pic]                                                |(1.1)         |


  при ограничениях по ресурсам:
|[pic]                                                |(1.2)         |


  где по смыслу задачи: [pic], [pic], [pic], [pic]
  Таким образом, получили задачу на нахождение условного экстремума. Для ее
решения введем дополнительные неотрицательные неизвестные:

|[pic],    |остаток ресурса определенного вида        |
|[pic],    |(неиспользуемое количество каждого        |
|[pic]     |ресурса)                                  |


  Тогда  вместо  системы  неравенств  (1.2),   получим   систему   линейных
алгебраических уравнений:

|[pic]                                                |(1.3)         |


где среди всех решений, удовлетворяющих условию неотрицательности:
               [pic], [pic], [pic], [pic], [pic], [pic], [pic]
надо найти решение, при котором функция (1.1)  примет  наибольшее  значение.
Эту  задачу  будем  решать  методом  последовательного  улучшения  плана   –
симплексным методом.
  Воспользуемся  тем,  что  правые  части  всех  уравнений  системы   (1.3)
неотрицательны, а сама система имеет  предпочитаемый  вид  –  дополнительные
переменные являются базисными. Приравняв к  нулю  свободные  переменные  x1,
x2, x3, x4, получаем базисное неотрицательное решение:
               [pic], [pic], [pic], [pic], [pic], [pic], [pic]
первые четыре компоненты которого  представляют  производственную  программу
[pic], по которой пока ничего не производится.
  Из выражения (1.1)  видно,  что  наиболее  выгодно  начинать  производить
продукцию третьего вида, т.к. прибыль на единицу выпущенной продукции  здесь
наибольшая, поэтому в системе (1.3) принимаем переменную x3  за  разрешающую
и  преобразуем  эту  систему  к  другому  предпочитаемому  виду.  Для   чего
составляем   отношения   правых   частей   уравнений    к    соответствующим
положительным коэффициентам при выбранной неизвестной и  находим  наибольшее
значение  x3,  которое  она  может  принять  при  нулевых  значениях  других
свободных неизвестных, сохранив  правые  части  уравнений  неотрицательными,
т.е.
                                    [pic]
  Оно соответствует первому уравнению в системе (1.3), и  показывает  какое
количество изделий третьего  вида  предприятие  может  изготовить  с  учетом
объемов сырья первого вида. Следовательно, в базис вводим неизвестную x3,  а
исключаем от  туда  неизвестную  x5.  Тогда  принимаем  первое  уравнение  в
системе (1.3) за разрешающее, а разрешающим элементом будет a13=6.
  Применив формулы исключения,  переходим  к  новому  предпочитаемому  виду
системы с соответствующим базисным допустимым решением.
  Полный процесс решения приведен в  таблице  1,  где  в  последней  строке
третьей таблицы  нет  ни  одного  отрицательного  относительного  оценочного
коэффициента
                      [pic],   где [pic],   где [pic],
т.е. выполняется критерий оптимальности для максимизируемой функции (1.1).

|Таблица 1                                                           |
|C |Бази|H |30  |11  |45  |6   |0   |0   |0   |Пояснения       |
|  |с   |  |    |    |    |    |    |    |    |                |
|  |    |  |[pic|    |[pic|[pic|[pic|[pic|[pic|                |
|  |    |  |]   |    |]   |]   |]   |]   |]   |                |
|0 |[pic|15|3   |2   |6   |0   |1   |0   |0   |[pic]           |
|  |]   |0 |    |    |    |    |    |    |    |x3 – разрешающая|
|  |    |  |    |    |    |    |    |    |    |переменная      |
|  |    |  |    |    |    |    |    |    |    |x3 ( в базис.   |
|  |    |  |    |    |    |    |    |    |    |[pic]           |
|  |    |  |    |    |    |    |    |    |    |первая строка – |
|  |    |  |    |    |    |    |    |    |    |разрешающая     |
|  |    |  |    |    |    |    |    |    |    |x5 ( из базиса. |
|  |    |  |    |    |    |    |    |    |    |разрешающий     |
|  |    |  |    |    |    |    |    |    |    |элемент = 6     |
|0 |[pic|13|4   |2   |3   |5   |0   |1   |0   |                |
|  |]   |0 |    |    |    |    |    |    |    |                |
|0 |[pic|12|4   |3   |2   |4   |0   |0   |1   |                |
|  |]   |4 |    |    |    |    |    |    |    |                |
|  |0   |  |-30 |-11 |-45 |-6  |0   |0   |0   |                |
|45|[pic|25|[pic|[pic|1   |0   |[pic|0   |0   |[pic]           |
|  |]   |  |]   |]   |    |    |]   |    |    |x1 – разрешающая|
|  |    |  |    |    |    |    |    |    |    |переменная      |
|  |    |  |    |    |    |    |    |    |    |[pic]           |
|  |    |  |    |    |    |    |    |    |    |вторая строка – |
|  |    |  |    |    |    |    |    |    |    |разрешающая     |
|  |    |  |    |    |    |    |    |    |    |разрешающий     |
|  |    |  |    |    |    |    |    |    |    |элемент = [pic] |
|0 |[pic|55|[pic|1   |0   |5   |[pic|1   |0   |                |
|  |]   |  |]   |    |    |    |]   |    |    |                |
|0 |[pic|74|3   |[pic|0   |4   |[pic|0   |1   |                |
|  |]   |  |    |]   |    |    |]   |    |    |                |
|  |1125|  |[pic|4   |0   |-6  |[pic|0   |0   |                |
|  |    |  |]   |    |    |    |]   |    |    |                |
|45|[pic|14|0   |[pic|1   |-1  |[pic|[pic|0   |Все [pic]       |
|  |]   |  |    |]   |    |    |]   |]   |    |                |
|30|[pic|22|1   |[pic|0   |2   |[pic|[pic|0   |                |
|  |]   |  |    |]   |    |    |]   |]   |    |                |
|0 |[pic|8 |0   |[pic|0   |-2  |[pic|[pic|1   |                |
|  |]   |  |    |]   |    |    |]   |]   |    |                |
|  |1290|  |0   |7   |0   |9   |6   |3   |0   |                |

  При  этом  каждый  элемент   симплексной   таблицы   имеет   определенный
экономический смысл. Например, во второй симплексной таблице:

|В столбце [pic]:                                                    |
|[pic]              |Показывает, на сколько следует уменьшить       |
|                   |изготовление изделия третьего вида, если       |
|                   |запланирован выпуск одного изделия первого     |
|                   |вида.                                          |
|[pic]; 3           |Показывают, сколько потребуется сырья второго и|
|                   |третьего вида, при включении в план одного     |
|                   |изделия первого вида.                          |
|Т.е. при включении в план одного изделия первого вида, потребуется  |
|уменьшение выпуска продукции третьего вида на 0.5 единиц, а также   |
|потребуются дополнительные затраты 2.5 единиц сырья второго вида и 3|
|единицы сырья третьего вида, что приведет к увеличению прибыли      |
|предприятия на 7.5 денежных единиц.                                 |
|В столбце [pic]:                                                    |
|[pic];[pic];[pic] |Показывают, что увеличение объема сырья первого |
|                  |вида на единицу позволило бы увеличить выпуск   |
|                  |продукции третьего вида на[pic].                |
|                  |[pic]                                           |
|                  |что одновременно потребовало бы [pic] единицы   |
|                  |сырья второго вида и [pic] единицы сырья        |
|                  |третьего вида.                                  |

  Т.к. в последней строке третьей таблицы 1 нет  ни  одного  отрицательного
относительного оценочного коэффициента, то производственная  программа,  при
которой получаемая пр
12345След.
скачать работу


 Другие рефераты
Наследственные болезни и образ жизни человека
Экологическое предпринимательство
Социальная дискриминация женщин как предмет социологического анализа: постановок проблемы и актуальные направления социальной политики
Передача данных в компьютерных сетях


 

Отправка СМС бесплатно

На правах рекламы


ZERO.kz
 
Модератор сайта RESURS.KZ