Решение задач целочисленного программирования с использованием метода Гомори и графическая интерпретация решения

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Комсомольский-на-Амуре государственный технический университет»

Факультет компьютерных технологий

Кафедра «Информационные системы»

РАСЧЁТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ

по дисциплине «Исследование операций и методы оптимизации»

Решение задач целочисленного программирования с использованием метода Гомори и графическая интерпретация решения

Вариант 20

Студент группы 3ПИб-1                                       Е. С. Берестнева

Преподаватель                                                       О. М. Воротникова

2015

Содержание

Введение        3

1 Постановка задачи        4

2 Решение методом Гомори        4

3 Графическая интерпретация решения        21

Заключение        30

Список использованных источников        31

Введение

Большой класс прикладных задач оптимизации сводится к задачам целочисленного линейного программирования. Под задачей целочисленного программирования понимается задача, в которой переменные должны принимать целые значения.

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

1 Постановка задачи

Используя метод Гомори, решить задачу целочисленного линейного программирования, а также дать графическую интерпретацию решения. Математическая модель:

F= –2x1 + 2x2 + 4x4 → max

          [pic 1]

2 Решение методом Гомори

Математическая модель представлена в каноническом виде. Приведем её к полной канонической записи, для этого необходимо выставить все коэффициенты при x. Полная каноническая запись будет выглядеть следующим образом:

F= –2x1 + 2x2 + 0х3 + 4x4 + 0х5 → max

[pic 2]

Далее перейдем к симплексной записи математической модели. В общем виде она выгляди следующим образом:

F= С1x1 + С2x2 + С3х3 + … + Сnxn→ max (min)

[pic 3]

В данном случае симплексная форма математическая модель примет вид:

F= –2x1 + 2x2 + 0х3 + 4x4 + 0х5 → max

[pic 4]

Для перехода к симплекс-таблице необходимо убедиться, что в симплексной форме математической модели присутствуют базисные переменные. Как правило, базисные переменные в матрице коэффициентов представлены единичными векторами. Построим матрицу коэффициентов при неизвестных :

[pic 5]

Единичный вектор – это запись, состоящая из одной единицы, стоящей на любом месте и n-1 нулей, стоящих на всех остальных местах.