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

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

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

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

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

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

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

студента  группы 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.Находим  начальное опорное решение. Начальным  решением будет являться вектор, состоящий из тех переменных, которые входят только в одно  из уравнений системы ограничений  с единичным коэффициентом. Заполняем симплексную таблицу.

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