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

Е.П. Панфилова

Высшая математика

(часть 4)

Методические рекомендации по компьютерному тестированию

для студентов заочной формы обучения

Бобруйск, 2011

Р е ц е н з е н т: доцент кафедры информатики, статистики и высшей математики Бобруйского филиала Белорусского государственного экономического университета кандидат физико-математических наук Шамукова Н.В.

СОДЕРЖАНИЕ

ПЕРЕЧЕНЬ ТЕМ ДЛЯ ТЕСТИРОВАНИЯ

Предмет, метод и классификация задач математического программирования

1 Предмет математического программирования.

2.Примеры оптимизационных экономических задач, сводящихся к задаче математического программирования.

3.Постановка общей задачи математического программирования.

Линейное программирование

1. Постановка общей задачи линейного программирования (ЗЛП).

2. Частные виды модели ЗЛП (каноническая, симметричная). Преобразование одной формы записи ЗЛП в другую.

3. Геометрическая интерпретация ЗЛП.

4. Графический метод решения ЗЛП.

5. Основная теорема линейного программирования.

6.1. Симплексный метод решения ЗЛП.

6.2. Алгоритм нахождения опорного решения ЗЛП.

6.3. Алгоритм нахождения оптимального решения ЗЛП.

6.4. Признак неразрешимости ЗЛП.

6.5. Признак неограниченности множества оптимальных планов.

6.6. Признак неограниченности целевой функции на множестве планов.

Двойственность в линейном программировании

1. Взаимодвойственные задачи линейного программирования и их математические модели.

2.Примеры симметричных двойственных задач и их экономическая интерпретация.

3. Несимметричные двойственные задачи.

4. Алгоритм построения двойственной задачи.

5. Теоремы двойственности и их экономические приложения.

6. Двойственные оценки и использование их для анализа решения ЗЛП.

Транспортная задача

1. Постановка транспортной задачи (ТЗ) по критерию стоимости и её математическая модель. Открытая и закрытая транспортная задачи.

2. Теорема о разрешимости ТЗ.

3. Структура опорного плана ТЗ. Циклы в транспортной таблице и их свойства.

4. Способы построения начального опорного плана ТЗ.

5. Алгоритм метода потенциалов. Признак оптимальности опорного плана ТЗ. Потенциалы поставщиков и потребителей. Оценки свободных клеток транспортной таблицы.

6. Усложненные постановки ТЗ.

7. Задачи транспортного типа с максимизируемой целевой функцией и особенности её решения методом потенциалов.

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

1. Экономические примеры задач целочисленного программирования.

2. Задача полностью (частично) целочисленного линейного программирования.

3. Решение ЗЦЛП методом отсечения Гомори.