Методы оптимазации в задачах планирования производства
- МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ИНСТИТУТ ЭКОНОМИКИ, УПРАВЛЕНИЯ И ПРАВА (г. КАЗАНЬ)
Кафедра высшей математики
КУРСОВОЙ ПРОЕКТ
ПО ВЫСШЕЙ МАТЕМАТИКЕ
НА ТЕМУ:
МЕТОДЫ ОПТИМИЗАЦИИ
В ЗАДАЧАХ ПЛАНИРОВАНИЯ ПРОИЗВОДСТВА
Выполнил:
Хайрутдинова Регина Нафисовна
Руководитель:
Кабирова Раиса Гашимовна
Бугульма – 2009 г.
ПОСТАНОВКА ЗАДАЧИ
Условия задачи представлены в таблице:
| D T | R T | VT | D Ж | R Ж | V Ж | B D | BR | BV | S T | S Ж | P0 | P1 | P2 |
| 13 | 7 | 1 | 3 | 3 | 1 | 0 | 720 | 180 | 21 | 9 | 30 | 0,02 | 200 |
Дополнительная
возможность 1: получение ссуды.
То есть задача формулируется следующим образом:
Строительная
фирма имеет возможность
P(y) = (30–
0,02∙y + 0,000∙1y2) процентов
годовых, если сумма кредита
превышает 50 млн. руб. и (30 – 0,02∙50 + 0,0001∙502)
= процентов годовых, если сумма кредита
меньше.
Определить
оптимальный план постройки зданий
при имеющихся ресурсах и возможностях,
стоимость своих
РЕШЕНИЕ
Составим экономико-математическую модель задачи. Для этого обозначим х1 – количество тысяч квадратных метров торговых площадей, а х2 – количество тысяч квадратных метров жилой площади построенных фирмой. Кредит у (в млн. руб.), полученный фирмой в банке может быть любым неотрицательным числом.
Эта задача является задачей оптимального использования ресурсов. Система ограничений, получаемая из ограниченности ресурсов, имеет вид:
7х1 + 1х2 ≤ у,
3х1 + 1х2
≤ 720,
1х1 + 3 х2 ≤ 180,
где справа стоит
количество каждого вида ресурса, которое
не может быть
Далее, х1
и х2 являются неотрицательными
(нельзя построить отрицательное число
квадратных метров зданий), что дает нам
тривиальное ограничение задачи:
х1
≥ 0, х2 ≥ 0
Наконец, функция цели (или целевая функция) представляет собой общую стоимость произведенной продукции, и эта функция в поставленных ограничениях оптимизируется на максимум:
F = 9х1
+ 9 х2 – f (y)
max
где функция f (y) отражает выплаты банку. Она связана с процентной ставкой Р и суммой кредита у следующим соотношением:
f (y) = (1 +P (y) ∕ 100) ∙ y
Согласно условию задачи, получаем:
(1 + 0,01 ∙ (0,15 – 0,02 ∙ y + 0,001y2)) ∙ y, при y > 50
Из- за нелинейной функции (4) к данной задаче нельзя применить методы линейного программирования непосредственно. Задача же нелинейного программирования (1)-(4) достаточно сложна.
Однако данную проблему можно разбить на два этапа. На первом определяем оптимальный план следующей задачи линейного программирования:
Z = 9х1
+ 9 х2 - f (y)
max
13х1 + 3х2 ≤ у,
7х1 + 3х2 ≤ 720,
1х1 + 1 х2 ≤ 180,
х1
≥ 0, х2 ≥ 0,
рассматривая у как параметр (известную величину). В результате решения задачи (5) - (7) получаем оптимальный план, в котором х1*, х2* и Z* зависит от у.
На втором этапе решаем задачу нелинейного программирования. Ищем у* из задачи
F
(y) = Z* (y) - f (y)
max,
y ≥ 0.
Задача
(8), (9), (4) – одномерная задача, и ее
можно легко решить графически с
последующим аналитическим
ЭТАП 1.
Для решения задачи симплекс – методом приведем систему (5)-(7) к каноническому виду, введя дополнительные балансовые переменные х3, х4, х5, которые означают неиспользованное количество денег, рабочих и стройматериалов соответственно. При этом неравенство (6) преобразуется в уравнения:
13х1 + 3х2 + х3 = у
7х1
+ 3х2 + х4
= 720
1х1 + 1х2 + х5 = 180
По смыслу балансовые переменные здесь также неотрицательны, поэтому тривиальная система неравенств принимает вид:
x j
≥ 0 для всех j = 1,5.
Введем балансовые переменные и в целевую функцию с коэффициентами равными нулю:
Z = 21х1
+9х2 + 0х3
+0х4 + 0х5
max
Задача в форме (12), (10), (11) имеет канонический вид. Соответствующая ей векторная форма записи будет такова:
с (21;9;0;0;0);
13 3 1 0 0 у
Р1 7 ; Р2 3 ; Р3 0 ; Р4 1 ; Р5 0 ; Р0 720 .
1 1 0 0 1 180
Здесь векторы Р3, Р4 и Р5 имеют базисный вид, т.е. являются единичными в одном из компонентов и нулевым во всех остальных компонентах. Их и возьмем в качестве первоначальных базисных векторов. Данная задача является классической задачей оптимального использования ресурсов, и потому в ней всегда имеется возможность выделить первоначальные базисные вектора.
Составим первоначальную симплексную таблицу:
Таблица 1.
| Базисные переменные | Свободные члены | х1 | х2 | х3 | х4 | х5 | Оценочные отношения |
| х3 | y | 13 | 3 | 1 | 0 | 0 | y/13 |
| х4 | 720 | 7 | 3 | 0 | 1 | 0 | 720/7 |
| х5 | 180 | 1 | -9 | 0 | 0 | 1 | 180/1=180 |
F |
0 | -21 | -9 | 0 | 0 | 0 | max |
Ведущим
столбцом будет первый столбец, так
как ему в индексной строке
соответствует самое
- Рассмотрим случай y/13≥720/7 . Тогда y≥ 180 и ведущей строкой будет вторая строка:
| Базисные переменные | Свободные члены | х1 | х2 | х3 | х4 | х5 | Оценочные отношения |
| х3 | y | 13 | 3 | 1 | 0 | 0 | y/13 |
| х4 | 720 | 7 | 3 | 0 | 1 | 0 | 720/7 |
| х5 | 180 | 1 | 1 | 0 | 0 | 1 | 180 |
F |
0 | -21 | -9 | 0 | 0 | 0 | max |
Таким образом,
в базис входит х1 , а покидает
ее х4.
Пересчитаем таблицу по всем правилам пересчета симплексных таблиц. Получаем новую симплексную таблицу:
| Базисные переменные | Свободные члены | х1 | х2 | х3 | х4 | х5 | Оценочные отношения |
| х3 | у – 9360/7 | 0 | -18/7 | 1 | 13/7 | 0 | |
| х1 | 720/7 | 1 | 3/7 | 0 | 1/7 | 0 | |
| х5 | 540/7 | 0 | 4/7 | 0 | 3/7 | 1 | |
F |
2160 | 0 | 0 | 0 | 3 | 0 | max |
Так
как в индексной строке все
элементы неотрицательны, то полученный
план является оптимальным. Таким образом,
при y≥180 оптимален план х1*=720,
х2*=0, х3*=(
у – 180), х4*=0, х5*=720, а значение
целевой функции равно Z=2160.
- Теперь рассмотрим случай y<180. Тогда в табл. 1 ведущей строкой будет первая строка:
| Базисные переменные | Свободные члены | х1 | х2 | х3 | х4 | х5 | Оценочные отношения |
| х3 | y | 13 | 3 | 1 | 0 | 0 | y/13 |
| х4 | 720 | 7 | 3 | 0 | 1 | 0 | 720/7 |
| х5 | 180 | 11 | 1 | 0 | 0 | 1 | 180 |
F |
0 | -21 | 9 | 0 | 0 | 0 | max |
В базис входит х1, а покидает его х3. Пересчитывая, получаем новую симплексную таблицу:
Таблица
2.
| Базисные переменные | Свободные члены | х1 | х2 | х3 | х4 | х5 | Оценочные отношения |
| х1 | y/13 | 1 | 3/13 | 1/13 | 0 | 0 | y |
| х4 | 720 - 7y/13 | 0 | 18/13 | -7/13 | 1 | 0 | 720 - 7y/13 |
| х5 | 180 - y/13 | 0 | 10/13 | -1/13 | 0 | 1 | 180-у/10 |
F |
21y/13 | 0 | -180/13 | 21/13 | 0 | 0 | max |
Ведущим столбцом будет второй, так как ему в индексной строке соответствует единственное отрицательное число. При определении ведущей среди оценочных отношений, полученных в последнем столбце, нужно выбрать наименьшее. Все они зависят от у. Определим, в каких интервалах изменения у минимально каждое из чисел αip. Для этого рассмотрим три неравенства:
720 -7 y/18 ≥ 180-у/10 → у ≤ 97200/52;
720 -7 y/18 ≥ y → у ≤12960/25;
180 – y/10 ≥ y → у ≤1800/11.
Проанализировав результат, приходим к следующим выводам:
α12 = y меньше остальных симплексных отношений при у≤1800;
α22 = 720 - 7y/18 меньше остальных отношений при у≥9720/52;
α32 = 180 – y/10 меньше остальных отношений при 1800/11≤ у≤9720/520.
Рассмотрим все три случая с учетом условий у<9360/7 и у≥0.0<y<1800/11
| Базисные переменные | Свободные члены | х1 | х2 | х3 | х4 | х5 | Оценочные отношения |
| х1 | y/13 | 1 | 3/13 | 1/13 | 0 | 0 | Y |
| х4 | 720 - 7y/13 | 0 | 18/13 | -7/13 | 1 | 0 | 720 - 7y/18 |
| х5 | 180 - y/13 | 0 | 10/13 | -1/13 | 0 | 1 | 180-y/10 |
F |
21y/13 | 0 | -180/13 | 21/13 | 0 | 0 | Max |
В базис входит х2, а покидает его х1. пересчитывая получаем новую симплексную таблицу:
| Базисные переменные | Свободные члены | х1 | х2 | х3 | х4 | х5 | Оценочные отношения |
| х2 | y/3 | 13/3 | 1 | 1/3 | 0 | 0 | |
| х4 | 714 - 7y/3 | -6 | 0 | -1 | 1 | 0 | |
| х5 | 18 - 61y/13 | 10/3 | 0 | 199/897 | 0 | 1 | |
F |
99y/13 | 60 | 0 | 81/13 | 0 | 0 | max |
Так как в
индексной строке все элементы неотрицательны,
то полученный план является оптимальным.
Таким образом, при 0≤
у≤1800 оптимальный план: х1*=0, х2*=
y/13, х3*=0, х4*=(720 - 7y/13), х5*=(180
+ 13), а значение целевой функции равно
Z*=21у/13.
97200≤ у<9360. тогда в табл. Ведущей строкой будет вторая:
| Базисные переменные | Свободные члены | х1 | х2 | х3 | х4 | х5 | Оценочные отношения |
| х1 | y/13 | 1 | 3/13 | 1/13 | 0 | 0 | y/3 |
| х4 | 720 - 7y/13 | 0 | 18/13 | -7/13 | 1 | 0 | 720 - 7y/18 |
| х5 | 180 - y/13 | 0 | 10/13 | -1/13 | 0 | 1 | 180 – y/10 |
F |
21y/13 | 0 | -180/3 | 21/13 | 0 | 0 | Max |
В базис входит х2, а покидает его х4. Пересчитывая, получаем новую симплексную таблицу:
| Базисные переменные | Свободные члены | х1 | х2 | х3 | х4 | х5 | Оценочные отношения |
| х1 | 720+13y/1170 | 1 | 0 | 15/9 | 1/13 | 0 | |
| х2 | 720 - 7y/18 | 0 | 1 | -7/9 | 13/18 | 0 | |
| х5 | 720 - 8y/9 | 0 | 0 | -7/69 | 101/13 | 1 | |
F |
28у/9 | 0 | 0 | 1 | 0 | 0 | max |
Так
в индексной строке все элементы
неотрицательны, то полученный план является
оптимальным. Таким образом, при 720-8у/9≤
у<180 оптимальный план: х1*=(720+13у/1170),
х2*=(720-7у/18)
, х3*=0, х4*=0, х5*=(720-8у/9),
а значение целевой функции равно Z*=(28у/9).
| Базисные переменные | Свободные члены | х1 | х2 | х3 | х4 | х5 | Оценочные отношения |
| х1 | y/13 | 1 | 3/13 | 1/13 | 0 | 0 | Y |
| Х2 | 720 - 7y/13 | 0 | 18/13 | -7/13 | 1 | 0 | 720 - 7y/18 |
| х5 | 180 - y/13 | 0 | 10/13 | -1/13 | 0 | 1 | 180 – y/10 |
F |
21y/13 | 0 | -180/3 | 21/13 | 0 | 0 | Max |
В базис входит
х2, а покидает его х5. Пересчитывая,
получаем новую симплексную таблицу:
| Базисные переменные | Свободные члены | х1 | х2 | х3 | х4 | х5 | Оценочные отношения |
| х1 | 3у/5-10 | 1 | 0 | 13/18 | 0 | 3/13 | |
| х4 | у/39 | 0 | 0 | 7/69 | 1 | -1/13 | |
| х2 | 180-у/10 | 0 | 1 | -1/10 | 0 | 13/10 | |
F |
18у/39 | 0 | 0 | 18/10 | 0 | 21/13 | Max |
Так как в индексной строке все элементы неотрицательны, то полученный план является оптимальным. Таким образом, при 97200/52<y<1800/11 оптимальный план: х1*=(3у/5-10), х2*=(180-у/10) , х3*=0, х4*=(у/39), х5*=0, а значение целевой функции равно Z*=(18у/39).

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