Вопросы для повторения.

1. Линейное программирование. Математическая модель.

2. Общая задача линейного программирования. Управляющие переменные. Целевая функция. Решение задачи линейного программирования.

3. Основная (каноническая) задача линейного программирования. Допустимое решение. Область допустимых решений. Оптимальное решение задачи линейного программирования.

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

5. Симплекс-метод решения задачи линейного программирования, его геометрический смысл. Правила перехода к канонической форме. Стандартная форма задачи линейного программирования. Опорный план задачи линейного программирования, признак его оптимальности. Вырожденный и невырожденный план.

6. Устройство симплекс-таблицы. Разрешающий элемент, разрешающие строка и столбец. Правила перехода к новой симплекс-таблице.

7. Метод искусственного базиса. Расширенная ЗЛП. Искусственный базис. Искусственные переменные. Алгоритм метода искусственного базиса.

8. Двойственная задача линейного программирования. Двойственная пара задач линейного программирования. Правила составления двойственной задачи по отношению к исходной. Связь между решениями прямой и двойственной задач. Теоремы двойственности. Геометрическая интерпретация двойственных задач.

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

10. Двойственный симплекс-метод. Псевдоплан. Теоремы о псевдоплане. Алгоритм двойственного симплекс-метода.

11. Целочисленное (дискретное) линейное программирование (ЦЛП). Математическая модель задачи ЦЛП. Алгоритм метода Гомори. Дробная часть числа. Геометрическая интерпретация метода Гомори (метод отсечения).

12. Алгоритм метода ветвей и границ решения задачи ЦЛП.

13. Внутренние и граничные точки множества и их классификация. Граница множества. Граница (множество) Парето.

14. Точка утопии. Метод идеальной точки.

Задачи для самостоятельного решения.

1. Мебельная фабрика выпускает стулья двух типов. На изготовление одного стула 1-го типа, стоящего 8 денежных единиц расходуется 2м. досок стандартного сечения, 0,5м² обивочной ткани и 2 человека – часа рабочего времени. Аналогичные данные для стульев 2-го типа даются цифрами: 12 денежных единиц, 4м., 0,25 м². и 2,5 человеко-часа. В наличии имеются: 440м. досок, 65м². обивочной ткани, 320 человеко-часов рабочего времени. Какие стулья и в каком количестве нужно выпустить, чтобы стоимость продукции была максимальной? Решить задачу графическим методом.

2. При переработке некоторого лекарственного сырья возможно использование одной из двух технологий. При переработке сырья по 1-ой технологии выход полезного продукта составляет 15⁰/₀, на производство 1кг продукта затрачивается 8 человеко-часов и 12 денежных единиц. При переработке сырья по 2-ой технологии выход полезного продукта составляет 10⁰/₀, на производство 1кг продукта затрачивается 14 человеко-часов и 9 денежных единиц. Фонд заработной платы не превышает 3960 денежных единиц, трудовые ресурсы 4480 человеко-часов. Масса лекарственного сырья 440кг. Какое количество сырья надо переработать, чтобы получит максимальный выход полезного продукта? Решить задачу графическим методом.

3. На звероферме могут выращиваться чёрно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используется 3 вида кормов. Количество корма каждого вида, которое должны ежедневно получать лисицы и песцы, приведено в таблице. В ней же указано общее количество корма каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки лисицы и песца.

Вид корма	Количество единиц корма, которое ежедневно должны получать		Общее количество корма
	лисица	песец
I II III	2 4 6	3 1 7	180 240 426
Прибыль от реализации одной шкурки (д. е.)	16	12

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

4. Решить задачу 1 симплекс-методом.

5. Решить задачу 2 симплекс-методом.

6. Предприятие рекламирует свою продукцию с использованием четырёх источников массовой информации: телевидения, радио, газет и расклейки объявлений. Анализ рекламной деятельности в прошлом показал, что эти средства приводят к увеличению прибыли соответственно на 10, 5, 7 и 4 у. е., в расчёте на 1 у. е., затраченную на рекламу. На рекламу выделено 50000 у. е. Администрация предприятия не намерена тратить на телевидение более 40 %, на радио и газеты – более 50 % от общей суммы выделенных средств. Как следует предприятию организовать рекламу, чтобы получить максимальную прибыль? Решить задачу симплекс-методом.

7. Решить задачу симплекс-методом. Предприятие электронной промышленности выпускает две модели радиоприёмников, причём каждая модель производится на отдельной технологической линии. Суточный объём производства первой линии – 75 изделий. На радиоприёмник первой модели расходуется 10 однотипных элементов электронных схем, на радиоприёмник второй модели – 8 таких же элементов. Максимальный суточный запас используемых элементов равен 800 единицам. Прибыль от реализации одного радиоприёмника первой и второй модели равна 30 и 20 ден. ед. соответственно. Определите оптимальные суточные объёмы производства первой и второй моделей, чтобы прибыль была максимальной.

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

9. Для задачи, состоящей в определении максимального значения функции при условиях

составить двойственную задачу и найти решение обеих задач графическим способом.

10. Методом Гомори найти максимальное значение функции при условиях

Дать геометрическую интерпретацию решения задачи.

11. Методом ветвей и границ найти максимальное значение функции при условиях

12. На множестве

заданы две линейные функции:

Требуется найти решение задачи и , при условии, что точка утопии M^*имеет координаты (5,7).