Построение математической модели задачи линейного программирования
Построение математической модели согласно варианту. Решение задачи графическим, алгебраическим и методом симплекс-таблицы. Определение допустимого решения методом введения искусственного базиса. Анализ взаимосвязи между решениями взаимодвойственных задач.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 24.12.2014 |
| Размер файла | 460,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
СЕВАСТОПОЛЬСКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
КАФЕДРА КИБЕРНЕТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
Пояснительная записка к курсовому проекту
по дисциплине
«Прикладная математика»
Выполнил: ст. гр. М-21д
Ткаченко К. С.
вариант № 22
Проверил: ст. преп.
Балакирева И. А.
Севастополь - 2006
Содержание
- Введение
- 1. Общая формулировка задания на курсовой проект
- 2. Линейное программирование
- 2.1 Задача линейного программирования
- 2.1.1 Постановка задачи линейного программирования
- 2.1.2 Математическая модель задачи линейного программирования
- 2.1.3 Графический метод
- 2.1.4 Алгебраический метод
- 2.1.5 Метод симплекс-таблицы
- 2.1.6 Метод допустимого базиса
- 2.1.7 Решение двойственной задачи
- 2.2 Задача целочисленного линейного программирования
- 2.2.1 Постановка задачи целочисленного линейного программирования
- 2.2.2 Метод Гомори
- 2.2.3 Метод ветвей и границ
- 2.3 Задача целочисленного линейного программирования с булевскими переменными
- 2.3.1 Постановка задачи целочисленного линейного программирования с булевскими переменными
- 2.3.2 Метод Баллаша
- 2.3.3 Определение снижения трудоемкости вычислений
- 3. Нелинейное программирование
- 3.1 Задача поиска глобального экстремума функции
- 3.1.1 Постановка задачи поиска глобального экстремума функции
- 3.1.2 Метод поиска по координатной сетке с постоянным шагом и метод случайного поиска. Сравнение результатов вычислений
- 3.2 Задача одномерной оптимизации функции
- 3.2.1 Постановка задачи одномерной оптимизации функции
- 3.2.2 Метод дихотомии
- 3.2.3 Метод Фибоначчи
- 3.2.4 Метод кубической аппроксимации
- 3.3 Задача многомерной оптимизации функции
- 3.3.1 Постановка задачи многомерной оптимизации функции
- 3.3.2 Метод Хука - Дживса
- 3.3.3 Метод наискорейшего спуска (метод Коши)
- 3.3.4 Метод Ньютона
- 3.3.5 Сравнение результатов вычислений
- Заключение
- Библиографический список
- Приложение
- А. Текст программы глобальной многомерной оптимизации
- Б. Результаты работы программы
Введение
Современный этап развития человечества отличается тем, что на смену века энергетики приходит век информатики. Происходит интенсивное внедрение новых технологий во все сферы человеческой деятельности. Встает реальная проблема перехода в информационное общество, для которого приоритетным должно стать развитие образования. Изменяется и структура знаний в обществе. Все большее значение для практической жизни приобретают фундаментальные знания, способствующие творческому развитию личности. Важна и конструктивность приобретаемых знаний, умение их структурировать в соответствии с поставленной целью. На базе знаний формируются новые информационные ресурсы общества. Формирование и получение новых знаний должно базироваться на строгой методологии системного подхода, в рамках которого отдельное место занимает модельный подход. Возможности модельного подхода крайне многообразны как по используемым формальным моделям, так и по способам реализации методов моделирования. Физическое моделирование позволяет получить достоверные результаты для достаточно простых систем.
В настоящее время нельзя назвать область человеческой деятельности, в которой в той или иной степени не использовались бы методы моделирования. Особенно это относится к сфере управления различными системами, где основными являются процессы принятия решений на основе получаемой информации. математический модель задача
1. Общая формулировка задания на курсовой проект
Вариант задания для задачи линейного программирования (ЗЛП) представляет собой область допустимых решений ЗЛП и целевую функцию. Для того чтобы определить, какое значение должна достигать целевая функция - минимальное или максимальное, необходимо найти градиент целевой функции. Если направление градиента совпадает с направлением стрелки у целевой функции в варианте задания, то в задаче определяется максимальное значение целевой функции, иначе - минимальное.
Итак, задание по решению ЗЛП состоит в следующем: построить математическую модель ЗЛП согласно варианту; получить решение ЗЛП графическим методом; решить ЗЛП алгебраическим методом; решить ЗЛП методом симплекс-таблицы; определить допустимое решение ЗЛП методом введения искусственного базиса; построить ЗЛП, двойственную данной, решить эту задачу и исследовать взаимосвязь между решениями взаимодвойственных задач.
Вариант для задачи целочисленного линейного программирования (ЗЦЛП) представляет собой область допустимых решений ЗЛП и целевую функцию. Задание состоит в следующем: решить ЗЦЛП, при условии целочисленности всех переменных, входящих в задачу методом ветвей и границ и методом отсекающих плоскостей (методом Гомори).
Вариант для задачи целочисленного линейного программирования с булевскими переменными составляется студентом самостоятельно с учетом следующих правил: в задаче используется не менее 5 переменных, не менее 4 ограничений, коэффициенты ограничений и целевой функции выбираются произвольно, но таким образом, чтобы система ограничений была совместна. Задание состоит в том, чтобы решить ЗЦЛП с булевскими переменными, используя алгоритм Баллаша и определить снижение трудоемкости вычислений по отношению к решению задачи методом полного перебора.
Задание на поиск глобального экстремума функции состоит в написании программы. Программа для поиска экстремума функции может быть разработана на любом алгоритмическом языке. Задание состоит в следующем: 1) найти точку глобального экстремума функции f(X) методом поиска по координатной сетке с постоянным шагом; 2) найти точку глобального экстремума функции f(X) методом случайного поиска; 3)сравнить результаты вычислений.
Задание для нахождения одномерного локального экстремума функции (одномерная оптимизация) состоит в том, чтобы выполнить поиск минимума заданной функции методом дихотомии (3-4 итерации), уточнить интервал поиска методом Фибоначчи (3 итерации) и завершить поиск методом кубической аппроксимации.
Задание для нахождения многомерного локального экстремума функции (многомерная оптимизация) состоит в том, чтобы минимизировать функцию, применяя следующие методы: нулевого порядка - Хука-Дживса, первого порядка - наискорейшего спуска (Коши), второго порядка - Ньютона, и провести сравнительный анализ методов оптимизации по количеству итераций, необходимых для поиска экстремума при фиксированной точности и начальных координатах поиска X(0)=[-1,-1]T.
2. Линейное программирование
2.1 Задача линейного программирования
2.1.1 Постановка задачи линейного программирования
Построить математическую модель ЗЛП согласно варианту. Получить решение ЗЛП графическим методом. Решить ЗЛП алгебраическим методом. Решить ЗЛП методом симплекс-таблицы. Определить допустимое решение ЗЛП методом введения искусственного базиса. Построить ЗЛП, двойственную данной, решить эту задачу и исследовать взаимосвязь между решениями взаимодвойственных задач.
2.1.2 Математическая модель задачи линейного программирования
AB: ; ;
BC: ; ;
CD: ; ;
DE: ; ;
F: ; ;
Математическая модель:
2.1.3 Графический метод
Вычисляем значение целевой функции во всех вершинах симплекса и выбираем из них наименьшее. Это и будет оптимальное решение.
FA = 1
FB = -8
FC = -14
FD = 0
FE = 3
C(2, 4)
F = -14
2.1.4 Алгебраический метод
x2, x4, x5, x6 - базисные переменные, x1, x3 - свободные переменные
x1^F^ x3^Fv Выбираем x3 - x4
x2, x3, x5, x6 - базисные переменные, x1, x4 - свободные переменные
x1^Fv x4^F^ Выбираем x1 - x5
x1, x2, x3, x6 - базисные переменные, x4, x5 - свободные переменные
x1^F^ x4^F^
X=(2, 4, 7, 0, 0, 5)
F = -14
2.1.5 Метод симплекс-таблицы
Приведем к каноническому виду:
x2, x4, x5, x6 - базисные переменные, x1, x3 - свободные переменные
|
^ |
|||||||||
|
b |
x1 |
x3 |
|||||||
|
x2 |
1 |
2 |
-1 |
||||||
|
1 |
-3 |
1 |
|||||||
|
< |
x4 |
1 |
-3 |
1 |
1 |
||||
|
1 |
-3 |
1 |
|||||||
|
x5 |
12 |
-1 |
2 |
6 |
|||||
|
-2 |
6 |
-2 |
|||||||
|
x6 |
4 |
3 |
-1 |
||||||
|
1 |
-3 |
1 |
|||||||
|
F |
-4 |
-9 |
4 |
||||||
|
-4 |
12 |
-4 |
|
^ |
|||||||||
|
b |
x1 |
x4 |
|||||||
|
x2 |
2 |
-1 |
1 |
||||||
|
2 |
1/5 |
-2/5 |
|||||||
|
x3 |
1 |
-3 |
1 |
||||||
|
6 |
3/5 |
-6/5 |
|||||||
|
< |
x5 |
10 |
5 |
-2 |
2 |
||||
|
2 |
1/5 |
-2/5 |
|||||||
|
x6 |
5 |
0 |
1 |
||||||
|
0 |
0 |
0 |
|||||||
|
F |
-8 |
3 |
-4 |
||||||
|
-6 |
-3/5 |
6/5 |
|
b |
x5 |
x4 |
|||||||
|
x2 |
4 |
1/5 |
3/5 |
||||||
|
x3 |
7 |
3/5 |
-1/5 |
||||||
|
x1 |
2 |
1/5 |
-2/5 |
||||||
|
x6 |
5 |
0 |
1 |
||||||
|
F |
-14 |
-3/5 |
-14/5 |
||||||
X = (2, 4, 7, 0, 0, 5)
F = -14
2.1.6 Метод допустимого базиса
|
^ |
|||||||||||||||||
|
b |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|||||||||||
|
F |
0 |
-1 |
4 |
0 |
0 |
0 |
0 |
||||||||||
|
1/2 |
1/2 |
1/2 |
-1/2 |
0 |
0 |
0 |
|||||||||||
|
< |
о1 |
1 |
2 |
1 |
-1 |
0 |
0 |
0 |
1/2 |
||||||||
|
1/2 |
1/2 |
1/2 |
-1/2 |
0 |
0 |
0 |
|||||||||||
|
о2 |
2 |
-1 |
1 |
0 |
1 |
0 |
0 |
14/3 |
|||||||||
|
1/2 |
1/2 |
1/2 |
-1/2 |
0 |
0 |
0 |
|||||||||||
|
о3 |
14 |
3 |
2 |
0 |
0 |
1 |
0 |
3 |
|||||||||
|
-3/2 |
-3/2 |
-3/2 |
3/2 |
0 |
0 |
0 |
|||||||||||
|
о4 |
3 |
1 |
-1 |
0 |
0 |
0 |
1 |
||||||||||
|
-1/2 |
-1/2 |
-1/2 |
1/2 |
0 |
0 |
0 |
|||||||||||
|
f |
20 |
5 |
3 |
-1 |
1 |
1 |
1 |
||||||||||
|
-5/2 |
-5/2 |
-5/2 |
5/2 |
0 |
0 |
0 |
|
^ |
|||||||||||||||||
|
b |
о1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|||||||||||
|
F |
1/2 |
1/2 |
9/2 |
-1/2 |
0 |
0 |
0 |
||||||||||
|
5/2 |
-1/2 |
-3/2 |
1 |
0 |
0 |
1 |
|||||||||||
|
x1 |
1/2 |
1/2 |
1/2 |
-1/2 |
0 |
0 |
0 |
||||||||||
|
5/2 |
-1/2 |
-3/2 |
1 |
0 |
0 |
1 |
|||||||||||
|
о2 |
5/2 |
1/2 |
3/2 |
-1/2 |
1 |
0 |
0 |
||||||||||
|
5/2 |
-1/2 |
-3/2 |
1 |
0 |
0 |
1 |
|||||||||||
|
о3 |
25/2 |
-3/2 |
1/2 |
3/2 |
0 |
1 |
0 |
25/3 |
|||||||||
|
-15/2 |
3/2 |
9/2 |
-3 |
0 |
0 |
-3 |
|||||||||||
|
< |
о4 |
5/2 |
-1/2 |
-3/2 |
1/2 |
0 |
0 |
1 |
5 |
||||||||
|
5 |
-1 |
-3 |
2 |
0 |
0 |
2 |
|||||||||||
|
f |
35/2 |
-5/2 |
1/2 |
3/2 |
1 |
1 |
1 |
||||||||||
|
-15/2 |
3/2 |
9/2 |
-3 |
0 |
0 |
-3 |
|
^ |
|||||||||||||||||
|
b |
о1 |
x2 |
о4 |
x4 |
x5 |
x6 |
|||||||||||
|
F |
3 |
0 |
3 |
1 |
0 |
0 |
1 |
||||||||||
|
-3 |
0 |
-3/5 |
9/5 |
0 |
-3/5 |
9/5 |
|||||||||||
|
x1 |
3 |
0 |
-1 |
1 |
0 |
0 |
1 |
||||||||||
|
1 |
0 |
1/5 |
-3/5 |
0 |
1/5 |
-3/5 |
|||||||||||
|
о2 |
5 |
0 |
0 |
1 |
1 |
0 |
1 |
||||||||||
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|||||||||||
|
< |
о3 |
5 |
0 |
5 |
-3 |
0 |
1 |
-3 |
1 |
||||||||
|
1 |
0 |
1/5 |
-3/5 |
0 |
1/5 |
-3/5 |
|||||||||||
|
x3 |
5 |
-1 |
-3 |
2 |
0 |
0 |
2 |
||||||||||
|
3 |
0 |
3/5 |
-9/5 |
0 |
3/5 |
-9/5 |
|||||||||||
|
f |
10 |
-1 |
5 |
-3 |
1 |
1 |
-2 |
||||||||||
|
-5 |
0 |
-1 |
3 |
0 |
-1 |
3 |
|
^ |
|||||||||||||||||
|
b |
о1 |
о3 |
о4 |
x4 |
x5 |
x6 |
|||||||||||
|
F |
0 |
0 |
-3/5 |
14/5 |
0 |
-3/5 |
14/5 |
||||||||||
|
-14 |
0 |
0 |
-14/5 |
-14/5 |
0 |
-14/5 |
|||||||||||
|
x1 |
4 |
0 |
1/2 |
2/5 |
0 |
1/5 |
2/5 |
10 |
|||||||||
|
-2 |
0 |
0 |
-2/5 |
-2/5 |
0 |
-2/5 |
|||||||||||
|
< |
о2 |
5 |
0 |
0 |
1 |
1 |
0 |
1 |
5 |
||||||||
|
5 |
0 |
0 |
1 |
1 |
0 |
1 |
|||||||||||
|
x2 |
1 |
0 |
1/5 |
-3/5 |
0 |
1/5 |
-3/5 |
||||||||||
|
3 |
0 |
0 |
3/5 |
3/5 |
0 |
3/5 |
|||||||||||
|
x3 |
8 |
-1 |
3/5 |
1/5 |
0 |
3/5 |
1/5 |
40 |
|||||||||
|
-1 |
0 |
0 |
-1/5 |
-1/5 |
0 |
-1/5 |
|||||||||||
|
f |
5 |
-1 |
-1 |
0 |
1 |
0 |
1 |
||||||||||
|
-5 |
0 |
0 |
-1 |
-1 |
0 |
-1 |
|
b |
о1 |
о3 |
о4 |
x4 |
x5 |
о2 |
|||||||||||
|
F |
-14 |
0 |
-3/5 |
0 |
-14/5 |
-3/5 |
-14/5 |
||||||||||
|
x1 |
2 |
0 |
1/5 |
0 |
-2/5 |
1/5 |
-2/5 |
||||||||||
|
x6 |
5 |
0 |
0 |
1 |
1 |
0 |
1 |
||||||||||
|
x2 |
4 |
0 |
1/5 |
0 |
3/5 |
1/5 |
-3/5 |
||||||||||
|
x3 |
7 |
-1 |
3/5 |
0 |
-1/5 |
3/5 |
-1/5 |
||||||||||
|
f |
0 |
-1 |
-1 |
-1 |
0 |
0 |
-1 |
||||||||||
|
b |
x4 |
x5 |
||
|
F |
-14 |
-14/5 |
-3/5 |
|
|
x6 |
5 |
1 |
0 |
|
|
x2 |
4 |
3/5 |
1/5 |
|
|
x3 |
7 |
-1/5 |
3/5 |
|
|
x1 |
2 |
-2/5 |
1/5 |
Допустимое базисное оптимальное решение:
X = (2, 4, 7, 0, 0, 5)
F = -14
2.1.7 Решение двойственной задачи
Прямая задача:
Двойственная задача:
Приводим к каноническому виду:
y1, y3 - базисные переменные, y2, y4, y5, y6 - свободные переменные
|
^ |
|||||||||||||
|
b |
y2 |
y4 |
y5 |
y6 |
|||||||||
|
< |
y1 |
14 |
5 |
-5 |
2 |
-3 |
14/5 |
||||||
|
14/5 |
1/5 |
-1 |
2/5 |
-3/5 |
|||||||||
|
y3 |
9 |
3 |
-3 |
1 |
-2 |
3 |
|||||||
|
-42/5 |
-3/5 |
3 |
-6/5 |
9/5 |
|||||||||
|
Ф' |
112 |
35 |
-40 |
12 |
-25 |
||||||||
|
-98 |
-7 |
35 |
-14 |
21 |
|||||||||
|
b |
y2 |
y4 |
y5 |
y6 |
|||||||||
|
y1 |
14/5 |
1/5 |
-1 |
2/5 |
-3/5 |
||||||||
|
y3 |
3/5 |
-3/5 |
0 |
-1/5 |
-1/5 |
||||||||
|
Ф' |
14 |
-7 |
-5 |
-2 |
-4 |
||||||||
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
||||||||
|
¦ |
¦ |
¦ |
¦ |
¦ |
¦ |
||||||||
|
y5 |
y6 |
y1 |
y2 |
y3 |
y4 |
||||||||
|
2 |
4 |
7 |
0 |
0 |
5 |
F' = Ф' = 14
X = (2,4,7,0,0,5)
F= -F' = -14
2.2 Задача целочисленного линейного программирования
2.2.1 Постановка задачи целочисленного линейного программирования
Решить ЗЦЛП, при условии целочисленности всех переменных, входящих в задачу, методом ветвей и границ и методом отсекающих плоскостей (методом Гомори).
2.2.2 Метод Гомори
x3, x4 - базисные переменные, x1, x2 - свободные переменные
|
^ |
|||||||||
|
b |
x1 |
x2 |
|||||||
|
x3 |
11 |
2 |
3 |
11/2 |
|||||
|
-5 |
-1/2 |
-1/2 |
|||||||
|
< |
x4 |
10 |
4 |
1 |
10/4 |
||||
|
5/2 |
1/4 |
1/4 |
|||||||
|
F' |
0 |
2 |
1 |
||||||
|
-5 |
-1/2 |
-1/2 |
|
^ |
|||||||||
|
b |
x4 |
x2 |
|||||||
|
< |
x3 |
6 |
-1/2 |
5/2 |
12/5 |
||||
|
12/5 |
-1/5 |
2/5 |
|||||||
|
x1 |
5/2 |
1/4 |
1/4 |
10 |
|||||
|
-3/5 |
1/20 |
-1/10 |
|||||||
|
F' |
-5 |
-1/2 |
1/2 |
||||||
|
-6/5 |
1/10 |
-1/5 |
|
b |
x1 |
x2 |
|||||||
|
x3 |
12/5 |
-1/5 |
2/5 |
||||||
|
x4 |
19/10 |
3/10 |
-1/10 |
||||||
|
F' |
-31/5 |
-2/5 |
-1/5 |
||||||
X = (19/10, 12/5, 0, 0)
F = -F' = 31/5
Составляем неравенство Гомори:
|
^ |
|||||||||
|
b |
x4 |
x3 |
|||||||
|
F' |
-31/5 |
-2/5 |
-1/5 |
||||||
|
1/5 |
1/10 |
-1/2 |
|||||||
|
x2 |
12/5 |
-1/5 |
2/5 |
||||||
|
-2/5 |
-1/5 |
1 |
|||||||
|
x1 |
19/10 |
3/10 |
-1/10 |
||||||
|
1/10 |
-1/4 |
||||||||
|
< |
u2 |
-2/5 |
-1/5 |
-2/5 |
|||||
|
1 |
1/2 |
-5/2 |
|
b |
x4 |
u2 |
|||||||
|
F' |
-6 |
-3/10 |
-1/2 |
||||||
|
x2 |
2 |
-2/5 |
1 |
||||||
|
x1 |
2 |
7/20 |
-1/4 |
||||||
|
x3 |
1 |
1/2 |
-5/2 |
||||||
X = (2, 2, 1, 0)
F = -F' = 6
2.2.3 Метод ветвей и границ
Размещено на http://www.allbest.ru
|
b |
x1 |
x2 |
||
|
x3 |
12/5 |
-1/5 |
2/5 |
|
|
x4 |
19/10 |
3/10 |
-1/10 |
|
|
F' |
-31/5 |
-2/5 |
-1/5 |
Задача № 1
Приводим к каноническому виду:
x3, x4, x5 - базисные переменные, x1, x2 - свободные переменные
|
^ |
|||||||||
|
b |
x1 |
x2 |
|||||||
|
x3 |
11 |
2 |
3 |
11/2 |
|||||
|
-5 |
-1/2 |
-1/2 |
|||||||
|
< |
x4 |
10 |
4 |
1 |
5/2 |
||||
|
5/2 |
1/4 |
1/4 |
|||||||
|
x5 |
2 |
0 |
1 |
||||||
|
0 |
0 |
0 |
|||||||
|
F' |
0 |
2 |
1 |
||||||
|
-5 |
-1/2 |
-1/2 |
|
^ |
|||||||||
|
b |
x4 |
x2 |
|||||||
|
x3 |
6 |
-1/2 |
5/2 |
12/5 |
|||||
|
-5 |
0 |
-5/2 |
|||||||
|
x1 |
5/2 |
1/4 |
1/4 |
10 |
|||||
|
-1/2 |
0 |
-1/4 |
|||||||
|
< |
x5 |
2 |
0 |
1 |
2 |
||||
|
2 |
0 |
1 |
|||||||
|
F' |
-5 |
-1/2 |
1/2 |
||||||
|
-1 |
0 |
-1/2 |
|
b |
x4 |
x5 |
|||||||
|
x3 |
1 |
-1/2 |
-5/2 |
||||||
|
x1 |
2 |
1/4 |
-1/4 |
||||||
|
x2 |
2 |
0 |
1 |
||||||
|
F' |
-6 |
-1/2 |
-1/2 |
||||||
X = (2, 2, 1, 0, 0)
F' = -6
F = -F' = 6
Задача № 2
Решаем задачу с x2 ? 3 в подсистеме «Поиск решения» системы Excel. Получаем допустимое не оптимальное решение F = 5, X = (1, 3)
|
=2*$B$1+$B$2 |
1 |
=2*$B$1+3*$B$2 |
11 |
|
|
3 |
=4*$B$1+$B$2 |
10 |
||
|
=$B$2 |
3 |
|
5 |
1 |
11 |
11 |
|
|
3 |
7 |
10 |
||
|
3 |
3 |
|
Ограничения |
|||||||
|
Ячейка |
Имя |
Значение |
Формула |
Статус |
Разница |
||
|
$C$1 |
|
11 |
$C$1<=$D$1 |
связанное |
0 |
||
|
$C$2 |
|
7 |
$C$2<=$D$2 |
не связан. |
3 |
||
|
$C$3 |
|
3 |
$C$3>=$D$3 |
связанное |
0 |
2.3 Задача целочисленного линейного программирования с булевскими переменными
2.3.1 Постановка задачи целочисленного линейного программирования с булевскими переменными
Составить самостоятельно вариант для задачи целочисленного линейного программирования с булевскими переменными с учетом следующих правил: в задаче используется не менее 5 переменных, не менее 4 ограничений, коэффициенты ограничений и целевой функции выбираются произвольно, но таким образом, чтобы система ограничений была совместна. Задание состоит в том, чтобы решить ЗЦЛП с булевскими переменными, используя алгоритм Баллаша и определить снижение трудоемкости вычислений по отношению к решению задачи методом полного перебора.
2.3.2 Метод Баллаша
|
№ |
x4 |
x3 |
x2 |
x1 |
x5 |
Выполнение ограничений |
Значение F |
||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
||||||||
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
Fф=0 |
||||||
|
2 |
0 |
0 |
0 |
0 |
1 |
44 |
|||||||
|
3 |
0 |
0 |
0 |
1 |
0 |
17 |
Подобные документы
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
курсовая работа [100,0 K], добавлен 31.10.2014Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Обзор алгоритмов методов решения задач линейного программирования. Разработка алгоритма табличного симплекс-метода. Составление плана производства, при котором будет достигнута максимальная прибыль при продажах. Построение математической модели задачи.
курсовая работа [266,4 K], добавлен 21.11.2013Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.
контрольная работа [191,1 K], добавлен 05.04.2016Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.
курсовая работа [232,4 K], добавлен 01.06.2009Краткий обзор решения транспортных задач. Экономическая интерпретация поставленной задачи. Разработка и описание алгоритма решения задачи. Построение математической модели. Решение задачи вручную и с помощью ЭВМ. Анализ модели на чувствительность.
курсовая работа [844,3 K], добавлен 16.06.2011Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.
контрольная работа [2,0 M], добавлен 02.05.2012Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Алгоритм симплекс-метода. Задача на определение числа и состава базисных и свободных переменных, построение математической модели. Каноническая задача линейного программирования. Графический метод решения задачи. Разработки математической модели в Excel.
курсовая работа [1,1 M], добавлен 18.05.2013Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015Восстановление математической модели задачи нелинейного программирования. Решение уравнений прямых. Метод линеаризации: понятие, особенности применения при решении задач. Нахождение точки максимума заданной функции. Решение задачи графическим методом.
задача [472,9 K], добавлен 01.06.2013Создание математической модели, приведение ее к виду задачи линейного программирования. Геометрическая трактовка решения. Определение области допустимых значений. Составление симплекс-таблиц. Разработка опорного плана задачи методом минимального элемента.
контрольная работа [260,2 K], добавлен 22.12.2013Метод решения математической модели на примере решения задач аналитической геометрии. Описание согласно заданному варианту методов решения задачи. Разработка математической модели на основе описанных методов. Параметры окружности минимального радиуса.
лабораторная работа [310,6 K], добавлен 13.02.2009Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2.
контрольная работа [199,8 K], добавлен 15.06.2009Особенности решения транспортной задачи распределительным методом и анализ результатов. Построение математической модели, алгоритма. Создание программы для решения транспортной задачи распределительным методом в программной среде Borland Delphi 7.
курсовая работа [1000,7 K], добавлен 23.06.2012Постановка задачи линейного программирования. Решение системы уравнений симплекс-методом. Разработка программы для использования симплекс-метода. Блок-схемы основных алгоритмов. Создание интерфейса, инструкция пользователя по применению программы.
курсовая работа [1,7 M], добавлен 05.01.2015Нахождение минимума целевой функции для системы ограничений, заданной многоугольником. Графическое решение задачи линейного программирования. Решение задачи линейного программирования с использованием таблицы и методом отыскания допустимого решения.
курсовая работа [511,9 K], добавлен 20.07.2012
