- •Общая характеристика симплекс-метода
- •Требования к задачам, решаемым симплекс-методом
- •В качестве критерия оптимизации может выступать:
- •Математическая формулировка задачи
- •Информационное обеспечение моделирования
- •Требования, предъявляемые к информации
- •Подготовка исходных данных для составления матрицы эмм и решения задачи на эвм
- •Технолого-экономические коэффициенты
- •Классификация технико-экономических коэффициентов
- •Моделирование системных ограничений. Формирование ограничений по земельным ресурсам
- •Моделирование использования сельскохозяйственных угодий с учетом трансформации
- •Моделирование использования пашни и сельскохозяйственных угодий с учетом структуры угодий или посевных площадей
- •По потребности в семенах и их производству
- •К ресурсным ограничениям относятся условия по использованию трудовых, денежно-материальных средств, минеральных удобрений, машин и механизмов, оросительной воде. Общий вид
- •2. Приведение задач линейного программирования к каноническому представлению
- •Алгоритм симплекс-метода
- •Расчет всех элементов новой симплекс-таблицы
- •К основным блокам информации относятся
- •Дополнительные переменные, попавшие в базис
- •Дополнительные переменные, не попавшие в базис
- •Введение в план дополнительной переменной
- •Двойственные задачи линейного программирования
- •Тогда структурный вид двойственной задачи будет иметь вид:
- •Изменение коэффициентов в целевой функции при переменной, вошедшей в базисное решение.
- •Изменение коэффициента в целевой функции при переменной, не вошедшей в базисное решение
- •Математическая модель задачи дз
- •Последняя симплекс-таблица задачи дз-1
- •Пределы устойчивости оптимального решения при изменении коэффициентов целевой функции
К основным блокам информации относятся
Оптимальное решение – значения переменных, попавших в базис, находятся в столбце свободных и характеризуют собой ответ задачи. Небазисные переменные равны нулю.
Оптимальное значение целевой функции находится в индексной строке в столбце свободных членов .
Значения элементов индексной строки, соответствующих остаточным и избыточным переменным, называемые двойственными оценками.
Коэффициенты замещения – коэффициенты структурных сдвигов, размещаемые по строкам таблицы в столбцах основных и дополнительных переменных.
Интерпретация оптимального решения.
(На конкретном примере)
Пусть заданы основные переменные: - площадь зерновых продовольственных, - площадь фуражных, - площадь кормовых культур, - поголовье коров, - поголовье свиней.
Система ограничений включает:
1 ( ) -Ограничение по использованию площади пашни:
;
2 ( ) - По использованию площади зерновых:
;
3 ( )- По использованию материально-денежных ресурсов (тыс.):
;
4( )- По использованию трудовых ресурсов:
;
5( )- Баланс кормов:
;
Целевая функция (тыс.):
.
Дополнительные переменные:
недоиспользованная площадь пашни, га;
недоиспользованная площадь зерновых, га;
недоиспользованные денежные ресурсы, руб.;
недоиспользованные трудовые ресурсы, чел.-дн.;
недоиспользованные корма, ц.
Дополнительные переменные с по .
Основной показатель – значение Z=933333.3
Основные переменные, попавшие в базис:
- площадь зерновых продовольственных равна 666.7 га
Основные переменные, не попавшие в базис:
- площадь фуражных=0
площадь кормовых культур=0
поголовье коров=0
- поголовье свиней=0
Таблица 27 Первая симплекс-таблица (первое опорное решение) |
|||||||||||||||||
№ огр. |
Базис. переменные |
Оценка целевой функции Сi |
Значение базисной прем-ой Аi0 |
|
|
|
|
|
|
|
|
|
|
|
Конт- роль |
Частное от деления |
|
Коэффициенты замещения |
|||||||||||||||||
Основные переменные |
Дополнительные переменные |
||||||||||||||||
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 (ост) |
Х7 (ост) |
Х8 (ост) |
Х9 (ост) |
Х10 (ост) |
||||||||
1 |
Х6(ост) |
0 |
1000 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1004 |
|
- |
|
2 |
Х7(ост) |
0 |
1000 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1002 |
|
- |
|
3 |
Х8(ост) |
0 |
800000 |
1200 |
1200 |
400 |
10000 |
3000 |
0 |
0 |
1 |
0 |
0 |
815801 |
|
80 |
|
4 |
Х9(ост) |
0 |
500000 |
5 |
5 |
5 |
100 |
80 |
0 |
0 |
0 |
1 |
0 |
500196 |
|
5000 |
|
5 |
Х10(ост) |
0 |
40000 |
0 |
-30 |
-45 |
40 |
30 |
0 |
0 |
0 |
0 |
1 |
39996 |
|
1000 |
|
Zj-Cj |
|
0 |
-1400 |
0 |
0 |
-5000 |
-2000 |
0 |
0 |
0 |
0 |
0 |
-8400 |
|
|
Таблица 28
Вторая симплекс-таблица
№ огр. |
Базис переменные |
Оценка целевой функции Сi |
Значение базисной прем-ой Аi0 |
|
|
|
|
|
|
|
|
|
|
|
Конт- роль |
Частное от деления |
|
Коэффициенты замещения |
|||||||||||||||||
Основные переменные |
Дополнительные переменные |
||||||||||||||||
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 (ост) |
Х7 (ост) |
Х8 (ост) |
Х9 (ост) |
Х10 (ост) |
||||||||
1 |
Х6(ост) |
0 |
1000 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1004 |
|
1000 |
|
2 |
Х7(ост) |
0 |
1000 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1002 |
|
1000 |
|
3 |
Х4(осн) |
0 |
80 |
0,12 |
0,12 |
0,04 |
1 |
3000 |
0 |
0 |
0,0001 |
0 |
0 |
3081,2801 |
|
667 |
|
4 |
Х9(ост) |
0 |
492000 |
-700 |
-700 |
1 |
0 |
80 |
0 |
0 |
-0,01 |
1 |
0 |
490681,99 |
|
- |
|
5 |
Х10(ост) |
0 |
36800 |
-480 |
-34,8 |
-46,6 |
0 |
30 |
0 |
0 |
-0,004 |
0 |
1 |
36269,59 |
|
- |
|
Zj-Cj |
|
400000 |
-800 |
600 |
200 |
0 |
-500 |
0 |
0 |
-0,5 |
0 |
0 |
399899,5 |
|
|
Таблица 29
Результаты решения симплексной задачи (максимизация целевой функции)
№ огр. |
Базис переменные |
Оценка целевой функции Сi |
Значение базисной прем-ой Аi0 |
|
|
|
|
|
|
|
|
|
|
||||
Коэффициенты замещения |
|||||||||||||||||
Основные переменные |
Дополнительные переменные |
||||||||||||||||
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6(ост) |
Х7(ост) |
Х8(ост) |
Х9(ост) |
Х10(ост) |
||||||||
1 |
Х6(ост) |
0 |
333,3 |
0 |
6,59*10-17 |
6,67 |
-8,33 |
-2,5 |
1 |
0 |
-8,33*10-4 |
0 |
0 |
||||
2 |
Х7(ост) |
0 |
333,3 |
0 |
-1 |
-0,333 |
-8,33 |
-2,5 |
0 |
1 |
-8,33*10-4 |
0 |
0 |
||||
3 |
Х1(осн) |
0 |
666,7 |
1 |
-1 |
0,333 |
8,33 |
2,5 |
0 |
0 |
8,33*10-4 |
0 |
0 |
||||
4 |
Х9(ост) |
0 |
496700 |
0 |
-8,88*10-16 |
3,33 |
58,3 |
67,5 |
0 |
0 |
-4,17*10-3 |
1 |
0 |
||||
5 |
Х10(ост) |
0 |
40000 |
0 |
-30 |
-45 |
40 |
30 |
0 |
0 |
0 |
0 |
1 |
||||
Zj-Cj |
|
933333,3 |
0 |
1400 |
467 |
6670 |
1500 |
0 |
0 |
177 |
0 |
0 |
Основные переменные, попавшие в базис, характеризуют эффективные отрасли хозяйства, не попавшие в базис – характеризуют отрасли, развитие которых нецелесообразно.