Решение задач линейного программирования. 2

ФГБОУ ВПО “Псковский государственный университет”

Колледж строительства и экономики

 

 

 

 

 

 

 

 

Предмет «Математические  методы»

 

 

 

 

РЕШЕНИЕ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

 

 

 

 

 

 

Курсовая работа

студента 

 

Руководитель курсовой работы

Васильева Наталья Анатольевна

 

 

 

 

 

 

 

Псков, 2012

 

СОДЕРЖАНИЕ

 

Введение

Задание

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

    1. Математическая модель линейного программирования
    2. Стандартная и каноническая форма задачи линейного программирования
    3. Алгоритм решения задачи линейного программирования симплексным

методом

    1. Решение задачи симплексным методом
    2. Вывод

Глава 2. Транспортная задача линейного программирования 
2.1    Транспортная задача 
2.2   Особенности транспортной задачи с ограничением на пропускную

способность 
2.3   Алгоритм решения транспортной задачи  
2.4   Методы построения начального опорного решения 
2.5   Метод потенциалов 
2.6   Переход от одного опорного решения к другому 
2.7  Решение транспортной задачи 
2.8   Вывод

Заключение

Литература  

ВВЕДЕНИЕ

 

Линейное программирование - один из важнейших разделов математики, изучающий теории и методы решения  определенных задач. Эта математическая дисциплина стала в последние  годы широко применяться в различных  областях экономики, техники и военного дела, где в их развитии не последнюю  роль играет математическое планирование и использование автоматических цифровых вычислительных машин.        Данный раздел науки изучает линейные оптимизационные модели. Иначе говоря, линейное программирование посвящено численному анализу и решению задач, требующих нахождения оптимального значения, т.е. максимума или минимума, некоторой системы показателей в процессе, а состояние его описывает система линейных неравенств.      Впервые термин "линейное программирование" предложил американский экономист Т. Купманс в 1951 году. В 1975 году русский математик Л.В.Канторович и Т. Купманс были удостоены Нобелевской премии по экономическим наукам за свой вклад в теорию оптимального распределения ресурсов. Т. Купманс пропагандировал методы линейного программирования и защищал приоритеты Л.В.Канторовича, открывшего эти методы.   История линейного программирования в США уходит корнями в 1947 год, когда Дж. Данциг написал об этом в своей работе. Л.В.Канторович изучал возможность применения математики к вопросам планирования, на основе чего в 1939 году была опубликована его монография "Математические методы организации и планирования производства".        Важнейшей находкой (открытием) Л.В.Канторовича явилась возможность четко математически сформулировать важнейшие производственные задачи, что позволяет найти количественный подход к данным задачам, а также их решение численными методами. Если бы первые работы Л.В.Канторовича получили в свое время должную оценку, то была бы велика вероятность еще большего продвижения линейного программирования в настоящее время. К сожалению, его работа оставалась в тени как в Советском Союзе, так и за его пределами, и, как отмечает Данциг: " …и за это время линейное программирование стало настоящим искусством."       Оптимальный план любой линейной программы следует автоматически связывать с оптимальными ценами или, согласно Л.В.Канторовичу, с "объективно обусловленными оценками"... Это нагромождение слов имело целью повысить "критикоустойчивость" термина. Суть экономического открытия Л.В.Канторовича заключается во взаимосвязи оптимальных решений 
и оптимальных цен.

ЗАДАНИЕ

 

  1. Составить математическую модель и решить задачу №1 симплексным методом.
  2. Решить методом потенциалов задачу №2 с ограничениями на пропускную способность, составив начальное опорное решение методом «минимальной стоимости».
  3. Оформить курсовую работу в соответствии с имеющимися требованиями.

 

ГЛАВА 1

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

 

    1. Математическая модель линейного программирования

 

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

Математическая модель - это упрощенное описание реальности с помощью математических понятий. Существует два основных класса задач, связанных с математическими моделями: прямые и обратные. В первом случае все параметры модели считаются известными, и нам остается только исследовать её поведение. А во втором какие-то параметры модели неизвестны (например, не могут быть измерены явно), и требуется их найти, сопоставляя поведение реальной системы с её моделью. Ещё одна обратная задача: подобрать параметры модели таким образом, чтобы она удовлетворяла каким-то заданным условиям — такие задачи требуется решать при проектировании систем.

Математическая  модель - это упрощенное описание реальности с помощью математических понятий.

Математическая модель составляется следующим образом:

  1. Выбираем переменные задачи: ими являются величины, полностью характеризующие экономический процесс этой задачи, их обычно записываются в виде вектора.
  2. Составляем систему ограничений задачи – это совокупность уравнений или  неравенств, которой удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других экономических условий.
  3. Находим целевую функцию задачи, которая характеризует качество выполняемой задачи и экстремумы, которые необходимо найти.

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

 

 

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

 

Стандартная форма – это форма, когда при составлении математической модели задачи, получается система ограничений из неравенств и не на все переменные может накладываться условия не отрицательности

Каноническая  форма – это форма где все ограничения задачи являются уравнениями, и все переменные удовлетворяют условию не отрицательности

Приведение к канонической форме:

Z(x)=C1 *x1 +C1 *x1+…+Cm *xn

 

 

 

Если система, содержит неравенства, то от неравенства переходим следующим  образом:

1.   Вводят дополнительные переменные, в левой части неравенств;

2. Если знак неравенства  , то дополнительная переменная берется с коэффициентом «+1»;

3. Если знак неравенства  , то дополнительная переменная берется с коэффициентом «-1»;

В целевую функцию, эти  дополнительные переменные записываются с нулевым коэффициентом.

Если какую либо переменную не наложено условие не отрицательности, её заменяют на разность двух других переменных, каждые из которых не отрицательные xj=x/j - x//j   x/j0, x//j 0

 

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

 

  1. Математическая модель задачи должна иметь каноническую форму. Если она записана в стандартной форме, то её нужно привести к канонической.
  2. Находим начальное опорное решение. Начальным решением является вектор, состоящий только из тех переменных, которая входит только в одно из уравнений системы ограничений с единым коэффициентом. Заполняем  симплексную таблицу.

 

Макет симплексной таблицы.

Все строки 1-го шага, за исключением  строки (индексной строки), заполняют по данным системы ограничений и целевой функции. Индексная строка нужна для проверки решения на оптимальность.

  1. Проверяем начальное опорное решение на оптимальность. Индексная строка находится по формуле :

.

     При решение задачи возможны следующие случаи:

  1. При решение задачи на максимум:

а) все оценки , тогда найденное решение оптимальное;

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

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

2) При решении задачи на минимум:

а) все оценки , тогда найденное решение оптимальное;

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

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

  1. В случае необходимости строям новое опорное решение. Для этого необходимо найти ключевой столбец, ключевую строку ключевой элемент. Ключевой столбец указывает на переменную, которую следует ввести в число базисных переменных для улучшения следующего опорного  решения. Ключевая строка указывает на переменную, которую следует вывести из базисных переменных для улучшения решения. Ключевой элемент нужен для расчёта элемента новой симплексной таблицы, соответствующей улучшенному опорному решению. Их нахождения зависят от цели задачи.
  2. При решении задачи на максимум:

а) ключевым столбцом является столбец соответствующий наименьшей отрицательной оценке в индексной строке;

б) ключевой строкой является строка соответствующая минимальному отношению свободных членов к  положительным коэффициентам ключевого  столбца, т.е. ;

в) ключевым элементом является число, расположенное на пересечении  ключевого столбца и ключевой строки.

2) При решении задачи на минимум:

а) ключевым столбцом является столбец соответствующий наименьшей положительной оценке в индексной строке;

б) ключевой строкой является строка соответствующая максимальному  отношению свободных членов к  положительным коэффициентам ключевого  столбца, т.е. ;

в) ключевым элементом является число, расположенное на пересечении  ключевого столбца и ключевой строки.

  1. Заполняем новую симплексную таблицу.

а) переписываем ключевую строку, разделив её на ключевой элемент;

б) заполняем базисные столбцы;

в) остальные коэффициенты таблицы находим по правилу «прямоугольника».

Правило «прямоугольника» заключается в следующем:

 

            Получаем новое опорное решение.

  1. Возвращаемся к третьему шагу алгоритма.

 

 

 

    1. Решение задачи симплексным методом

 

Условие:              Для кормления скота требуется суточный рацион, обладающий определение питательностью, а именно он должен содержать не более 104 ед. биостимуляторов, равно 414 ед. микроэлементов и не менее 120 ед. кормовых единиц.            Вещества, входящие в рацион, содержатся в комбикормах трех видов I, II, III Известно: в одном килограмме комбикорма I вида содержится 2 ед. биостимуляторов 16 ед. микроэлементов и  4 ед. кормовых элементов; II вида - 4 ед. биостимуляторов, 34 ед. микроэлементов и 8 ед. кормовых элементов; III вида - 8 ед. биостимуляторов, 18 ед. микроэлементов и 6 ед. кормовых элементов.

          Известна калорийность одного килограмма комбикорма I вида 1000 ккал., II вида - 1600 ккал., III вида - 1200 ккал.      Сколько килограмм комбикорма каждого вида нужно взять для составлена суточного рациона наибольшей калорийности.

 

Питательные вещества

Содержание питательных  веществ в кг комбикорма

Минимальная суточная потребность

I

II

III

Биостимуляторы

2

4

8

  

Микроэлементы

        

Кормовые единицы

4

8

6

  

Тысяча ккал

     

max


 

  1. Выбираем переменные – количество комбикорма каждого вида

(в кг), причем

  1. Составляем систему ограничений

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

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

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

  1. Находим целевую функцию задачи, так как цель задачи составление рациона наибольшей калорийности, то

Z(Х)=1+1.6+1.2→max

 

Таким образом, математическая модель имеет вид: составить такой рацион кормления Х=(, удовлетворяющий системе ограничений

 

и условию не отрицательности , при котором целевая функция Z(Х)=+1.6+1.2→max

 

Приводим задачу к каноническому виду.

Для этого введем новые  переменные   и в первое и третье ограничения системы, а также в целевую функцию с нулевыми коэффициентами:

Z(x)=1+1.6+1.2→max

 

 

Строим начальное опорное решение методом Гаусса:


2    4    8    1    0    104


16  24  18   0    0    414   :4

4    8   6    0  -1    120

1  1.6 1.2  0   0     0


2    4    8    1    0    104         


16  24  18   0    0    414              +

1    2  1.5  0  -4    30    *(-2)


1  1.6 1.2  0   0     0


0    0    5    1    8    44


          16  24  18   0    0    414                 +


1    2  1.5  0  -4    30    *(-16)

1  1.6 1.2  0   0     0

0    0    5    1    8    44


          0   -8  -6    0  64   -66                

1    2  1.5  0  -4    30    *(-1)     +


1  1.6 1.2  0   0     0


 

0    0     5    1    8    44


          0   -8   -6    0  64   -66    :8               

1    2   1.5  0  -4    30   

0 -0.4 -0.3 0   4   -30

 

0    0     5    1    8    44


          0    1  0.75  0   -8   8.25 *(-2)   +


1    2   1.5  0  -4    30   

0 -0.4 -0.3 0   4   -30

 

0    0     5    1    8    44


          0    1  0.75  0   -8   8.25  *0.4


1    0    0    0  12  13.5              +

0 -0.4 -0.3 0   4   -30



0    0     5    1     8   44


          0    1  0.75  0    -8   8.25 

1    0    0    0   12    13.5          

0    0    0    0  0.8  -26.7


 

 

Теперь решаем задачу симплексным методом. Составляем первую симплексную таблицу. Б=(x4;x2;x1)

Б

      

0

0

0

    
           
 

0

  

0

0

5

1

8

  
 

0

  

0

1

  

0

    
 

0

  

1

0

0

0

    
   

0

0

  

0

    

 

 

 

Проверяем решение на оптимальность

 

0=     3=

 

1==0                             4

 

2=5=

 

Так как 5<0, то решение не оптимальное, следовательно, его можно улучшить. Для этого находим новое опорное решение с помощью «правила прямоугольника».

Так как наименьшее отрицательное  значение5=-0.8, то ключевым столбцом является столбец А5; наименьшее значение 5, то ключевой строкой является строка х1. Рассчитываем новые элементы таблицы:

Новый элемент =44-(13.5*8)/12=35

Новый элемент =0-(1*8)/21=2/3

Новый элемент =5-(0*8)/12=5

Новый элемент =8.25-(-8*13.5)/12=17.25

Новый элемент =0-(-8*1)/12=-(2/3)

Новый элемент =0.75-(-8*0)/12=0.75

 

Получаем новую симплексную  таблицу: Б=(x4;x2;x5)

 

Б

      

0

0

0

    
           
 

0

  

0

5

1

0

  
 

0

  

1

  

0

    
     

0

0

0

    
   

0

0

  

0

    

 

          Аналогично проверяем решение на оптимальность.

Так как все , то решение оптимальное, следовательно, наибольшее значение Z(Х)=27.6, если x1=0, x2=17.25, x3=0, x4=35, x5=1.125.

 

Ответ: максимальное  значение Z(Х)=27.6 при Х=(0; 17.25; 0)

 

    1. Вывод

 

Можно составить рацион кормления  наибольшей калорийности в размере 27.6 тыс. ккал., если купить только 17.25 кг комбикорма второго вида. При этом суточный рацион содержит ровно 414 единиц микроэлементов, 104 единицы биостимуляторов и 120 кормовых единиц.

 

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

 

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

 
  Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из А1,А2…Аm пунктов отправления в В1,В2…Вn пунктов назначения. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Известно Cij( i=) – стоимость перевозки единиц груза от i-поставщика, j- потребителю, или время, необходимое на перевозку единицы груза. Требуется составить такой план перевозок, при котором:

1. Все запасы поставщика  будут вывезены полностью.

2. Все запросы потребителя  удовлетворены полностью.

3. Суммарные затраты на  перевозку груза минимальны.

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

Условие транспортной задачи задается в виде таблицы:

 

1.Выбираем переменные задачи.

Пусть хij () – количество единиц груза, перевозимое от i-го поставщика j-му потребителю, причем хij .

2.Составляем систему ограничений.

Система будет состоять из уравнений, так как:

а) все запасы поставщиков  должны быть вывезены полностью

 

б) все запросы потребителей должны быть удовлетворены полностью

 

3.Задаем целевую функцию.

Цель задачи осуществить  перевозки с минимальными затратами, поэтому

Z(x) = с1*x1 + с1*x1 + … + сm*xn .

 

Таким образом, математическая модель имеет вид:

 составить план перевозки Х = , удовлетворяющий системе ограничений  ,хij ( ), обеспечивающий минимум целевой функции Z(x) =.

 

Транспортные задачи делятся  на два класса:

1. Задачи закрытого типа или с правильным балансом  .

2. Задачи открытого типа или с неправильным балансом  делятся на две группы:

а) общие запасы , для разрешимости задачи, вводят фиктивного потребителя с запросами стоимость перевозок от каждого поставщика фиктивному потребителю = 0.

б) если же запас товара меньше запросов, вводят фиктивного поставщика стоимость перевозок от  фиктивного поставщика потребителю = 0.

 

2.2  Особенности  транспортной задачи с ограничением  на пропускную

       способность

 

Пусть требуется при решении  транспортной задачи ограничить перевозки  от поставщика с номером l и потребителю с номером k. Возможны ограничения двух типов: 1)xlk≥a; 2)xlk≤b, где a и b- постоянные величины.

  1. Если xlk≥ a, то необходимо прежде, чем решать задачу, сократить (уменьшить) запасы l-го поставщика и запросы k-го потребителя на величину a (зарезервировать перевозку xlk=а). В полученном оптимальном решении следует увеличить объем перевозки xlk на величину а.
  2. Если xlk≤b, то необходимо вместо k-го потребителя с запросами bk ввести двух других потребителей. Один из них с номером k должен иметь запросы b,k=b, а другой с номером n+1- запросы bn+1=bk-b. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости cl(n+1), которая принимается равной сколь угодно большому числу M (M<< 1). После получения оптимального решения величины грузов, перевозимых к (n+1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как cl(n+1)=M- самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l,n+1) останется пустой (xl(n+1)=0) и объем перевозки xlk не превзойдет b.

 
      

2.3  Алгоритм  решения транспортной задачи

 

1. Проверяют выполнение  необходимого и достаточного  условия разрешимости задачи. Если  задача имеет неправильный баланс, то вводят фиктивного поставщика  или потребителя с недостающими  запасами или запросами и нулевыми  стоимостями перевозок.

2. Строят начальное опорное  решение (методом минимальной  стоимости или каким-либо другим  методом) и проверяют правильность  его построения, для чего подсчитывают  количество занятых клеток (их  должно быть m+n-1) и убеждаются  в линейной независимости векторов-условий  (методом вычеркивания).

3. Проверяют решение на оптимальность методом потенциалов.

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

4.Если решение неоптимальное, переходят к новому опорному решению, с помощью построения цикла и возвращаются к пункту 3.

2.4 Методы построения  начального опорного решения

 
  Существует ряд методов построения начального опорного решения, наиболее простым из которых является метод северо-западного угла.

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

Заполнение таблицы транспортной задачи начинается с левого верхнего угла, поэтому и называется метод  северо-западного угла.

Метод состоит из ряда однотипных шагов, на каждом из которых, исходя из запасов очередного поставщика и  запросов очередного потребителя, заполняется  только одна клетка и соответственно исключается из рассмотрения один поставщик  или один потребитель.

Распределение груза начинается с верхней левой клетки таблицы. В неё ставится груз величиной  х11=min{a1;b1} при этом из дальнейшего рассмотрения исключается или поставщик или потребитель. Затем, из оставшихся клеток таблицы, выбираем верхнею левую клетку, в которую записывают груз величиной:

хij = min

 и так далее до тех пор, пока весь груз не будет распределён.

Примечание: за один шаг построения решения, можно исключить одного поставщика или одного потребителя  если одновременно исключается и  поставщик и потребитель, то для  разрешения задачи надо поставить нулевую  перевозку или исключить поставщика или потребителя. 

Метод минимальной стоимости прост и позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи C=(cij).

Как и метод северо-западного  угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется  только одна клетка таблицы, соответствующая  минимальной стоимости:

и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую , заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы груза использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь затем поставщик исключается из рассмотрения. Аналогично с потребителем.