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

Министерство  образования и науки Российской Федерации

ФГОУ  СПО «Псковский колледж строительства  и экономики» 
 
 
 
 
 
 
 
 
 
 
 
 

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

Решение задач

линейного программирования 
 
 
 
 
 

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

студента  группы 320-ПО

Хруцкого  Максима Игоревича

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

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

Псков, 2011

Содержание 

Введение 

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

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

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

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

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

1.5 Вывод 

Глава 2 Транспортная задача линейного программирования

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

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

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

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

2.5 Метод потенциалов

2.6 Переход от первого опорного решения к другому

2.7 Решение транспортной задачи

2.8 Вывод 

Заключение  

Литература 
 
 
 
 
 
 
 
 
 
 
 

Введение 

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

     Линейное  программирование - один из первых и  наиболее  подробно изученных  разделов  математического   программирования.   Именно   линейное программирование явилось тем разделом, с которого  начала  развиваться  сама дисциплина «математическое программирование».  Термин  «программирование»  в названии  дисциплины  ничего  общего  с  термином  «программирование   (т.е. составление программ) для  ЭВМ»  не  имеет,  так  как  дисциплина  «линейное программирование» возникла еще до  того  времени,  когда  ЭВМ  стали  широко применяться при решении  математических,  инженерных,  экономических  и  др. задач. Термин «линейное  программирование»  возник  в  результате  неточного перевода  английского  «linear  programming».   Одно   из   значений   слова «programming» - составление планов, планирование. Следовательно,  правильным переводом «linear programming» было бы  не  «линейное  программирование»,  а

«линейное планирование», что более  точно  отражает  содержание  дисциплины.

      Однако, термин  линейное  программирование,  нелинейное  программирование  и т.д. в нашей литературе стали общепринятыми.

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

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

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

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

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

линейного программирования 

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

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

    Составление математической модели включает:

• выбор переменных задачи;
• составление системы ограничений;
• выбор целевой функции.

     Общая формулировка задачи использования ресурсов или планирования производства:

Для изготовления n-видов продукции P₁;P₂;…;Pn используется m-видов сырья (ресурсов) S₁; S₂; …; S_m. Расход ресурсов на единицу каждого вида продукции известен a (i = 1, 2, …, m; j = 1, 2, …, n). Также известна прибыль от реализации продукции каждого вида C₁; C₂; …; C_n. Требуется составить план выпуска продукции обеспечивающий максимальную выгоду.

Составим  математическую модель этой задачи:

1. Выбираем переменные задачи: пусть х₁; х₂; …; x_n – это количество продукции каждого вида, причем х_j ≥ 0.
2. Составляем систему ограничений задачи: ограничения задачи связаны с ресурсами имеющимся в наличии, поэтому система будет содержать m-ограничений по каждому ресурсу.

S₁:a₁₁x₁+a₁₂x₂+…+a_1nx_n≤ b₁

“≤” ставится, т.к мы не можем израсходовать ресурсов больше, чем имеется в наличии, следовательно, аналогично и для остальных ресурсов.

S₂:a₂₁x₁+a₂₂x₂+…+a_mnx_n≤b

S_m: a_m1x₁+a_m2x₂+…+a_mnx_n≤b_m

3. Целевая функция.

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

Z(x)=c1x₁+c₂x₂+…+c_nx_n      max

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

найти такой план  X=(х₁, х₂, ..., х_n) выпуска продукции удовлетворяющий системе ограничений :

и условию  неотрицательности х_j ≥ 0, при котором целевая функция

Z(x)=c1x₁+c₂x₂+…+c_nx_n      max

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

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

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

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

Z(x)= c₁x₁+c₂x₂+…+c_nc_n   extrem

a₁₁x₁+…+a_1nxn=b₁

  -   -   -   -  -  -

a_m1x₁+…+a_mnx_n=b_m 

xj 0  (j=1n) 

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

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

• если знак неравенства “≤”, то переменная берется с коэффициентом “+1”;
• если знак “≥”, то дополнительная переменная “-1”.

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

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

1.3. Алгоритм симплексного метода

1.Математическая  модель задачи должна иметь  каноническую форму. Если она записана в стандартной форме, то ее нужно привести к канонической.

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

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

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

Проверяем начальное опорное решение на оптимальность. Индексная строка находится  по формуле Δ_к =∑С_бА_j-с_j. При решении задачи возможны следующие случаи:

1) при решении задачи на максимум:

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

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

в) хотя бы одна оценка   Δк < 0   и при соответствующей переменной есть  хотя бы  один

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

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

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

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

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

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

столбца, т.е.

тiп Θ =                                  A₀

             {положит.эл.кл.столбца} 

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

5.Заполняем  следующую симплексную таблицу.

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

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

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

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

                                  соотв.эл.кл.столбца х соотв.эл.кл.строки

новый эл.=старый эл

                                              ключевойэлемент

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

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

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

      Предприятие изготавливает три вида станков I, II, III. При этом расходуются сырье, трудовые ресурсы и учитываются накладные расходы.

      Известно, что для изготовления станка I-го вида требуется по1 ед. сырья, трудовых ресурсов и накладных расходов; для станка II-го вида – 2 ед. сырья, 1 ед. трудовых ресурсов и 2 ед. накладных расходов; для станка III-го вида – 3 ед. сырья, 1 ед. трудовых ресурсов и 6 ед. накладных расходов. Предприятие может обеспечить 15 ед. сырья, 12 ед. трудовых ресурсов и 14 ед. накладных расходов. Прибыль от реализации станка I вида 5 тыс. руб., II вида – 9 тыс. руб., III вида – 8 тыс.руб.

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

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

Запишем условие задачи в виде таблицы: 

Составляем математическую модель задачи.

Вводим  переменные:

Пусть x₁; x₂; x₃ – количество станков каждого вида, причем х₁ ≥ 0, х₂ ≥ 0, х₃ ≥ 0.

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

S₁:1х₁+2х + 3х3≤15

Знак  “≤” ставим потому, что мы не можем использовать ресурсов больше, чем имеется в наличии.

S₂:1х₁+1х₂+1х₃=12

Знак  “=” ставим потому, что условие задачи требует, чтобы трудовые ресурсы были использованы полностью.

 S₃:1х₁+2х₂+6х₃≥14

Знак  “≥” ставим потому, что условие задачи требует, чтобы накладные расходы были не менее указанных.

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

Z(x)=5x₁+9x₂+8x₃ max

      Таким образом, математическая модель этой задачи имеет вид: найти такой план X=(х₁, х₂, ...,х_n) производства станков, удовлетворяющий стстеме ограничений:

хj≥0 (j=1,2,3), при  Z(x)=5x₁+9x₂+8x₃       max 

Приводим  задачу к канонической форме. Для  этого в систему ограничений  вводим дополнительные переменные, чтобы  уравнять правые и левые части: +x₄; -x₅. В целевую функцию дополнительные переменные входят с нулевыми коэффициентами.

Таким образом, каноническая форма задачи:

Z(x)=5x1+9x2+8x3+0x4+0x5  max

хj>=0 (j=1,2,3); 

 Z(x)=5x1+9x2+8x3+0x4+0x5        max

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

хj>=0 (j=1,2,3); 

 Z(x)=5x1+9x2+8x3+0x4+0x5         max 

+  

 
Домножим вторую строку матрицы  на (-1) и сложим ее с первой, а потом  с третьей.  В результате получим: 

+   

Домножим  вторую строку на (-5) и сложим ее со строкой  под чертой. В результате получим  : 

 +    
 

Домножим  третью строку на (-1) и сложим ее с первой, а потом со второй. В результате получим: 

+ 

Домножим  третью строку на -4 и сложим ее со строкой  под чертой. В результате получим  матрицу:

x1  x2    x3  x4   x5

0   0   -3   1   1    1  

1   0   -4   0   1    10

0   1    5   0   -1    2

0   0  -17  0    4    -68 

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

Проверяем решение на оптимальность, для этого вычисляем ∆_k: 

∆₀=   × -(-68)=68

∆₁=   × -0=0

∆₂ = × -0=0

∆₃= × -(-17)=17

  ∆₄= × - 0 = 0

 ∆₅= × -4=-4