Методы линейного программирования

 

2)По F-строке выбираем наибольший по величине отрицательный элемент у  нас он равен -1, соответствующий этому элементу столбец является разрешающим.

3)Находим отношения  членов к соответствующим элементам  разрешающего столбца.

базисные переменные	коэф. переменных					свободные члены	отношения
	x1	x2	x3	x4	x5
0	1	1	-1	0	0	4	4
0	-1	2	0	1	0	2	1
0	1	2	0	0	1	10	5
F	2	-1	0	0	0	0	0

                                                                                     

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

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

базисные переменные	коэф. переменных					свободные члены	отношения
	x1	x2	x3	x4	x5
0	1	1	-1	0	0	4	4
0	-1	2	0	1	0	2	1
0	1	2	0	0	1	10	5
F	2	-1	0	0	0	0	0

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

5)Элементы разрешающей  строки предыдущей таблицы делим  на разрешающий элемент и записываем на прежнее место.

Остальные элементы таблицы записываем по формуле:

базисные переменные	коэф. переменных					свободные члены	отношения
	x1	x2	x3	x4	x5
0	1,5	0	-1	-1	0	3
x2	-0,5	1	0	0,5	0	1
0	2	0	0	-1	0	8
F	1,5	0	0	1	0	1

 

Таким образом, оптимальное решение найдено, следовательно,            x₂=1, а все остальные элементы равны 0.

Задача 4.

Компания производит полки для ванных комнат двух размеров - А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В - 3 м² материала. Компания может получить до 1200 м² материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В - 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В - 4 ден. ед., то сколько полок каждого типа следует выпускать в неделю?

 

Решение

Составим математическую модель задачи. Пусть x₁ – количество полок вида А, x₂- количество полок вида В, которые производятся в неделю. Прибыль от продажи такого количества полок составит 3x₁+4x₂, прибыль требуется максимизировать. Выпишем ограничения задачи .x₁+x₂≤550-  в неделю  на рынке может быть реализовано до 550 полок.

Затраты материала: 2x₁+3x₂≤1200

Затраты машинного  времени:12x₁+30x₂≤9600

Таким образом, приходим к задаче линейного программирования.

F=3x₁+4x₂→max,

x₁+x₂≤550,

2x₁+3x₂≤1200,

12x₁+30x₂≤9600,

x₁≥0,x₂≥0.

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

F=3x₁+4x₂→max,

x₁+x₂+x₃=550,

2x₁+3x₂+x₄=1200,

12x₁+30x₂+x₅=9600,

x_i≥0,i=1,2,3,4,5

Составим симплекс-таблицу

базисные переменные	коэф. переменных					свободные члены	отношения
	x1	x2	x3	x4	x5
0	1	1	1	0	0	550	550
0	2	3	0	1	0	1200	400
0	12	30	0	0	1	9600	320
F	-3	-4	0	0	0	0	0

 

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

базисные переменные	коэф. переменных					свободные члены	отношения
	x1	x2	x3	x4	x5
0	0,6	0	1	0	-0,033	230	383,3
0	0,8	0	0	1	-0,1	240	300
x2	0,4	1	0	0	0,033	320	800
F	-1,4	0	0	0	0,13	1280

 

базисные переменные	коэф. переменных					свободные члены	отношения
	x1	x2	x3	x4	x5
0	0	0	1	-0,75	0,042	50	1190
x1	1	0	0	1,25	-0,125	300	2400
x2	0	1	0	-0,5	0,083	200	2409
F	0	0	0	1,75	-0,042	1700

 

 

 

 

базисные переменные	коэф. переменных					свободные члены	отношения
	x1	x2	x3	x4	x5
x5	0	0	24	-18	1	1200
x1	1	0	3	-1	0	450
x2	0	1	-2	1	0	100
F	0	0	1	1	0	1750

 

В последнем  плане строка F не содержит отрицательных значений, план x₁=450,x₂=100 оптимален, целевая функция принимает значение 1750.

 Таким образом,  чтобы получить максимальную прибыль предприятию необходимо производить 450 полок вида A и 100 полок вида В, при этом прибыль составит 1750 ден.ед., а останется неиспользованными 1200 минут машинного времени.

 

 

 

 

 

 

Заключение

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

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

Таким образом, использование симплекс-метода в  задачах линейного программирования   является наиболее оптимальным.

 

 

 

 

 

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

1. Алесинская, Т.В. Экономико-математические методы и модели. Линейное программирование / Т.В. Алесинская.- Таганрог, 2002.
2. Балдин К.В. Краткий курс высшей математики / К.В. Балдин, Ф.К. Балдин, В.И.Джеффаль, Н.А.Кочкин,  А.В.Рукосуев, Е.В.Шустова.-М.: Издательство «Дашков и К», 2009.
3. Балдин, К.В. Математическое программирование/ К.В.Балдин.-М.: Издательство «Дашков и К»,2009.
4. Васильев, Ф.П. Линейное программирование / Ф.П. Васильев, А.Ю.Иваницкий, 2008.
5. Грешилов, А.А. Прикладные задачи математического программирования: Учебное пособие / А.А.Грешилов.-М.: Издательство «Логос» 2006.
6. Количественные методы в экономических исследованиях: Учебник для вузов –М.: Издательство «Юнита-Дана»,2004.
7. Зайченко, Ю.П. Исследование операций / Ю.П.Зайченко, С.А.Шумилова, 2003.
8. Карасев, А.Н. Математические методы в экономике / А.Н. Карасев, Н.Ш. Кремер, Т.н. Савельева, 2000.
9. Лищенко, А.В. Линейное  и нелинейное программирование/ А.В.Лищенко,2003.
10. Минько, Э.В. Методы прогнозирования и исследования операций: Учебное пособие/ Э.В.Минько, А.Э.Минько.-М.: Издательство «Инфра-м»,2010.
11. Орлов, А.И. Теория принятия решений: Учебное пособие/ А.И. Орлов.-М.: Издательство «Март»,2004.
12. Поттосина, С.А. Экономико-математические модели и методы / С.А.Поттосина , В.А. Журавлев.-М.: Издательство Минск,2003.
13. Солодовников, А.С. Математика в экономике. Часть . Линейная алгебра, аналитическая геометрия и линейное программирование / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов, И.Г. Шандра.-М.: Издательство «Финансы и статистика»,2011.
14. Справочник по математики для экономистов: Учебное пособие –М.: Издательство «Инфра-м»,2007.
15. Сеславина, Е.А. Математическое моделирование экономических процессов / Е.А. Сеславина.-М.: Издательство РГОТУПС, 2006.
16. Количественные методы в экономических исследованиях: Учебник для вузов- М.: Издательство «Юнити-Дана»,2004.
17. Смординский, С.С. Оптимизация решений на основе методов и моделей математического программирования/ С.С.Смординский , Н.В.Батин,2004.
18. Струченков, В.И. Методы оптимизации в прикладных задачах / В.И.Струченков.-М.: Издательство «Солон-Пресс»,2009.
19. Юденков, А.В. математическое программирование в экономике : Учебное пособие / А.В.Юденков, М.И.Дли, В.В. Круглов.- М.: издательство «Финансы и статистика»,2010.
20. Корнев, В.В. Прикладные методы оптимизации / В.В. Корнев, В.В. Курдюмов, В.С. Рыхлов, 2004.