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

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

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

 

 

 

 

 

 

 

 

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

 

 

 

 

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

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

 

 

 

 

 

 

 

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

студента 

 

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

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

 

 

 

 

 

 

 

Псков, 2012

 

СОДЕРЖАНИЕ

 

Введение

Задание

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

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

методом

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

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

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

 

 

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

 

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

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

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

Z(x)=C₁ *x₁ +C₁ *x₁+…+C_m *x_n

 

 

 

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

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

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

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

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

Если какую либо переменную не наложено условие не отрицательности, её заменяют на разность двух других переменных, каждые из которых не отрицательные x_j=x^/_j - x^//_j   x^/_j0, x^//_{j 0}

 

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

 

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

 

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

 

 

 

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

 

Условие:              Для кормления скота требуется суточный рацион, обладающий определение питательностью, а именно он должен содержать не более 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. Выбираем переменные – количество комбикорма каждого вида

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

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

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