Линейное программирование

Процесс нахождения экстремума некоторой функции или выбор наилучшего варианта из множества возможных – это задачи оптимизации.

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

Требуется определить максимум или минимум функции при следующих ограничениях:

Пример: Рассмотрим задачу об оптимальном распределении ресурсов.

Для производства двух видов изделия А и В предприятие использует три вида сырья. Нормы расхода сырья каждого вида на изготовление единицы продукции представлены ниже. Требуется составить план выпуска изделий А и В, при котором прибыль от их реализации максимальна.

Составим математическую модель задачи.

Пусть – количество изделий вида А, – количество изделий вида В. Тогда

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

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

Получили уравнения трех прямых, построим их, каждую по двум точкам (рис. 39). Прямые соответствующие ограничениям совпадают с осями координат.

Рис. 39. Графическое решение

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

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

Координаты вершины определяют искомые величины и .

Заметим, что данная вершина является точкой пересечения прямых (1) и (2). Поэтому решим систему:

Получим и . Максимальное значение функции

Нахождение решение с использованием пакета «Поиск решения». Встроенный пакет «Поиск решения» позволяет автоматизировать решение задач линейного программирования.

Для использования пакета оформим исходные данные (рис. 40).

Рис. 40. Исходные данные

Первоначально ввести и В ячейку D3 ввести формулу =B3*$B$2+C3*$C$2. В ячейку D5 ввести формулу =B5*$B$2+C5*$C$2 и протянуть ее вниз для заполнения столбца D, на первом этапе эти формулы дадут 0.

Вызываем команду «Поиск решения» (место ее нахождения уточняйте у преподавателя). Появится диалоговое окно (рис. 41).

Рис. 41. Диалоговое окно пакета «Поиск решения»

Заполняем поля диалогового окна (рис. 41), далее нажимаем кнопку «Параметры» и устанавливаем флажки «Линейная модель» и «Неотрицательные значения», затем нажимаем кнопку «Выполнить».

В ячейках таблицы В2: С2 появится решение задачи и Максимальное значение функции появится в ячейке D3

Задания для самостоятельного выполнения.

Из таблицы 7 приложения взять исходные данные своего варианта. Вариант определяется по порядковому номеру в списке группы.

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

Решить задачу с использованием пакета «Поиск решения».

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

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

2. Графическое решение задачи.

3. Решение задачи линейного программирования с использованием пакета «Поиск решения».

Литература

1. Бахвалов Н.С. Численные методы: 3-е изд., перераб. и доп. /Н.С.Бахвалов, Н.П.Жидков, Г.М. Кобельков – М.: БИНОМ. Лаборатория знаний, 2009. - 632 с.

2. Протасов И.Д. Лекции по вычислительной математике: учеб. пособ. /И.Д. Протасов – М.: Гелиос АРВ, 2009.

3. Исаков В.Н. Элементы численных методов: учеб. пособ. /В.Н. Исаков – М.: Академия, 2008.

4. URL: https://eqworld.ipmnet.ru/ru/library/mathematics/numerics.htm