Метод искусственного базиса

Министерство образования и культуры Тульской области

 ГОУ СПО ТО «Донской  техникум информатики и вычислительной  техники»

 

 

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

по дисциплине

Математические методы

на тему:

Метод искусственного базиса

 

 

 

 

 

Выполнил: студент группы 3-П-1

Столяров Виктор

Проверила: Попова О.Б.

 

 

 

Донской, 2013

Оглавление

 

 

 

Введение

Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича "Математические методы организации и планирования производства". Поскольку методы, изложенные Л.В.Канторовичем, были мало пригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В.Канторовича осталась почти не замеченной.

Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за "вклад в разработку теории и оптимального использования ресурсов в экономике".

В автобиографии, представленной в Нобелевский комитет, Леонид Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К нему, 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда… Поэтому простой перебор вершин не годился. Леонид Витальевич писал: "оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения". И уже летом 1939 года была сдана в набор книга Л.В.Канторовича "Математические методы организации и планирования производства", в которой закладывались основания того, что ныне называется математической экономикой.

Американский математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течении пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.

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

Цель данной курсовой работы — изучение метода искусственного базиса.

В соответствии с данной целью выделяются следующие этапы:

1. Теоретические сведения по линейному программированию
2. Сферы применения метода искусственного базиса
3. Теоретические основы метода
4. Алгоритм метода
5. Решение экономической задачи

 

1.Теоретическая  часть

1.1. Линейное программирование.

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

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

Виды задач линейного программирования.

Вид задачи определяется по системе ограничений.

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

1.2. Методы решения задач.

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

Графический метод – основан на геометрической интерпретации задачи и применяется для решения стандартных задач линейного программирования с двумя переменными.

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

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

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

1.3. Искусственный базис.

Данный метод решения применяется при наличии в системе ограничений условий-равенств и(или) условий-неравенств типа ≥, и является модификацией симплексного метода. Решение системы производится путём ввода искусственных переменных Xj со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами M, имеющими смысл "штрафов" за ввод искусственных переменных, а в задачи минимизации - с положительными M. Таким образом, из исходной получается новая M-задача (поэтому метод искусственного базиса так же называют M-методом).

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

1.3.1. Правила преобразований симплексной таблицы

При составлении новой итерации симплекс-таблицы в ней происходят следующие изменения: 

• Итоговая строка ∑ считается как сумма произведения ai,i *cj. По минимальному элементу этой строки выбирают ведущий столбец l;
• Последний столбец рассчитывается по формуле   ai,0 / al,i если al,i>0, иначе ставим прочерк. По минимальному элементу этого столбца выбирают ведущую строку k;

• Вместо базисной переменной xk записываем xl;  

• Ведущий элемент заменяется на единицу ak,l'= 1;

• Все элементы ведущего столбца кроме ведущего (ak,l) умножаются на 0;

• Все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l;

• Все оставшиеся элементы симплекс-таблицы преобразуются по формуле ai,j'= ai,j- ai,l×ak,j/ ak,l.

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

Замечание 2. После выхода из базиса всех искусственных переменных дальнейшие вычисления идут обычным симплекс-методом.

1.3.2. Алгоритм метода искусственного базиса.

Шаг 1. Приводим задачу ЛП к каноническому виду с неотрицательными правыми частями  ai0, i=1,..., m.

F=с1x1+с2x2+...сnxn+0(xn+1+xn+2+…+xn+m)-с0→ max

a11x11+a12x12+…+a1nxn+xn+1=a10

a21x21+a22x22+…+a2nxn+xn+2=a20

…………………………………………..

ai1xi1+ai2xi2+…+ainxn+xn+i=ai0

…………………………………………..

am1xm1+am2xm2+…+amnxn+xn+m=am0

при x1  ≥ 0; x2 ≥ 0; …; xn+m ≥ 0.

Замечание. Курсивом выделены балансовые переменные.

Шаг 2. Ввод Базисных переменных.

В каждое i-е ограничение вводим искусственную переменную xn+m+i >0. Всего m новых искусственных переменных.

 В целевую функцию  F вводим m дополнительных отрицательных слагаемых с коэффициентами –М, где М — произвольная очень большая константа.

 

 

 

F=с1x1+с2x2+...сnxn+0(xn+1+xn+2+…+xn+m) -M(xn+m+1+ xn+m+2+…+ xn+m+m)→ max

a11x11+a12x12+…+a1nxn+xn+1+xn+m+1=a10

a21x21+a22x22+…+a2nxn+xn+2+ xn+m+2=a20

…………………………………………..

ai1xi1+ai2xi2+…+ainxn+xn+i+ xn+m+i=ai0

…………………………………………..

am1xm1+am2xm2+…+amnxn+xn+m+ xn+m+m=am0

при x1  ≥ 0; x2 ≥ 0; …; xn+m+m ≥ 0.

Замечание. Жирным выделены базисные переменные.

Шаг 3. Формируем начальное базисное решение новой М-задачи :

X = ( 0, ... 0, a0, ... am ).

Шаг 4. Решаем М-задачу модифицированным симплекс-методом (правила преобразований приведены выше).

Шаг 5. Анализируем решение М-задачи в соответствии со следующими правилами :

• Если в оптимальном решении М-задачи: 
  X` = ( X`1, ... X`n, X`n+1, ... X`n+m )  
  все искусственные переменные равны 0, то получено оптимальное решение исходной ЗЛП.
• Если в оптимальном решении М-задачи хотя бы одна искусственная переменная не равна 0, то исходная ЗЛП не имеет решения.

Шаг 6. Формулируем ответ.

 

 
2. Практическая  часть

2.1 Постановка задачи

На заводе из стандартных листов железа необходимо вырезать заготовки 3-х видов в количествах 24, 31, 18 шт. Каждый лист железа может быть порезан на заготовки двумя способами.

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

Вид заготовки	Количество заготовок (шт) при раскрое по способу:
	1	2
1	2	6
2	5	4
3	2	3
Отходы(см2)	12	16

 

 

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

Обозначим за х1 количество листов железа, которые надо раскроить по первому способу. За х2 примем количество листов железа, которые надо раскроить по второму способу. Количество полученных заготовок первого вида будет ровняться (2*х1 + 6*х2)шт, второго вида —(5*х1 + 4*х2)шт, а третьего — (2*х1 +3*х2)шт. Так как количество полученных заготовок должно быть не менее 24, 31, 18 шт. соответственно, то связь между получаемыми и требуемыми заготовками можно выразить системой неравенств:

2х1 + 6х2 ≥ 24

5х1 + 4х2 ≥ 31

2х1 +3х2 ≥ 18

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

Составим целевую функцию минимизации отходов:

F= 12х1 + 16х2→min 

и систему ограничений:

2х1 + 6х2 ≥ 24

5х1 + 4х2 ≥ 31

2х1 +3х2 ≥ 18

xj ≥ 0; j= 1÷ 2.

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

1. Сведем функцию к определению максимального значения. Для этого умножим функцию на -1.

F= -12х1 - 16х2→max

2. Введем балансовые переменные х3, х4, х5:

F= -12х1 - 16х2 – 0(х3+ х4+ х5)→max

2х1 + 6х2 - х3 = 24

5х1 + 4х2 – х4 = 31

2х1 +3х2 – х5 = 18

xj ≥ 0; j= 1÷5.

3. Введем искусственные переменные х6, х7, х8:

F= –12х1 – 16х2 – 0(х3+ х4+ х5) – М(х6+ х7+ х8)→max

2х1 + 6х2 – х3 + х6 = 24

5х1 + 4х2 – х4 + х7 = 31

2х1 +3х2 – х5 + х8 = 18

xj ≥ 0; j= 1÷8.

Заполним симплексную таблицу и используя алгоритм модифицированного симплексного метода найдем оптимальное решение

 

 

 

ci,j	xi	bi	-12	-16	0	0	0	-M	-M	-M
			x1	x2	x3	x4	x5	x6	x7	x8
-M	x6	24	2	6	-1	0	0	1	0	0	4
-M	x7	31	5	4	0	-1	0	0	1	0
-M	x8	18	2	3	0	0	-1	0	0	1	6
	∑	-73M	-9M	-13M	M	M	M	0	0	0
-16	x2	4		1		0	0		0	0	12
-M	x7	15		0		-1	0		1	0
-M	x8	6	1	0		0	-1		0	1	6
	∑	-21M -64	M	-16	M	M	M		0	0
-16	x2			1			0			0	—
-12	x1			0			0			0
-M	x8		0	0			-1			1	6
	∑	M	0	0	M	M	M			0
-16	x2	4		1
-12	x1	3		0
0	x3	6	0	0
	Z	-100	0	0	0