Задания для подготовки к работе

СОДЕРЖАНИЕ

ВВЕДЕНИЕ………………………………………………………………. 3

ЛАБОРАТОРНАЯ РАБОТА №1. Исследование множества опорных планов системы ограничений задачи линейного программирования в канонической форме ……………………………………………………....3

ЛАБОРАТОРНАЯ РАБОТА №2. Симплекс-метод в чистом виде …..8

ЛАБОРАТОРНАЯ РАБОТА №3. Модификации симплекс метода. Методы искусственного базиса и больших штрафов……..……………14

ЛАБОРАТОРНАЯ РАБОТА №4. Закрытая транспортная задача......20

ЛАБОРАТОРНАЯ РАБОТА №5. Двойственный симплекс метод ….27

ЛАБОРАТОРНАЯ РАБОТА №6. Нахождение седловой точки в смешанных стратегиях для матричной игры с нулевой суммой …...…34

ЛАБОРАТОРНАЯ РАБОТА №7. Решение полностью целочисленных задач с помощью первого алгоритма Гомори, а также методом ветвей и границ ………………….………………………………………………….37

ЛАБОРАТОРНАЯ РАБОТА №8. Задачи дробно-линейного программирования …………………………………………………….....40

Библиографический список ……………………………………………..46

ВВЕДЕНИЕ

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

1) название;

2) цель работы;

3) задания к работе;

4) формулировку задачи конкретного варианта (номер варианта совпадает с номером студента в групповом журнале);

5) решение задачи конкретного варианта без использования ЭВМ;

6) описание алгоритма решения задачи в укрупненных блоках;

7) спецификацию основных подпрограмм.

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

ЛАБОРАТОРНАЯ РАБОТА № 1

Исследование множества опорных планов системы ограничений задачи линейного программирования (задачи ЛП) в канонической форме

Цель работы: изучить метод Гаусса-Жордана и операцию замещения, а также освоить их применение к отысканию множества допустимых базисных видов системы линейных уравнений, и решению задачи линейного программирования простым перебором опорных решений.

Задания для подготовки к работе

1. Составить программу для отыскания всех базисных видов системы линейных уравнений.

2. Организовать отбор опорных планов среди всех базисных решений, а также нахождение оптимального опорного плана методом прямого перебора. Целевая функция выбирается произвольно.

3. Решить одну из следующих ниже задач вручную (подготовить тестовые данные).

Варианты заданий

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

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

1. Как формулируется общая задача линейного программирования?

2. Когда задача линейного программирования называется имеющей каноническую форму?

3. Какая форма задачи линейного программирования называется стандартной?

4. C помощью каких приемов производятся преобразования моделей линейного программирования?

5. Дайте определения базисного и допустимого базисного вида системы линейных уравнений, базисного и опорного решений такой системы.

6. Когда по базисному виду системы ограничений можно заключить, что задача ЛП в канонической форме не имеет решений по причине неограниченности целевой функции на области допустимых значений?

7. Опишите алгоритм метода Гаусса-Жордана с произвольным выбором разрешающего элемента.

8. Базисные и свободные переменные, отвечающие данному базисному виду системы уравнений. Операция замещения.

9. Сформулируйте фундаментальную теорему симплекс-метода.