Математическое программирование

Размещено на http://www.allbest.ru/

РЕСПУБЛИКА КАЗАХСТАН

АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ

КАФЕДРА КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ

Расчетно-графическая работа № 2

Дисциплина: модели и методы управления

Вариант № 12

Выполнила: ст. группы БВТ-09-4

Сариева Д.Б.

Проверила: ассистент кафедры КТ

Акижанова З.А.

Алматы 2011

Задание № 6.

Записать математическую модель, решить методом Гомори и провести экономический анализ полученного оптимального решения.

Доски длиной 3,4 м, имеющиеся в достаточном количестве, следует распилить на заготовке двух видов: длиной 1,5 м и длиной 0,9 м, причем заготовок первого вида должно быть получено не менее 78 штук и заготовок второго вида не менее 45 штук. Каждая доска может быть распилена на указанные заготовки несколькими способами. Требуется найти число досок, распиливаемых каждым способом, с тем, чтобы необходимое количество заготовок было получено из наименьшего количество досок.

Решение:

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

№ способа	1- вид заготовки	2- вид заготовки	План
1	2	0	х1
2	1	2	х2
3	0	3	х3
Минимальное количество заготовок	78	45

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

Хi - планируемое количество досок, подлежащих распилке по i-му способу, i = 1,2,3.

Тогда планируемое количество досок для распилки определяется формулой: F= х1+х2+х3 > min. Это количество должно быть минимальным.

Количество первого вида заготовок должно быть не менее 78, поэтому запишем следующее неравенство: 2х1 + х2 ? 78, а количество 2-го вида заготовок - не менее 45: 2х2 + 3х3 ? 45.

Количество досок не может быть отрицательным и дробным числом, поэтому х1 ? 0, х2 ? 0, х3 ? 0, х1 , х2 , х3 - целые.

Итак, определена математическая модель данной задачи.

Теперь приведем ее к ОЗЛП. Изменив знак целевой функции, можно рассматривать вместо минимума максимум целевой функции:

Z(X)=-F(X);

Z(X)=-х1-х2-х3 > max, а ограничения записываются в виде равенств :

2х1 + х2 - х4 = 78

2х2+3х3 - х5 = 45.

Здесь х4 и х5 - дополнительно введенные неотрицательные переменные величины. Тогда целевая функция имеет вид:

Z(X)=-х1-х2-х3 + 0*х4 + 0*х5> max

Изменим знаки и запишем ограничения в следующем виде:

-2х1 - х2 + х4 = -78

-2х2 - 3х3 + х5 = -45.

х4 и х5 - базисные переменные, значит первоначальное псевдорешение можно записать как:

Х0={х1=0, х2=0, х3=0, х4= -78, х5=-45} , Z(X0)=0, F(X0)=0.

Проверка на оптимальность полученного псевдоплана и дальнейшее решение задачи показаны с помощью симплекс-таблицы.

i	базис			-1	-1	-1	0	0
1		0	-78	-2	-1	0	1	0
2		0	-45	0	-2	-3	0	1
3		Z =	0	1	1	1	0	0
				1/2	1
1	х1	-1	39	1	1/2	0	-1/2	0
2	х5	0	-45	0	-2	-3	0	1
3		Z =	-39	0	1/2	1	1/2	0
					1/4	1/3
1	х1	-1	111/4	1	0	-3/4	-1/2	1/4
2	х2	-1	45/2	0	1	3/2	0	-1/2
3		Z =	-201/4	0	0	1/4	1/2	1/4

После трех итераций найдено оптимальное решение задачи. Однако в нем не выполняется условие целочисленности найденных значений переменных:

Х1={х1=111/4, х2=45/2, х3=0, х4= 0, х5=0} , Z(X1)= -201/4, F(X1)= 201/4.

Поэтому по методу Гомори должно быть составлено новое ограничение. Для этого рассматривается первая строка последней симплекс-таблицы, потому что дробная часть значения переменной, находящейся на этой строке, имеет наибольшую дробную часть: 0,75 > 0,5.

Дополнительные ограничения составляются в следующем виде:

1*х1 + 0*х2 - ѕ* х3 - Ѕ* х4 + ј* х5 ? 111/4

ј *х3 + Ѕ* х4 + ј *х5 ? ѕ

Домножим на 4 и получим:

х3+2х4+х5 ? 3.

Введем новую переменную х6 ? 0 и запишем равенство:

х3+2х4+х5 - х6 = 3/ *(-1)

-х3-2х4-х5 + х6 = -3.

С учетом данного дополнительного ограничения составляются симплекс-таблицы:

i	базис			-1	-1	-1	0	0	0
1		-1	111/4	1	0	-3/4	-1/2	1/4	0
2		-1	45/2	0	-1	3/2	0	-1/2	0
3		0	-3	0	0	-1	-2	-1	1
4		Z =	-201/4	0	0	1/4	1/2	1/4	0
1	х1	-1	30	1	0	0	1	1	-3/4
2	х2	-1	18	0	1	0	-3	-2	3/2
3	х3	-1	3	0	0	1	2	1	-1
4		Z =	-51	0	0	0	0	0	1/4

Решение, которое удовлетворяет всем требованиям постановки задачи, записывается в следующем виде:

Х={х1=30, х2=18, х3=3, х4= 0, х5=0} , Z(X)= -51, F(X)= 51.

Итак, первым способом будут распилены 30 досок, вторым способом - 18 досок и третьим способом -3 доски. Всего будет распилено 51 досок. Из решения данной задачи следует, что при решении задачи на минимум целевой функции ее значение будет больше, когда учитывается условие целочисленности нежели без учета целочисленности: 51 > 201/4.

Задание № 7

Решить следующую задачу методом потенциалов:

;

Решение:

Это открытая транспортная задача, т.к. ?Аi ? ?Bj. А = (28, 32, 24, 16), В = (13, 25, 17, 10, 30); ?Аi = 28 + 32 + 24 +16 = 100, ?Bj = 13 + 25 + 17 + 10 +30 = 95.

1. Приведем ее к закрытой транспортной задаче. Т.к. не хватает потребителей, внесем фактического потребителя с тарифом перевозки = 0. Определим первоначальное опорное решение транспортной задачи способом наименьшего элемента, который основан на выборе вначале наименьшей стоимости перевозки груза. Поэтому распределение груза начинается с клетки в таблице, где находится наименьший элемент.

	B1	B2	B3	B4	B5	Bф	Запасы
A1							28
A2							32
A3							24
A4							16
Потребности	13	25	17	10	30	5

В данной задаче наименьшим элементом является 0; он в таблице встречается 2 раза, но начинать можно с любой из 2-х клеток, где они находятся. Пусть рассматривается та клетка, которая расположена в 5 столбце. В эту клетку записали число 30, т.е. 5-ый потребитель B5 удовлетворяет все свои потребности за счет второго поставщика A2, х25=30, следовательно, он не получит груза от других поставщиков: х15= х35= х45=0.

Остаток груза у второго поставщика равный 2, передается 2-му потребителю B2, т.к. у него наименьший элемент = 0. Заполнив таблицу таким образом, получим новый план перевозок:

х11=13, х12=10, х13=0, х14=0, х15=0, х1ф=5;

х21=0, х22=0, х23=2, х24=0, х25=30, х2ф=0;

х31=0, х32=9, х33=15, х34=0, х35=0, х3ф=0;

х41=0, х42=6, х43=0, х44=10, х45=0, х4ф=0.

Затрата на выполнение этого плана:

F=2*13 + 9*10 + 2*9 + 1*15 + 6*6 + 3*10 = 215.

2. Определим оптимальность решения методом потенциалов. Для этого определим потенциалы занятых клиентов.

V1-U1-2=0

V2-U1-9=0

VФ-U1-0=0

V3-U2=0

V5-U2=0

V2-U3-2=0

V3-U3-1=0

V2-U4-6=0

V4-U4-3=0

Пусть U1=0, тогда: U2=8, U3= 7, U4= 3, V1=2, V2=9, V3=8, V4=6, V5=8, VФ=0.

Заполним значения незаполненных клеток:

V3-U1-4=4

V4-U1-10= -4

V5-U1-6=2

V1-U2-7= -13

V2-U2-3= -2

V4-U2-5= -7

VФ-U2= -8

V1-U3-5= -10

V4-U3-7= -8

V5-U3-8= -7

VФ-U3= -7

V1-U4-11= -12

V3-U4-2= 3

V5-U4-4= 1

VФ- U4= -3

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

1) Выбирается та клетка таблицы, где имеется наибольшее положительное значение выражения Vi - Uj - Cij и в нее стараются записать возможно большее число.

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

Получим новый план перевозки груза транспортной задачи:

	B1	B2	B3	B4	B5	Bф	Запасы
A1							28
A2							32
A3							24
A4							16
Потребности	13	25	17	10	30	5

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

V1-U1-2=0

V3-U1-4=0

VФ-U1=0

V3-U2=0

V5-U2=0

V2-U3-2=0

V3-U3-1=0

V2-U4-6=0

V4-U4-3=0

Пусть U1=0, тогда: U2=4, U3= 3, U4= -1, V1=2, V2=5, V3=4, V4=2, V5=4, VФ=0.

Заполним значения незаполненных клеток:

V2-U1-9= -4

V4-U1-10= -8

V5-U1-6= -2

V1-U2-7= -9

V2-U2-3= -2

V4-U2-5= -7

VФ-U2= -4

V1-U3-5= -6

V4-U3-7= -8

V5-U3-8= -7

VФ-U3= -3

V1-U4-11= -8

V3-U4-2=3

V5-U4-4= 1

VФ- U4= -3

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

	B1	B2	B3	B4	B5	Bф	Запасы
A1							28
A2							32
A3							24
A4							16
Потребности	13	25	17	10	30	5

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

V1-U1-2=0

V3-U1-4=0

VФ-U1=0

V3-U2=0

V5-U2=0

V2-U3-2=0

V2-U4-6=0

V3-U4-2=0

V4-U4-3=0

Пусть U1=0, тогда: U2=4, U3= 6, U4=2, V1=2, V2=8, V3=4, V4=5, V5=4, VФ=0.

Заполним значения незаполненных клеток:

V2-U1-9= -1

V4-U1-10= -5

V5-U1-6= -2

V1-U2-7= -9

V2-U2-3= 1

V4-U2-5= -4

VФ-U2= -4

V1-U3-5= -9

V3-U3-1= -3

V4-U3-7= -8

VФ-U3= -6

V5-U3-8= -10

V1-U4-11=-11

V5-U4-4= -2

VФ- U4= -2

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

	B1	B2	B3	B4	B5	Bф	Запасы
A1							28
A2							32
A3							24
A4							16
Потребности	13	25	17	10	30	5

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

V1-U1-2=0

V3-U1-4=0

VФ-U1=0

V2-U2-3=0

V3-U2=0

V5-U2=0

V2-U3-2=0

V3-U4-2=0

V4-U4-3=0

Пусть U1=0, тогда: U2=4, U3= 5, U4=2, V1=2, V2=7, V3=4, V4=5, V5=4, VФ=0.

Заполним значения незаполненных клеток:

V2-U1-9= -2

V4-U1-10= -5

V5-U1-6= -2

V1-U2-7= -9

V4-U2-5= -4

VФ-U2= -4

V1-U3-5= -8

V3-U3-1= -2

V4-U3-7= -7

V5-U3-8= -9

VФ-U3= -5

V1-U4-11=-11

V2-U4-6= -1

V5-U4-4= -2

VФ- U4= -2

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

х11=13, х12=0, х13=10, х14=0, х15=0, х1ф=5;

х21=0, х22=1, х23=1, х24=0, х25=30, х2ф=0;

х31=0, х32=24, х33=0, х34=0, х35=0, х3ф=0;

х41=0, х42=0, х43=6, х44=10, х45=0, х4ф=0.

Fmin=2*13 + 4*10 + 0*5 + 3*1 + 0*1 + 0*30 + 2*24 + 2*6 +3*10 = 159.

Задание № 8

Решить следующую задачу нелинейного программирования:

;

,

Решение:

Решим задачу, используя метод множителей Лагранжа. Найдем минимальное значение функции F(x)=4x1 + x1 2+ 8x2 +x22 > min при условии х1 + х2=180, т.е. без учета требования неотрицательности переменных. Для этого составим функцию Лагранжа:

F(x1,x2,л) = 4х1+ х12+8х2+х22 + л(180 - х1 - х2).

Вычислим их частные производные по х1, х2, л и приравняем их к нулю:

Перенесем в левые части первых двух уравнений л и приравняем их левые части. Получим:

4+ 2х1 = 8 + 2х2 , или х1 - х2 =2

Решая последнее уравнение совместно с уравнением х1 + х2=180 , найдем х1 = 91, х2 = 89, что удовлетворяет условию неотрицательности переменных. Эта точка является подозрительной на экстремум. Используя вторые частные производные, можно показать что в данной точке функция имеет условный минимум.

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

Список литературы:

1. Куралбаев З.К. Модели и методы управления. Учебное пособие. Алматы 2010 г.

2. Акулич И.А. Математическое программирование в примерах и задачах. Учебное пособие для ВУЗов. «Высшая школа», 1986 г.

3. Ашманов С.А. Линейное программирование. - М.: Наука, 1978. - 400с.

4. Карманов В.Г. Математическое программирование. - М.: Наука, 1975.-322 с.

5. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.В. Математическое программирование. - М.: Высшая школа, 1980. - 356 с.

Размещено на Allbest.ru