Порядок проведения лабораторной работы

1. Получить у преподавателя вариант задания и указание по ре­жиму его ввода.

Возможны следующие режимы ввода:

а) ввод из стандартного файла, при этом надо указать только номер лабораторной работы и номер варианта;

б) ввод с терминала. В этом случае ввод осуществляется по за­просу машины. Числа вводятся в свободном формате, разделителем между числами является пробел;

в) ввод из файла. В этом случае необходимо создать файл без расширения с именем, содержащим не более четырех символов.

Структура файла:

M _ N

α₁₁ _ α₁₂ _ ... _ α_1,N-1

...

α_M-1,1 _ α_M-1,2 _ ... _ α_M-1,N-1

B₁ _ B₂ _ ... _ B_M-1

C₁ _ C₂ _ ... _ C_N-1

- 13 -

2. Запустить ведущую программу.

3. В процессе диалога с машиной осуществить ввод исходных данных.

4. Записать в протокол номер бригада и ее состав, номер и ва­риант лабораторной работы. В процессе работы в протокол записывать все действия.

5. Записать в протокол работы таблицу с экрана дисплея.

6. Отвечая на вопросы машины, определить координаты разрешаю­щего элемента.

7. С помощью калькулятора, логарифмической линейки или головы провести преобразование таблицы по формулам (3.1). Результат запи­сать в протокол.

8. Записать в протокол результат преобразований таблицы ма­шиной.

9. Повторить пп. 6,7,8 до получения оптимальной точки (если она существует).

10. Определить координаты оптимальной точки.

11. Записать число и тип допущенных ошибок.

12. Вывести на АЦПУ результаты работы из файла OUT.

Требования к отчету

1. Опишите алгоритм поиска оптимальной точки.

2. Приведите полный протокол решения конкретной задачи.

3. Объясните допущенные ошибки при выполнении лабораторной работы.

4. Опишите Ваши предложения по улучшению программы, управляю­щей ходом лабораторной работы.

Контрольные вопросы

1. Как определяется, что

а) крайняя точка найдена,

б) крайняя точка не существует,

в) оптимальная точка найдена,

г) оптимальная точка не существует.

- 14 -

2. Обоснуйте пункты алгоритма поиска

а) крайней точки

б) оптимальной точки.

Лабораторная работа 4 решение прямой и двойственной задач

Цели работы:

а. Постановка задачи линейного программирования и ее решение с помощью стандартной программы.

б. Исследование прямой и двойственной задачи.

Краткие общие сведения

Если исходная задача линейного программирования представлена в виде:

найти минимум функции ƒ = (c, x)на множестве

, (4.1).

то двойственная задача может быть сформулирована следующим обра­-зом:

найти максимум функции (B, λ) на множестве

где A^T— матрица транспонированная кА.

Двойственная к двойственной задаче есть исходная задача.

Известно, что если существует решение исходной задачи, то су­ществует решение и двойственной задачи, причем значения экстрему­мов совпадают. При этом координаты экстремальной точки для двойст­венной задачи являются коэффициентами чувствительности результата в исходной задаче по коэффициентам вектора B.

Рассмотрим видоизмененную исходную задачу:

найти min(C, X)на множестве{ х: Х ≥ О, Аx ≥ В + ε * е_i }, где ε>0,

- 15 -

Если исходная задача имеет единственное решение, то при малых ε>0 и видоизмененная задача имеет решение; причем если -значение минимума, то существует. Оказыва­-ется, что β естьi-я координата оптимальной точки для двойст­венной задачи.

Для проведения лабораторной работы составлена программа, обеспечивающая решение задачи линейного программирования при зада­нии с терминала исходных значений параметров.