Раздел 6. Вычислительная математика, дискретная математика

I. Задания для самостоятельной работы

1. Изучить теоретический материал по теме «Линейное программирование» по вопросам:

1.1. Постановка и различные формы записи задач ЛП.

1.2. Каноническая форма задачи ЛП.

1.3. Приведение общей задачи ЛП к канонической форме

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

1.5. Симплексные таблицы и алгоритм решения задач ЛП.

1.6. Двойственная задача ЛП.

2. Изучить теоретический материал по вопросам:

2.1. Формулировка транспортной задачи.

2.2. Математическая модель транспортной задачи.

2.3. Закрытая и открытая ТР.

2.4. Методы построения начального опорного решения.

2.5. Метод потенциалов.

3. Выполнить задания:

Задача 1.

Фирма производит две модели А и В сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3 досок, а для изделия модели В – 4 . Фирма может получить от своих поставщиков до 1710 досок в неделю. Для каждого изделия модели А требуется 12 мин. машинного времени, а для изделия модели В – 30 мин. В неделю можно использовать 110 ч машинного времени. Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В – 4 дол. прибыли?

Решить двумя способами, используя графический и симплексный методы.

Задача № 2.

Решить транспортную задачу.

II. Контрольные вопросы для самопроверки

1. Как формулируется основная задача Л.П.?

2. Какие основные этапы необходимо выполнить для составления математической модели задачи ЛП?

3. В чем состоит графический метод решения задачи ЛП?

4. Какую задачу ЛП называют канонической?

5. В чем заключается основная теорема ЛП?

6. Что такое «опорное решение» задачи ЛП?

7. Является ли любая угловая точка области допустимых решений опорным решением?

8. В чем суть симплексного метода решения задач ЛП?

9. Как исходной задаче ЛП поставить в соответствие двойственную задачу?

10. Как формулируется транспортная задача ЛП?

11. Какая транспортная задача называется закрытой?

12. Какие вы знаете методы построения начального опорного решения?

13. Как построить систему потенциалов, соответствующую опорному решению?

14. Какой признак оптимальности опорного решения?

15. Что такое «цикл»?

16. В чем заключается вырожденность ТР? Как ее исключить?

17. Как от открытой ТР перейти к закрытой ТР?