На бирже курсовых и дипломных проектов можно найти образцы готовых работ или получить помощь в написании уникальных курсовых работ, дипломов, лабораторных работ, контрольных работ, диссертаций, рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Лекции Математическое программирование

Информация:

Тип работы: Лекции. Добавлен: 06.06.2012. Сдан: 2011. Страниц: 20. Уникальность по antiplagiat.ru: < 30%

Описание (план):


МАТЕМАТИЧЕСКОЕ  ПРОГРАММИРОВАНИЕ 

1. Задачи оптимизации при ограничениях–неравенствах. 

     Математическое  программирование представляет собой  математическую дисциплину, которая  занимается изучением экстремальных  задач и разработкой методов  их решения.
     В общем виде математическая постановка экстремальной задачи состоит в определении наибольшего или наименьшего значения целевой функции F1, х2, …, хn) при условиях
     gi1, х2, …, хn)?b, i=1, 2, ..., m. 

     F1, х2, …, хn)>max
       

     где F(х1, х2, …, хn), gi – некоторые заданные функции,
     bi – некоторые действительные числа. 

     Если  все функции gi и F являются линейными относительно (х1, х2, …, хn), то соответствующая задача называется задачей линейного программирования (ЗЛП).
     Если  хотя бы одна из функций gi или F является нелинейной функцией относительно переменной, то задачи называются задачами нелинейного программирования.
     Функция, максимум или минимум которой  надо найти называется функцией цели.
     Система уравнений или неравенств gi называется системой ограничений задачи.
     Решением задач линейного программирования называется набор переменных, удовлетворяющих системе ограничений, при котором функция цели достигает экстремального значения.
      - эта совокупность называется  оптимальным планом.
     Совокупность переменных, удовлетворяющих системе ограничений, при котором функция цели F?Fmax, называется опорным (допустимым или промежуточным) планом.
     Рассмотрим  три формы задач линейного  программирования.
     1. Общей задачей линейного программирования называется задача определения экстремального значения цели, при условии, что в систему ограничений входят как неравенства, так и равенства.
     
     2. Стандартной (симметричной) называется задача линейного программирования, в которой находится оптимальное значение функции цели при условии, что система ограничений состоит из неравенств.
     
       
     3. Канонической (основной) задачей линейного программирования называется задача отыскания максимального значения функции F, при условии, что система ограничений состоит только из равенств.
     
     
     Эти три формы задачи эквивалентны, т.е. с помощью несложных преобразований возможен переход от одной к другой. 

     2. Экономические примеры  задач линейного  программирования. 

     1. Задачи планирования производства.
     Пусть предприятию необходимо спланировать производственную деятельность на некоторый  период времени. Известны виды и количества ресурсов, которыми оно располагает, и перечень товаров, которые оно может производить без дополнительных капиталовложений. Известна также структура затрат и доходов, т.е. коэффициенты удельных затрат на единицу каждого вида товара, а также прибыль от реализации одного изделия каждого вида. Пусть предприятие будет выпускать n различных товаров и имеет m видов ресурсов.
     Введем  обозначения:
     aij – расход i–го ресурса на производство j–го товара
     cj – прибыль, полученная от реализации единицы продукции j–го вида
      - план производства, где xj - количество продукции j–го вида, предусмотренное планом (j=1,2,...,n);
     cjxj – прибыль, получаемая при выпуске xj единиц продукции.
     Общая прибыль предприятия от реализации всех видов продукции может быть выражена суммой таких произведений:
     
     и является функцией цели данной задачи.
     aijxj – количество ресурса j-го вида, затраченного на производство продукции j-го вида в количестве xj.
     Суммарный расход i–го ресурса на производство всех видов продукции не должен превышать суммарный запас этого ресурса.
     
     Т.к. переменные xi- это количество выпускаемой продукции, то должно выполняться условие неотрицательности переменных.
     В результате получаем следующую математическую модель задачи:
     
                                (1) 
 
 

     Задача  о диете. 

     Требуется выделить самый дешевый пищевой рацион, содержащий необходимое количество указанных заранее питательных веществ.
     Известен  перечень биологических питательных веществ и их минимальная суточная норма, задан набор продуктов, из которых можно составить рацион питания.
     Имеются нормы содержания питательных веществ  в единице каждого продукта, известна цена каждого продукта. Допустим можно  использовать n видов продуктов, содержащих m различных питательных веществ.
     Введем  обозначения:
     bi – суточная норма i-го питательного вещества;
     aij – содержание i-го питательного вещества в единице j-го продукта;
     cj – стоимость единицы j-го продукта;
      - общий рацион.
     Функция цели показывает общую стоимость  рациона
     
     aijxj – потребление i-го питательного вещества в j-ом продукте.
     Суммарное потребление i–го питательного вещества (во всех продуктах) не должно быть меньше биологической нормы bi.
     
     Т.к. xj – количество продукции каждого вида, то должно выполняться условие неотрицательности переменной. Получим следующую математическую модель задачи:
     
                                 (2) 

     Транспортная  задача. 

     В m пунктах производится однородный продукт ai, i=1,2,...,m, в n пунктах имеется потребность в этом продукте в количестве bj, j=1,2,...,n.
     Известна  стоимость перевозки единицы  продукта из каждого пункта производства в каждый пункт потребления. Предполагается, что суммарное количество выпущенного продукта в точности равно суммарной потребности в нем.
     Требуется составить наиболее дешевый план перевозок от производителей к потребителям, удовлетворяющий следующим условиям:
      От каждого производителя должен быть вывезен весь произведенный продукт.
      Потребность каждого потребителя должна быть полностью удовлетворена.
      Не допускаются встречные перевозки.
     Введем  обозначение матриц перевозок и  тарифов:
      , где X – матрица перевозок
     xij - количество груза, перевезенного от поставщика к потребителю.
     Матрица тарифов:
     
     cij – тариф на перевозку груза от i-го поставщика к j-му потребителю.
     Функция цели выражает полную стоимость перевозок.
     
     Условия:
     
     Имеем следующую математическую модель задачи:
     
     
     
     Модель  задачи, в которой сумма запасов  равна сумме потребностей, называется закрытой. 

     3. Методы решения задач линейного программирования. 

     3.1. Графический метод. 

     Пусть дана математическая модель задачи линейного  программирования в виде (1). Допустимый план задачи можно представить как точку в пространстве Rn. Д – область допустимых планов (Д).
     Множество оптимальных планов образует в пространстве Rn область Д0 – область оптимального планирования.
     Множество точек пространства Rn, координаты которых удовлетворяют линейному уравнению
     
     называется  гиперплоскостью.
     Гиперплоскость делит все пространство на две полуплоскости:
     - положительная Н+:
     - отрицательная Н-:
     Линейные  функции цели в гиперпространстве  соответствуют гиперплоскости.
     Уравнение определяет гиперплоскость, которая называется уровнем функции цели.
     Если  , то говорят о нулевом уровне функции цели.
     Уровень функции цели возрастает в направлении  градиента этой функции или нормали функции цели:
    Область допустимых планов ЗЛП – это область решений системы линейных неравенств, ограниченная выпуклым многогранником.
    Каждая вершина этого многогранника определяет опорный план.
    В одной из вершин многогранника решений значение целевой функции является максимальным при условии, что функция ограничена сверху на множестве планов.
    Если максимальное значение целевая функция принимает более чем в одной вершине, то это же значение она принимает в любой точке, являющейся выпуклой линейной комбинацией данных вершин.
     Задачи  линейного программирования имеют  простую геометрическую интерпретацию, если задача записана в стандартной форме и имеет не более 2-х переменных, или задача записана в канонической форме и содержит не более 2-х свободных переменных.
     Найдем  решение задачи:
     (1)
     (2)
     (3)
     Каждое  из неравенств (2), (3) геометрически определяет полуплоскость с граничными прямыми
     (4) .
     В том случае, если система неравенств (2),(3) совместна, область ее решения есть множество точек, принадлежащих всем указанным плоскостям. Т.к. множество точек пересечения данных полуплоскостей выпуклое, то областью допустимых решений задачи (1)-(3) является выпуклое множество, которое называется многоугольником решений (т.е. область решения – это пересечение данных полуплоскостей), а при m?3 – многогранником решений.
     Стороны этого многогранника лежат на прямых (4).
     Для определения Fmax надо найти вершину многоугольника (многогранника), в которой функция цели максимальная. Для этого строится линия уровня функции цели
     
     Сначала полагаем h=0, т.е. строим нулевой уровень функции цели.
      - прямая линия
     Передвигаем прямую, соответствующую нулевому уровню цели в направлении вектора нормали до тех пор, пока она не пройдет через последнюю ее общую точку с многоугольником решений.
     Координаты  этой точки и есть решение задачи, т.е. ее оптимальный план.
     При этом возможны следующие 4 случая:
       
 
 
 

     При нахождении минимального значения функции  цели линия нулевого уровня передвигается  в направлении, противоположном  направлению вектора  .
     Итак, графический метод решения задач линейного программирования состоит из следующих этапов:
      для каждого неравенства строят граничные прямые и выбирают полуплоскость, соответствующую данному неравенству;
      находят область допустимых планов, как область пересечения полуплоскостей (многоугольник решений);
      строят нулевой уровень функции цели;
      строят вектор-градиент функции цели (или вектор-нормаль);
      параллельным переносом перемещают уровень функции цели в направлении вектора-нормали (при поиске максимального значения) до тех пор, пока он не окажется в крайней точке области допустимых планов;
      координаты этой точки (множества точек) и есть оптимальный план ЗЛП (координаты точек находят, решая систему уравнений прямых, на пересечении которых они находятся). .
    Пример 1.:
                         

    Пример 2.
                         

    3.2. Симплексный метод решения задач линейного программирования. 

      Идея  симплексного метода решения ЗЛП состоит в переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план, и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план.
      Пусть требуется найти максимальное значение функции


    Запишем эту  задачу в канонической форме:


Таким образом, мы перешли к рассмотрению задачи линейного программирования в пространстве Rn+m.
Такая система m уравнений с (n+m) неизвестными имеет бесконечное множество решений. Пусть переменные W1,...,Wm – базисные.
Полагая свободные переменные равными нулю, получим первое базисное решение. Чтобы перейти к другому базисному решению, надо поменять ролями одну свободную и одну базисную переменные. Опорный план ЗЛП является одним из базисных решений системы уравнений-ограничений.

    Первый допустимый (опорный) план задачи:
      
      Переход от одного базисного решения к  другому реализуется с помощью  метода модифицированных жордановых исключений (МЖИ), что удобнее делать в виде симплексных таблиц. 

Б\С 1
2
-xn b С/о
W1 W2
?
?
?
Wm
a11
a21
?
?
?
am1
a12 a22
?
?
?
am2
... ...
?
?
?
...
a1n a2n
?
?
?
amn
b1 b2
?
?
?
bm
b1/a12 b2/a22
?
?
?
b2/a22
F -c1 -c2 ... -cn    
 
      Решение осуществляется по следующей схеме:
    В строке F выбирают самый большой по модулю отрицательный элемент. Столбец, в котором он стоит, будет разрешающим.
    Для элементов разрешающего столбца находят симплексное отношение (не отрицательное отношение элементов столбца свободных членов b к элементам разрешающего столбца).
    Разрешающая строка будет соответствовать наименьшему симплексному отношению.
    На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент. (В данном случае это                  , ему соответствуют базисная переменная W1 и свободная переменная x2.)
    Составляем новую симплекс-таблицу, меняя местами x2 и W1.
    Разрешающий элемент в новой таблице заменяем на обратную величину a12>1/a12.
    Элементы разрешающей строки делятся на разрешающий элемент.
    Элементы разрешающего столбца делим на разрешающий элемент с противоположным знаком.
    Остальные элементы таблицы пересчитываем по правилу прямоугольника. 
     

Б\С 1
-W1
-xn b С/о
x2 W2
?
?
?
Wm
a11/a12
a21
?
?
?
am1
1/a12 -a22/a12
?
?
?
-am2/a12
... ...
?
?
?
...
a1n/a12 a2n
?
?
?
amn
b1/a12 b2
?
?
?
bm
 
F -c1 -c2/a12 ... -cn    
 
    Процедура повторяется до тех пор, пока все  элементы строки F станут неотрицательными.
 
    Оптимальный план задачи – это базисное решение, при котором все элементы строки F положительны, а оптимальное значение функции цели записано в клетке таблицы на пересечении строки F и столбца b.
    Если  при решении ЗЛП все симплексные  отношения получились отрицательные, то функция цели не ограничена на области  допустимых (опорных) планов. 

    Пример: 

    Для производства 2-х видов продукции  П1 иП2 предприятие расходует два вида ресурсов Р1 и Р2. Расход каждого вида ресурса на единицу продукции каждого вида, запасы ресурсов и прибыль от реализации единицы продукции каждого вида приведена в таблице 

Виды  ресурсов Виды  продукции Запасы  ресурсов
П1 П2
Р1 Р2
1 2
5 1
15 12
Прибыль от реализации единицы продукции 6/5 3/2  
 
    Математическая  модель задачи:
    L1:
    S1:
    Математическая формулировка ЗЛП: найти такие значения переменных х1 и х2, удовлетворяющих системе ограничений S1, которые максимизируют функцию цели F.
    1. Приведем задачу к каноническому  виду, введя дополнительные неотрицательные  переменные w1 и w2.
      

      

    2. Разрешим систему ограничений  задачи относительно w1 и w2:
    
     , где w1, w2 – базисные переменные; х1, х2 – свободные. 

    Запишем задачу в виде симплекс-таблицы:
    Т.1.
    Б\С 1 2 b с/о
     
    W1 W2
     
    1 2
    5
    1
     
    15 12
     
    2
    12
    F -6/5 -3/2 0  
                                                #
     - опорный план
    F=0
    w1, w2 – остатки ресурсов 

    Т.2.
    Б\С 1 - W1 b с/о
    х2 
    W2
    1/5
    1/5 
    -1/5
    3 
    9
    15 
    5

    F -9/10 3/10 9/2  
                             #
    
    F2=9/2 

    Т.3.
    Б\С - W2 - W1 b
    х2 х1
    -1/9 5/9
    2/9 -1/9
    2 5
    F 1/2 1/5 9
 
    
    F3=9 > Fmax
     - оптимальный план. 

    Итак, в смысле разрешимости канонических задач  строится конечная последовательность опорных планов системы ограничений такая, что на каждом последующем опорном плане значение целевой функции не меньше, чем на предыдущем. Тогда через конечное число шагов найдется оптимальный план задачи (включая случаи вырождения).
    Таким образом, симплекс-метод позволяет не только решить каноническую задачу , но и получить оптимальный план задачи об оптимальном планировании производства. Кроме того, каждый опорный план системы ограничений задачи содержит дополнительную экономическую информацию об остатках ресурсов при реализации соответствующего допустимого плана задачи .
    При решении задачи отыскания минимума функции цели, когда все элементы в строке F симплексной неотрицательные, изменяется правило выбора разрешающего столбца: столбец выбирается по наибольшему положительному коэффициенту в строке F. Разрешающая строка выбирается так же.
    План  задачи на минимум функции является оптимальным, когда в строке F все элементы не положительны.
    Рассмотрим  случай, когда в столбце свободных  членов есть отрицательные элементы. (bi<0).
    Если  среди свободных членов системы  ограничений имеется хотя бы один отрицательный элемент bi<0, то соответствующая базисная переменная в базисном решении не удовлетворяет условию неотрицательности. Поэтому надо сначала получить первый опорный план задачи.
    При этом необходимо руководствоваться  следующим правилом выбора разрешающего элемента:
    - выбирают любую строку с отрицательным свободным членом;
    - если среди элементов этой  строки нет отрицательных, то  система ограничений несовместна;
    - если среди элементов этой  строки есть отрицательные, то  выбирают любой из них, и  столбец, в котором он стоит,  будет разрешающим;
    - разрешающая строка выбирается по наименьшему симплексному отношению. 

    Пример:
    
                              
    
    Б\С - х1 - х2 b с/о
    W1 W2
    W3
    1
    -1
    2
    2 -2
    1
    10 -2
    10
    10 2
    5
    F -1 -1
     
                            #
     - 1-е базисное решение, не  является допустимым планом, т.к.  W2=-2<0 

    Б\С - W2 - х2 b с/о
    W1 х1
    W3
    1 -1
    2

    0 2
    -3
    8 2
    6
    8 -
    3

    F -1 1 2  
                            #
    
    F2=2
    Б\С - W3 - х2 b с/о
    W1 х1
    W2
    -1/2 1/2
    1/2
    3/2
    1/2
    -3/2
    5 5
    3
    10/3
    10/2
    3
    F 1/2 -1/2 5  
                                               #
    
    F3=5
    Б\С - W3 - W1 b
    х2 х1
    W2
    -1/3 3/3
    0
    2/3 -1/3
    1
    10/3 10/3
    8
    F 1/3 1/3 20/3
 
    
    Fmax=
    4. Двойственные задачи линейного программирования. 

    Каждой  задаче линейного программирования можно определенным образом сопоставить другую задачу линейного программирования, называемую двойственной или сопряженной. Например, задача планирования производства – прямая, а задача оценивания ресурсов – двойственная.
    4.1. Постановка двойственной задачи об оценивании ресурсов.
    Предположим, что предприятие, не желающее выпускать продукцию, продает все ресурсы. Располагая информацией прямой задачи L, определить цены на ресурсы, таким образом, чтобы удовлетворить интересы обеих сторон – продавца и покупателя.
    Составим  математическую модель задачи L1+.
    Пусть y1 и y2 – цены ресурсов R1 и R2. Стоимость ресурса R1, идущего на выпуск единицы продукции 1-го вида П1 – 1y1, а стоимость ресурса R2, также идущего на выпуск единицы продукции 1-го вида П1, - 2y2, общая стоимость ресурсов на выпуск единицы продукции П1 1y1+2y2.
    Общая стоимость ресурсов, идущих на выпуск единицы П2:
    5y1+1y2.
    С точки зрения предприятия-продавца ресурсы выгодно продавать в  том случае, если стоимость ресурсов на единицу продукции не меньше, чем прибыль от реализации их, т.е.:
    
    С точки зрения предприятия-покупателя ресурсы выгодно покупать, если их стоимость окажется наименьшей, т.е.
    15y1+12y2>min
    В результате получаем математическую модель двойственной задачи L+ об оценивании ресурсов:
    T1(y)= 15y1+12y2>min
    
    4.2. Математическая формулировка задачи L1+.
    Найти такие значения переменных y1 и y2, удовлетворяющих системе ограничений S+, при которых функция цели Т(у) принимает наименьшее значение.
    4.3. Общая постановка задачи L1+.
    Дадим определение двойственной задачи по отношению к общей задаче линейного программирования, состоящей в нахождении максимума функции цели.
    (1)
    (2)
    (3)
    Задача, состоящая в нахождении минимального значения функции:
    (4) Т(у)=b1y1+b2y2+...+bmym
    при условиях:
    (5)
    (6)
    называется  двойственной по отношению к задаче (1)-(3).
    Задачи (1)-(3) и (4)-(6) образуют пару задач, которая  называется двойственной парой.
    Двойственная  задача, по отношению к исходной, составляется по следующим правилам:
      Целевая функция исходной задачи (1)-(3) задается на максимум, а двойственной – на минимум.
      Матрица , составленная из коэффициентов при неизвестных в системе ограничений (2) исходной задачи и аналогичная матрица получаются друг из друга транспонированием, т.е. заменой строк столбцами, а столбцов – строками.
      Число переменных в двойственной задаче (4)-(6) равно числу ограничений в системе (2) исходной задачи (1)-(3), а число ограничений в двойственной задаче (5) – числу переменных в исходной задаче.
      Коэффициентами в целевой функции Т(у) (4) L+являются свободные члены в соотношениях (2) задачи L1, а правыми частями в системе ограничений (5) двойственной задачи L1+ являются коэффициенты при неизвестных в целевой функции F(x) исходной задачи (1).
      Если переменная xj в задаче L1 (1)-(3) может принимать только положительные значения (xj?0), то ограничение с таким же номером (j-тое) в системе (5) задачи L1+ (4)-(6) является неравенством вида «?». Если же переменная xj может быть как >0, так и <0, то (j-тое) соотношение в системе ограничений (5) задачи L+ представляет собой равенство.
      Аналогично, если i–тое соотношение в системе ограничений (2) исходной задачи L1 является неравенством, i-тая переменная двойственной задачи yi?0, в противном случае переменная может быть как положительной, так и отрицательной.
    Пример:
      (1)
      (2)                          L1
      (3)
      Cоставить двойственную задачу.
      а) Согласно п.3, число переменных в  двойственной задаче L1+ равно трем (у1, у2, у3), согласно п.4 – целевая функция имеет вид:
      
      б) Согласно п.1 необходимо найти минимум  этой функции
      в) Матрица коэффициентов задачи L1
      а матрица коэффициентов задачи L1+
      г) Согласно п.5, т.к. все переменные исходной задачи L1 , система ограничений задачи L1+ имеет вид
      
     д) Согласно п.5, т.к. все три ограничения  в системе (2) исходной задачи L1 – равенства, переменные yi в задаче L1+ могут быть как больше нуля, так и меньше нуля (т.е. ).
     Итак, математическая модель двойственной задачи L1+ имеет вид:
              (4)

                               (5)
                   (6) 

5. Связь между решениями прямой и двойственной задач. 

     Каждая  из двойственной пары задач (1)-(6) и (4)-(6) может быть решена самостоятельно. Но при решении симплекс-методом можно получить оптимальное решение обеих задач.
     Зависимость между решениями L1 и L1+ характеризуется следующими леммами и теоремами. 

     Лемма 1. Если Х – некоторый план задачи L1 (1)-(3)? а У – произвольный план задачи L1+ (4)-(6), то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане У.
     

     Лемма 2. Если для некоторых планов Х0 и У0 исходной и двойственной задач, то Х0 – оптимальный план задачи L1+, У0 – оптимальный план задачи L1. 

     Теорема (Первая теорема двойственности).
     а) Если одна из пары двух задач (1)-(3) или (4)-(6) имеет оптимальный план, то и другая имеет оптимальный план. Причем .
     б) Если целевая функция одной из двойственных задач не ограничена (для  задач (1)-(3) сверху, а для задач (4)-(6) снизу), то другая задача не имеет планов. 

     Теорема (Вторая теорема двойственности).
     а) Если оптимальный план Х0 задачи L1 обращает i-е ограничение системы S1 (2) в строгое неравенство, то соответствующая ему переменная уi в оптимальном плане У двойственной задачи L1+ обращается в 0.
     б) Если в оптимальном плане Х0 задачи L1 переменная хi>0 (положительна), то соответствующее ей ограничение задачи  на ее оптимальном плане У0 обращается в верное равенство. 

      Целочисленные задачи линейного  программирования.
 
     Определение. Экстремальная задача, переменные которой  принимают лишь целочисленные значения, называется задачей целочисленного программирования.
     В математической модели задачи целочисленного программирования как целевая функция, так и функции системы ограничений могут быть линейными, нелинейными, смешанными.
     Рассмотрим  случай, когда функция цели и функции системы ограничений задачи являются линейными. 

     Задача. В цехе решено установить дополнительное оборудование, для которого выделено 19/3 кв.м площади. На приобретение оборудования двух типов предприятие может выделить 10 тысяч рублей.
     Комплект  оборудования 1-го типа стоит 1000 рублей, 2-го типа – 3000 рублей.
     Приобретение  одного комплекта оборудования 1-го типа позволит увеличить выпуск продукции  на 2 единицы в смену, 2-го типа –  на 4 единицы в смену.
     Для установки оборудования 1-го типа необходимо 2 кв.м площади, 2-го типа – 1 кв.м площади.
     Определить  какой набор дополнительного  оборудования даст возможность максимально  увеличить выпуск продукции. 

     Решение. Составим математическую модель задачи. Пусть предприятие приобретет Х1 комплектов оборудования 1-го типа, Х2 – 2-го типа.
     Тогда                  (1)
                                    (2) общее увеличение выпуска продукции
                                     (3) экономическое содержание переменных
      - целые,                             (4) 

     Математическая  постановка задачи: найти максимальное значение функции (2) при выполнении условий (1), (3), (4). Т.к. х1, х2 могут быть только целыми, то это задача целочисленного программирования.
     Решим задачу геометрическим способом:
                                                                                                                                                    
     Многоугольник ОАВС – многоугольник решений, т.к. координаты всех его точек удовлетворяют условиям (1), (3). А условию целочисленности удовлетворяют только 12 точек.
     Многоугольник OKEMNF – координаты всех его точек удовлетворяют условиям (4) целочисленности х1, х2. Максимальное значение функции цели Fmax(1;3)=2*1+4*3=14/
     Координаты  точки Е определяют оптимальный  план задачи. Таким образом, предприятию следует дополнительно приобрести 1 комплект оборудования 1-го типа, и 3 комплекта оборудования 2-го типа, что обеспечит при ограниченных производственных площадях и денежных средствах максимальное увеличение выпуска продукции, равное 14 единиц в смену. 
 
 

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

     В общем виде задачу можно записать следующим образом:
     Найти максимум функции
                                          (6)
     при условиях
                     (7)
                               (8)
      - целые                                       (9) 

     6.2 Метод Гомори.
     Задача.
     Найти максимальное значение функции  (1)
     При условиях           (2)
                                         (3)
                                  (4) 

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

    Базис b X1 X2 X3 X4 X5 с/о
    X3 13 1 1 1 0 0 13
    Х4 6 1 -1 0 1 0 6
    Х5 9 -3 1 0 0 1 -
    F 0 -3 -2 0 0 0  
    X3 7 0 2 1 -1 0 3,5
    Х1 6 1 -1 0 1 0  
    Х5 27 0 -2 0 3 1  
    F 18 0 -5 0 3 0  
    X2 7/2 0 1 1/2 -1/2 0  
    Х1 14/2 1 0 1/2 ? 0  
    Х5 34 0 0 1 2 1  
    F 71/2 0 0 5/2 1/2 0  
 
     Найден  оптимальный план X(19/2, 7/2, 0, 0, 34) задачи (1)-(3), но он не является оптимальным планом целочисленного программирования (1)-(4), т.к. переменные х1 и х2 – не являются целыми значениями. Дробные части их равны, поэтому для одной из них составляется дополнительное ограничение. Составим ограничение для переменной х2.
     Из  последней таблицы
     
     Откуда  следует дополнительное условие
     
     где f – положительные дробные части чисел после отбрасывания целой части ?
                              (5)
     Найдем  максимальное значение функции (1) при  условиях (2), (3), (5). 

Базис b X1 X2 X3 X4 X5 X6 с/о
X2 7/2 0 1 ? -1/2 0 0  
X1 19/2 1 0 ? ? 0 0  
X5 34 0 0 1 2 1 0 17
X6 -1 0 0 -1 -1 0 1  
F 71/2 0 0 5/2 1/2 0 0  
X2 4 0 1 1 0 0 -1/2  
X1 9 1 0 0 0 0 ?  
X5 32 0 0 -1 0 1 2  
X4 1 0 0 1 1 0 -1  
F 35 0 0 2 0 0 1/2  
 
     Выбирается  наименьшее по абсолютной величине отношение  элементов строки F к элементам разрешающей строки.
     X0(9;4;0;1;32)
     F0max=35
     Решим задачу геометрически 

     
     Xc(19/2,7/2,0,0,34)
     Многоугльник  ОАВСД – многоугольник решений  задачи (1)-(3). Максимум достигается в  точке С(19/2, 7/2). Для задач (1)-(4) вводится дополнительное ограничение  .
     Найдем  x3 из первого ограничения
     Из  второго ограничения найдем х4:
     
     XE(9, 4, 0, 1, 32) 

     Таким образом область допустимых решений  – многоугольник OABEFD. В точке Е(9;4) этого многоугольника целевая функция достигает максимального значения. Т.к. координаты точки Е целые и неизвестные x3, x4, x5 принимают целочисленные значения при подстановке в систему (2), х1=9, х2=4.
     Таким образом Х0(9;4;0;1;32) является оптимальным планом задачи (1)-(4).
     Итак, процесс определения оптимального плана задачи целочисленного программирования методом Гомори включает следующие  этапы:
    Используя симплекс-метод, находят решения задачи (6)-(8) без учета требования целочисленности переменных.
    Составляют дополнительные ограничения для переменной, которая в оптимальном плане задач (6)-(8) имеет максимальную дробную часть числа, а в оптимальном плане задач (6)-(9) эта переменная должна быть целочисленной.
    Используя двойственный симплекс-метод, находим решение задачи, получающейся из задач (6)-(8) в результате присоединения дополнительного ограничения.
    В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационны процесс до получения оптимального плана задачи (6)-(9) или установления ее неразрешимости.
 
7. Транспортная задача. 

7.1 Общая постановка задачи. 

     Транспортная  задача – одна из распространенных задач линейного программирования. Ее цель – разработка наиболее рациональных путей и способов транспортирования  товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это ведет к экономии затрат на перевозку грузов (сокращение времени продвижения товаров, уменьшение затрат предприятий, связанных со снабжением сырьем, материалами, топливом, оборудованием и т.д.).
     В общем виде задачу можно представить  следующим образом: в m пунктах производства А1, А2,    ,Аm имеется однородный груз в количестве соответственно а12,   , аm. Этот груз необходимо доставить в n пунктов назначения B1, B2, …, Bn  b1, в количестве соответственно b2, …, bn. Стоимость перевозки единицы груза (тариф) из пункта Ai в пункт Bj равна cij.
     Требуется составить план перевозок, позволяющий  вывезти все грузы и имеющий минимальную стоимость.
     Математическая  модель задачи выглядит следующим образом:
     Пусть xij – количество груза, перевозимого из пункта Ai в пункт Bi.
     Целевая функция имеет вид:    (1)
при следующих  системах ограничений:
(2)           
(3)              
Определения:
1. Всякое  матричное решение систем (2) и  (3), определяемое матрицей Х(xij), называется планом транспортной задачи.
2. Решение,  при котором функция (1) принимает  минимальное значение, называется  оптимальным планом транспортной задачи.
3. Суммарным  количеством груза у поставщиков  является величина, равная  , суммарная потребность в грузе у потребителей составляет .
4. Если  общая потребность в грузе  равна запасу груза ( = ), то модель такой транспортной задачи называется закрытой. Если это условие не выполняется, то модель задачи называется открытой.
Теорема.
Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т.е чтобы выполнялось условие = .
Обычно  условия транспортной задачи записываются в виде таблицы:

и т.д.................


            Потреб. Постав.
B1 B2 Bn Запасы
A1 c11 c12 c1n a1
x11 x12 x1n
A2 c21 c22 c2n

Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.