Контрольная работа № 3 «Целочисленное программирование» Вариант № 37

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

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР)

Кафедра компьютерных систем в управлении и проектировании (КСУП)

Контрольная работа № 3

«Целочисленное программирование»

Вариант № 37

Выполнил:

2014

Исходная информация

i №	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
37	8	6	1	9	2	1	6	8	9	8	6	2	6	9	3	4	3	7	2	5	2	5	9	4

Контрольная работа 3

Целочисленное программирование

1. Формулировка задачи линейного программирования

Исходные данные:

i	1	2	3
i	7	8	9
i	3	6	9
i	19	20	21

.

Задача целочисленного линейного программирования:

- целые .

2. Содержательная постановка задачи

В цехе решено установить три вида станков, для размещения которых отводится 7 м2 площади. На приобретение оборудования выделено 7 млн. руб. Станок 1-го типа стоит 6 млн. руб. и производит продукции на 1 млн. руб. в месяц; Станок 2-го типа стоит 8 млн. руб. и производит продукции на 1 млн. руб. в месяц. Станок 3-го типа стоит 9 млн. руб. и производит продукции на 9 млн. руб. в месяц. Сколько станков каждого типа нужно купить и установить для получения максимальной выручки от выпущенной продукции, если для размещения одного станка 1-го, 2-го и 3-го типа требуется 8, 6 и 1 м2 площади соответственно?

Обозначения математической модели:

- число установленных станков каждого вида;

- цена месячной продукции станка каждого вида;

- общая площадь, отведенная для размещения станков;

- выделенные денежные средства для закупки станков;

- площадь, необходимая для размещения станка -го вида;

- цена одного станка каждого вида.

3. Определение оптимального решения модели методом ветвей и границ

Шаг 1. Исходное допустимое решение .

Исходная задача заносится в дерево задач в качестве задачи 1.

Нижняя граница оптимального значения целевой функции на первой итерации

Итерация 1

       Шаг 2. Выбираем задачу 1.

       Шаг 3. Решаем задачу линейного программирования, соответствующую задаче 1:

Обозначим через значение целевой функции и введем остаточные переменные .

Дерево задач:

В результате получим систему уравнений (I):

,                (0)

               (1)

,                (2)

где .

Исходное базисное решение:

; ; .

Базисные переменные .

Итерация 1

Шаг 2. Вводим в базис переменную, отрицательный коэффициент при которой в уравнении (0) имеет наибольшее абсолютное значение.

Шаг 3. Наибольшее возможное значение определяется уравнением (2), где отношение наименьшее.

Шаг 4. Замена опорного плана.

а) разделим строку (2) на 9

б) умножим строку (2) на 9 и результат прибавим к строке (0)

в) умножим строку (2) на (-1) и результат прибавим к строке (1)

В результате получим систему уравнений:

,                        (0)

               (1)

               (2)

Значения переменных нового базиса:

; ; .

Целевая функция увеличилась до .

Итерация 2

Шаг 2. Так как в строке (0) все коэффициенты положительны, получено оптимальное решение.

.

       Шаг 4. Полученное оптимальное решение задачи не является целочисленным, поэтому переход на шаг 5.

       Шаг 5. Выбираем переменную , которая в полученном решении имеет нецелочисленное значение . Запишем в дерево две задачи: в задаче 2 добавляется ограничение , в задаче  3 добавляется ограничение . Принимаем

Итерация 2

       Шаг 2. Выбираем задачу 2.

       Шаг 3. Решаем задачу линейного программирования, соответствующую задаче 2:

Из и следует , поэтому исключим эту переменную из задачи:

Полученную задачу с двумя переменными решим графически:

Оптимальное наибольшее значение целевой функции в области допустимых значений соответствует экстремальной точке b. В этой точке

,        откуда        .

Целевая функция увеличилась до .

Получено оптимальное решение .

       Шаг 4. Полученное оптимальное решение задачи не является целочисленным, поэтому переход на шаг 5.

       Шаг 5. Выбираем переменную , которая в полученном решении имеет нецелочисленное значение . Запишем в дерево две задачи: в задаче 4 добавляется ограничение , в задаче 5 добавляется ограничение . Принимаем

Итерация 3

       Шаг 2. Выбираем задачу 4.

       Шаг 3. Решаем задачу линейного программирования, соответствующую задаче 4:

Из и следует , поэтому исключим эту переменную из задачи:

Решение этой задачи: ; .

Получено оптимальное решение .

       Шаг 4. Полученное оптимальное решение задачи не является целочисленным, поэтому переход на шаг 5.

       Шаг 5. Запишем в дерево две задачи: в задаче 6 добавляется ограничение , в задаче 7 . Принимаем

Итерация 4

       Шаг 2. Выбираем задачу 6.

       Шаг 3. Задача линейного программирования, соответствующая задаче 6:

       имеет решение ; .

Получено оптимальное решение .

       Шаг 4. Полученное оптимальное решение задачи является целочисленным, принимаем Переходим на шаг 2.

Итерация 5

       Шаг 2. Выбираем задачу 7.

       Шаг 3. Задача линейного программирования, соответствующая задаче 7:

не имеет допустимого решения (система ограничений несовместна).

Принимаем

Итерация 6

       Шаг 2. Выбираем задачу 5.

       Шаг 3. Задача линейного программирования, соответствующая задаче 5:

Графическая модель:

Задача не имеет допустимого решения.

Принимаем

Итерация 7

       Шаг 2. Выбираем задачу 3.

       Шаг 3. Задача линейного программирования, соответствующая задаче 3:

Представим переменную в виде , где .

Получим

Система ограничений несовместна (при неотрицательных значениях переменных второе неравенство не может выполняться).

Задача не имеет допустимого решения.

Принимаем

Итерация 8

Шаг 2. В дереве задач не осталось нерассмотренных висячих вершин. Выполнение алгоритма закончено: .

Оптимальное целочисленное решение:

4. Математическая модель с учетом дополнительных условий:

а) станки типа 1 устанавливаются только в том случае, если устанавливаются станки хотя бы одного типа 2 и 3;

б) установка станков типа 2 возможна только в том случае, если не устанавливаются станки типа 1 и не устанавливаются станки типа 3.

Пусть - достаточно большое положительное число.

Ограничение (а) можно выразить дополнительным условием

.

При , т. е. когда устанавливаются станки хотя бы одного типа 2 и 3, это ограничение можно не учитывать, а при с учетом неотрицательности получаем .

Пусть - достаточно большие положительные числа и - логическая переменная.

Ограничение (б) можно выразить дополнительными условиями .

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

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

То есть случай соответствует возможности при , а случай соответствует требованию при или .

Математическая модель:

- логическая переменная,

- целые .

5. Математическая модель транспортной задачи с учетом дополнительных условий:

а) для любого из восьми пунктов транспортной сети могут использоваться

не более двух дорог, связывающих его с соседними пунктами;

б) общая длина всех дорог транспортной сети не может превышать 40. (В

качестве длины дороги между пунктами i и j следует взять число cij).

Введем логические переменные .

Пусть - достаточно большие положительные числа.

Введем дополнительные условия:

.

При первое неравенство можно не учитывать, а из второго следует .

При второе неравенство можно не учитывать, а из первого следует .

То есть выполняется .

Тогда ограничение (а) можно выразить дополнительными условиями .

Ограничение (б) можно выразить дополнительным условием .

Математическая модель:

,

- логические переменные .