Экономико-математические модели задач
Механизм и основные этапы определения выпуска продукции при максимальной прибыли. Система ограничений общей задачи линейного программирования в развернутом виде. Проверка индексной строки. Определение вектора, который следует исключить из базиса.
Рубрика | Экономико-математическое моделирование |
Вид | контрольная работа |
Язык | русский |
Дата добавления | 15.03.2011 |
Размер файла | 76,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Задача №1.
Для производства столов и стульев имеются ресурсы трех видов: доски 1-го типа - 500 м, доски 2-го типа - 290 м и трудовые ресурсы 440 чел.-ч. От реализации столов организация получает прибыль в размере 12 у.д.е., стульев - 5 у.д.е. Затраты ресурсов на единицу изделия представлены в таблице 10.
Таблица 10 - Исходные данные
Столы |
Стулья |
||
доски 1 типа, м |
5 |
1 |
|
доски 2 типа, м |
2 |
1 |
|
трудовые ресурсы, чел.-ч |
3 |
2 |
|
Определить выпуск продукции при максимальной прибыли.
Решение:
1) Формулируем экономико-математическую модель задачи в общем виде:
Введем следующие обозначения:
i - индекс видов изделий;
j - индекс вида ресурса;
аij - расход j-ого ресурса на производство i-ого изделия;
bj - объём ресурса j-го вида;
ci - оценка переменных в целевой функции (прибыль единицы i-ого изделия);
xi - значения отыскиваемых переменных величин (количество i-ых изделий).
В принятых обозначениях математическая модель задачи имеет вид:
Система ограничений общей задачи линейного программирования в развернутом виде записывается так:
Каждое из ограничений данной системы является ограничением определенного вида сырья. При этом в левой части ограничения отражается потребность в сырье, а в правой - его запас (ресурс).
2) Запишем модель задачи в численном виде:
Введем неизвестные х1? 0 и х2?0, соответствующие количествам столов и стульев, планируемым к производству.
Тогда суммарный расход досок I вида будет 5x1+х2; суммарный расход досок II вида 2x1+х2; суммарный расход человеко-часов 3x1+2х2. Поскольку запасы ресурсов ограничены, то получаем систему ограничений:
Функция цели, соответствующая условиям задачи (максимум прибыли), будет иметь вид: f(x)=12x1+5х2 > max - целевая функция.
Решим данную задачу симплекс-методом
От общей формы модели переходим к канонической форме за счет введения трех дополнительных неизвестных х3, х4 и х5. Тогда модель принимает следующий вид:
f(x)=12x1+ 5х2+0•х3+0•х4+0•х5 > max
Базис |
Коэффициент |
Свободные члены |
х1 |
х2 |
х3 |
х4 |
х5 |
? |
|
12v |
5 |
0 |
0 |
0 |
|||||
х3 |
0 |
500 |
[5] |
1 |
1 |
0 |
0 |
100< |
|
х4 |
0 |
290 |
2 |
1 |
0 |
1 |
0 |
145 |
|
х5 |
0 |
440 |
3 |
2 |
0 |
0 |
1 |
146,67 |
|
f |
0 |
-12 |
-5v |
0 |
0 |
0 |
|||
х1 |
12 |
100 |
1 |
0,2 |
0,2 |
0 |
0 |
500 |
|
x4 |
0 |
90 |
0 |
0,6 |
-0,4 |
1 |
0 |
150 |
|
х5 |
0 |
140 |
0 |
[1,4] |
-0,6 |
0 |
1 |
100< |
|
f |
1200 |
0 |
-2,6 |
2,4 |
0 |
0 |
|||
х1 |
12 |
80 |
1 |
0 |
0,2857 |
0 |
-0,143 |
||
х4 |
0 |
30 |
0 |
0 |
-0,143 |
1 |
-0,429 |
||
х2 |
5 |
100 |
0 |
1 |
-0,429 |
0 |
0,7143 |
||
f |
1460 |
0 |
0 |
1,2857 |
0 |
1,8571 |
|||
Для модели в канонической форме составляем исходную симплексную таблицу и проверяем индексную строку. При проверке индексной строки делается вывод, что исходное базисное решение неоптимально, поскольку в строке есть два отрицательных элемента -12 и -5, которые соответствуют векторам х1 и х2. Минимальный отрицательный элемент в индексной строке -12. Следовательно, вектор х1 необходимо ввести в базис для улучшения решения.
Определяется вектор, который следует исключить из базиса. Составляются отношения компонент вектора X к положительным компонентам вектора А1 и находят среди этих отношений минимальное число: ?=min (500/5; 290/2; 440/3) = min (100; 145; 146.67)=100 соответствует индексу i=3. Следовательно, из базиса надо исключить вектор х3. Первая строка, соответствующая этому вектору, будет ведущей. Число 5, стоящее на пересечении ведущего столбца и ведущей строки, будет разрешающим элементом.
Далее делят ведущую строку на 5. Получают преобразованную ведущую строку (1; 0,2; 0,2; 0; 0) и с помощью разрешающего элемента преобразуют симплексную таблицу по правилу прямоугольника. Приступают к составлению второй таблицы. Вместо единичного вектора х3 мы вводим в базис вектор х1 (итерация I).
Вновь проверяют индексную строку. Наличие в ней числа -2,6 говорит о том, что базисное решение X = (100, 0, 0, 90, 140) неоптимально и его можно улучшить за счет введения в базис вектора х2 (итерация II).
При просмотре индексной строки видно, что все числа неотрицательны. Следовательно, базисное (оптимальное) решение Xопт= (80, 100, 0, 30, 0) оптимально, т.е. обеспечивает максимальное значение функции цели fmax=1460.
Таким образом, предприятие получит максимальную прибыль в 1460 руб., если примет план по выпуску 80 столов и 100 стульев. При этом останется неизрасходованным доски II типа в количестве 30 м.
Задача №3.
Сетевая модель комплекса работ с исходным событием 0, завершающим событием 6, и с указанными в таблице 67 продолжительностями работ показана на рисунке 5. Рассчитать величину критического пути и определить параметры событий и работ. Результаты представить графически и в виде таблицы.
Таблица 67 - Исходные данные
Исходная работа |
Продолжительность, дни |
|
(0,1) |
3 |
|
(0,2) |
2 |
|
(1,3) |
1 |
|
(2,4) |
2 |
|
(1,4) |
0 |
|
(3,5) |
4 |
|
(4,5) |
2 |
|
(4,6) |
1 |
|
(5,6) |
3 |
|
Рисунок 5 - Сетевая модель
Решение:
Выпишем все существующие полные пути: ?1=(0-2-4-6), ?2=(0-2-4-5-6), ?3=(0-1-3-5-6), ?4=(0-1-4-5-6), ?5=(0-1-4-6).
Рассчитаем их длительность: t(?1)=2+2+1=5, t(?2)=2+2+2+3=9, t(?3)=3+1+4+3=11, t(?4)=3+0+2+1=6, t(?5)=3+0+1=4.
Критический путь ?3=(0-1-3-5-6), длиной 1. На рисунке показан линией
Продолжительности выполнения работ tij известны и приписаны у соответствующих дуг графика; (рис). Определим, прежде всего, ранние сроки свершения событий ti сетевого графика. Исходное событие означает момент начала выполнения комплекса операций, следовательно, tр(0) = 0. Очевидно, что событие (1) свершится спустя 3 ед. времени после свершения события (0), так как время выполнения операции (0,1) равно 3 ед. Следовательно, tр(0)=tр(0)+t (0,1)=0+3=3. Для события (2) и (3) аналогично. Событию (4) предшествуют два пути: 1 = (0,1) и 2=(0,2). Продолжительность первого пути равна t (1,4)=3+0=2 ед. времени, а второго - 2+2=4 ед. времени. Поскольку событие (4) может свершиться не раньше момента окончания всех входящих в него операций, то tр(4)=max{tр(2)+t (2,4); tр(1)+t (1,4)}=max {4; 3}=4 и т.д.
Определим поздние сроки свершения событий j сетевого графика. В нашем примере tп(6)=tкр=11. Определим этот показатель для оставшихся событий. Из события (5) исходит одна операция, следовательно, tп(5)= tп(5) - t (5,6)=11-3=8. Из события (4) исходят две операции, поэтому tп(4)=min{tп(6) - t (4,6); tп(5) - t (4,5)}=min {11-1; 8-2}=min {10; 6}=6 и т.д.
Определим резерв времени события i
R(1)= tп(1) - tр(1)=3-3=0; R(2)= tп(2) - tр(2)= 4-2=2; и т.д.
Анализируя резервы времени события, видно, что резервы времени есть только у событий, не принадлежащих критическому пути. Критические работы, как и критические события, резервов времени не имеют.
Все остальные временные параметры легко определяются по найденным значениям tп и tр на основании приведенных выше формул. Представим расчеты временных параметров сетевого графика в виде таблицы.
Временные параметры сетевого графика для событий
События |
Ранний срок tp(j) свершения события j |
Поздний срок tп(i) свершения события i |
Резерв времени R(i) события i |
|
0 |
0 |
0 |
0 |
|
1 |
3 |
3 |
0 |
|
2 |
2 |
4 |
2 |
|
3 |
4 |
4 |
0 |
|
4 |
4 |
6 |
2 |
|
5 |
8 |
8 |
0 |
|
6 |
11 |
11 |
0 |
|
Временные параметры сетевого графика для работ
Работы |
Ранний срок начала работы (i; j) |
Ранний срок окончания работы (i; j) |
Поздний срок начала работы (i; j) |
Поздний срок окончания работы (i; j) |
Полный резерв времени Rп(i; j) работы (i; j) |
Свободный резерв времени Rп(i; j) работы (i; j) |
Независимый резерв времени Rн(i; j) работы (i; j) |
Резерв времени пути R(L) работы(i; j) |
|
(0,1) |
0 |
3 |
0 |
3 |
0 |
0 |
0 |
8 |
|
(0,2) |
0 |
2 |
2 |
4 |
2 |
0 |
0 |
9 |
|
(1,3) |
3 |
4 |
3 |
4 |
0 |
0 |
0 |
10 |
|
(2,4) |
2 |
4 |
4 |
6 |
2 |
0 |
- |
9 |
|
(1,4) |
3 |
3 |
3 |
6 |
0 |
0 |
0 |
11 |
|
(3,5) |
4 |
8 |
4 |
8 |
0 |
0 |
0 |
7 |
|
(4,5) |
4 |
6 |
4 |
8 |
0 |
0 |
0 |
9 |
|
(4,6) |
4 |
5 |
10 |
11 |
6 |
6 |
4 |
10 |
|
(5,6) |
8 |
11 |
8 |
11 |
0 |
0 |
0 |
8 |
|
Список используемой литературы
продукция максимальный прибыль индексный
1. Кузнецов В.П. Экономико-математические методы и модели. - Мн.: Минский институт управления, 2000. - 264 с.
2. Минюк С.А. Математические методы и модели в экономике: Учеб. пособие / Минюк С.А., Ровба Е.А., Кузьмич К.К.-Мн.: ТетраСистемс, 2002. - 432 с.
3. Пугачева О.В. Экономико-математические методы и модели: практическое пособие для студентов экономических специальностей вузов / О.В. Пугачева; М-во образования РБ, Гомельский государственный университет им. Ф. Скорины, - Гомель: ГТУ им. Ф. Скорины, 2006. - 108 с.
4. Экономико-математические методы и модели: Учеб. пособие / Под общ. ред. А.В. Кузнецова. - Мн.: БГЭУ, 2000. - 512 с.
5. Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. В.В. Федосеева. - М.: ЮНИТИ, 2001. - 382 с.
Размещено на Allbest.ru
Подобные документы
Моделирование экономических систем: основные понятия и определения. Математические модели и методы их расчета. Некоторые сведения из математики. Примеры задач линейного программирования. Методы решения задач линейного программирования.
лекция [124,5 K], добавлен 15.06.2004Основные понятия моделирования. Общие понятия и определение модели. Постановка задач оптимизации. Методы линейного программирования. Общая и типовая задача в линейном программировании. Симплекс-метод решения задач линейного программирования.
курсовая работа [30,5 K], добавлен 14.04.2004Исследование методом Жордана-Гаусса системы линейных уравнений. Решение графическим и симплексным методом задач линейного программирования. Экономико-математическая модель задачи на максимум прибыли и нахождение оптимального плана выпуска продукции.
контрольная работа [177,8 K], добавлен 02.02.2010Решение задач линейного программирования на примере ПО "Гомсельмаш". Алгоритм и экономико-математические методы решения транспортной задачи. Разработка наиболее рациональных путей, способов транспортирования товаров, оптимальное планирование грузопотоков.
курсовая работа [52,3 K], добавлен 01.06.2014- Примеры использования графического и симплексного методов в решении задач линейного программирования
Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
контрольная работа [367,5 K], добавлен 11.05.2014 Построение экономико-математической модели задачи, комментарии к ней и получение решения графическим методом. Использование аппарата теории двойственности для экономико-математического анализа оптимального плана задачи линейного программирования.
контрольная работа [2,2 M], добавлен 27.03.2008Решение задач линейного программирования с применением алгоритма графического определения показателей и значений, с использованием симплекс-метода. Использование аппарата теории двойственности для экономико-математического анализа оптимального плана ЗЛП.
контрольная работа [94,6 K], добавлен 23.04.2013Способы решения задач линейного программирования с вещественными числами симплекс-методом. Общие задачи, формы записи, максимизация и минимизация функции методом искусственного базиса. Пути поиска и исключения из базиса искусственных переменных.
контрольная работа [130,6 K], добавлен 09.02.2013Задача оптимального составления смесей при производстве бензина различных сортов. Модели формирования шихты при выплавке чугуна и смешивания волокон. Решение задач линейного программирования с помощью различных приемов и математического программирования.
курсовая работа [94,6 K], добавлен 17.11.2016Построение математической модели, максимизирующей прибыль фирмы от реализации всех сделок в виде задачи линейного программирования. Сущность применения алгоритма венгерского метода. Составление матрицы эффективности, коэффициентов затрат и ресурсов.
контрольная работа [168,7 K], добавлен 08.10.2009