Метод ветвей и границ решение задач целочисленного программирования

Автор работы: Пользователь скрыл имя, 01 Июля 2013 в 23:07, курсовая работа

Краткое описание

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

Скачать полностью (86.02 Кб) Сколько стоит заказать работу?

Прикрепленные файлы: 1 файл

курсовая.doc

— 301.00 Кб (Скачать документ)

Итерация №2.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i1
и из них выберем наименьшее:
min (- , 4⁵/₇ : ²/₇ ) = 16¹/₂
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (²/₇) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	min
x₂	2¹/₇	-1¹/₇	1	0	³/₇	³/₇	^-1/₇	-
x₃	4⁵/₇		0	1	¹/₇	¹/₇	²/₇
F(X3)	41⁴/₇		0	0	2⁵/₇	2⁵/₇	1³/₇	0

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x₃ в план 3 войдет переменная x₁.
Строка, соответствующая переменной x₁ в плане 3, получена в результате деления всех элементов строки x₃ плана 2 на разрешающий элемент РЭ=²/₇
На месте разрешающего элемента в плане 3 получаем 1.
В остальных клетках столбца x₁ плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x₁ и столбец x₁.
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:

B	x ₁	x ₂	x ₃	x ₄	x ₅	x ₆
2¹/₇-(4⁵/₇ • -1¹/₇):²/₇	-1¹/₇-(²/₇ • -1¹/₇):²/₇	1-(0 • -1¹/₇):²/₇	0-(1 • -1¹/₇):²/₇	³/₇-(¹/₇ • -1¹/₇):²/₇	³/₇-(¹/₇ • -1¹/₇):²/₇	^-1/₇-(²/₇ • -1¹/₇):²/₇
4⁵/₇ : ²/₇	²/₇ : ²/₇	0 : ²/₇	1 : ²/₇	¹/₇ : ²/₇	¹/₇ : ²/₇	²/₇ : ²/₇
41⁴/₇-(4⁵/₇ • -5⁴/₇):²/₇	-5⁴/₇-(²/₇ • -5⁴/₇):²/₇	0-(0 • -5⁴/₇):²/₇	0-(1 • -5⁴/₇):²/₇	2⁵/₇-(¹/₇ • -5⁴/₇):²/₇	2⁵/₇-(¹/₇ • -5⁴/₇):²/₇	1³/₇-(²/₇ • -5⁴/₇):²/₇

Получаем новую симплекс-таблицу:

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆
x₂	21	0	1	4	1	1	1
x₁	16¹/₂	1	0	3¹/₂	¹/₂	¹/₂	1
F(X3)	133¹/₂	0	0	19¹/₂	5¹/₂	5¹/₂	7

1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆
x₂	21	0	1	4	1	1	1
x₁	16¹/₂	1	0	3¹/₂	¹/₂	¹/₂	1
F(X4)	133¹/₂	0	0	19¹/₂	5¹/₂	5¹/₂	7

Оптимальный план можно записать так:
x₂ = 21
x₁ = 16¹/₂
F(X) = 4•21 + 3•16¹/₂ + 18 = 151¹/₂

3.Структурное проектирование задачи

Заключение

По итогам проведенного исследования можно сделать следующие выводы, что в некоторых задачах линейного программирования результат вычислений должен выражаться целым числом. Например, количество изготовленных автомобилей, изданных книг, собранных холодильников и т.д. Целевая функция и условия ограничений в таких задачах также выражаются целыми числами .В данной работе мы на примере решили задачу методом ветвей и границ, здесь же в проекте была разобрана и изучена тема: "Метод ветвей и границ", по которой представлена презентация. В презентации были рассмотрены следующие разделы: основные понятия, пример целочисленного решения задачи линейного программирования графическим методом. Слайды презентации подробно описаны в пояснительной записке.

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

1.Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986. - 319 с.

2.Вентцель Е.С. Исследование операций: задачи, принципы, методология. - М.: Высшая школа, 2004. - 208 с.

3.Исследование операций в экономике/ Под ред. Кремера Н.Ш. - М.:ЮНИТИ, 2004. - 407 с.

4.Конюховский П.В. Математические методы исследования операций в экономике. Краткий курс. - СПб.: Питер, 2002. - 208 с.

5.Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. - М.: Новое знание, 2003. - 424 с.

6.Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. - М.: Вузовский учебник, 2004. - 144 с.

7.Просветов Г.И. Математические методы в экономике: Учебно-методическое пособие. - М.: Издательство РДЛ, 2004. - 160 с.

8.Интернет ресурсы: - http://matesha.ru/book/lp11.php

-http://www.matburo.ru/ex_mp.php?p1=mpsim

Приложение

Информация о работе Метод ветвей и границ решение задач целочисленного программирования