1.6. Задачи с булевыми переменными

Частным случаем рассмотренных выше задач являются задачи, в результате решения которых искомая переменная x_j может принимать одно из заранее заданных значений w_u, u=1,n.

Для решения подобной задачи помимо (1), (2) и (3) экономико-математическая модель задачи включает следующее условие:

х_j=w₁×₁+w₂×₂+…+w_n×_n, (15)

где w_u – один из вариантов возможных значений; _u – булевая переменная, которая может принимать только одно из двух значений - 0 или 1 (u=1,n).

х_j может должна быть равна только одному из значений w_u, что достигается введением дополнительных ограничений:

0 _u 1 (16)

 _u – целое

Согласно (11) только одна _u равна единицы, все остальные нулю.

При решении задачи в Excel используется методика, рассмотренная в п. 1.5. В таблицу Excel заносятся данные построенной модели. В диалоговом окне “Поиск решения” указываем в «изменяя ячейки» - адреса ячеек искомых переменных и булевых переменных (кроме искомых переменных, входящих в (15)).

1.7. Варианты заданий линейного программирования

Перечень вопросов, подлежащих рассмотрению в теоретической части:

1. Классификация методов моделирования.

2. Классификация математических моделей.

3. Задачи линейного программирования и способы их решения.

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

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

6. Построение двойственной задачи.

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

8. Постановка и описание задач с булевыми переменными.

9. Описания методики и анализа решения задач в Microsoft Excel.

Содержимое расчетной части:

1. Решение задачи симплекс-методом и в Microsoft Excel.

2. Целочисленное решение задачи.

3. Решение задачи в Microsoft Excel с использованием булевых переменных

4. Решение двойственной задачи симплекс-методом с проведением анализа устойчивости двойственных оценок.

5. Выводы после решения каждой задачи.

Перечень вопросов для защиты:

• Классификация методов моделирования, их суть;

• классификация математических моделей;

• канонические и неканонические модели;

• что называется допустимым решением задачи линейного программирования;

• что называется оптимальным решением задачи линейного программирования;

• суть симплексного метода, условия его применения;

• правила построения симплексных таблиц;

• понятие базисных и небазисных переменных, ключевой строки, ключевого столбца, индексной строки, генерального элемента;

• суть метода Гомори;

• суть двойственной задачи задач и ее разновидности;

• методика построения двойственной задачи;

• какие переменные называются объективно обусловленными оценками;

• определение двойственных оценок при решении исходной задачи симплексным методом;

• анализ значений по отчетам Microsoft Excel;

• методика решения задачи с двойственными переменными и определение предельных значений изменения каждого ресурсов

2.Динамическое программирование