Решение задачи линейного программирования

Рассмотрим информационную технологию задачи линейного программирования на примере следующей задачи.

Требуется определить, в каком количестве надо выпускать продукцию четырех типов Прод1, Прод2, Прод3, Прод4, для изготовления которой требуются ресурсы трех видов: трудовые, сырье, финансы, чтобы получить максимум прибыли. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены ниже в таблице.

Таблица № 3.5

Исходные данные задачи линейного программирования

Составим математическую модель, для чего введем следующие обозначения:

х_j – количество выпускаемой продукции j-го типа;

b_i – количество располагаемого ресурса i-го вида;

a_ij – норма расхода i-го ресурса для выпуска единицы продукции j-го типа;

c_j – прибыль, получаемая от реализации единицы продукции j-го типа;

n – количество типов выпускаемой продукции;

m – количество ограничений на ресурсы.

Тогда задача линейного программирования в общем виде может быть записана.

Задача сводится к нахождению такого вектора X, при котором целевая функция F(X) принимает максимальное (или минимальное) значение с учетом ограничений, задаваемых нестрогими линейными неравенствами (или линейными уравнениями). В задачах линейного программирования целевая функция F(X) тоже должна быть линейной.

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

В ячейках A8:G12 листа 2 MS (см. рис. 3.5) Exсel разместим таблицу исходных данных задачи (см. табл. 3.5). Ячейки I22:I25 выделим для формирования вектора решения задачи . В ячейке F22 запишем выражение для вычисления правой части целевой функции. В ячейках F24:F26 сформируем формулы для вычисления левых частей ограничений (в виде нестрогих неравенств). Формулы, записанные в ячейки F22, F24:F26 приведены в табл. 3.6.

Таблица 3.6

Формулы целевой функции и ограничений

Для решения задачи линейного программирования необходимо в пункте главного меню MS Excel “Сервис” выбрать подпункт “Поиск решения…”. Если в пункте главного меню MS Excel “Сервис” отсутствует подпункт “Поиск решения…”, то необходимо в пункте главного меню “Сервис” выбрать подпункт “Надстройки” и в окне “Надстройки” поставить галочку в строке “Поиск решения…”. Если же в окне “Надстройки” отсутствует строка “Поиск решения…”, то следует переустановить MS Excel.

Рис. 3.5 Задача линейного программирования

Вид окна “Надстройки” представлен на рис. 3.6.

Рис. 3.6. Окно “Надстройки”

На рис. 3.7 представлено окно “Поиск решения”

Рис. 3.7. Окно “Поиск решения”

В окне “Поиск решения” необходимо установить целевую ячейку $F$22 (F22) равной максимальному значению (по условию задачи). В поле ниже метки с заголовком “Изменяя ячейки:” необходимо отметить ячейки вектора решения задачи линейного программирования. Ниже метки с заголовком “Ограничения:” с помощью кнопки “Добавить” следует сформировать ограничения задачи линейного программирования. Выделение ячеек и формирование ограничений реализуется в режиме конструктора (адреса ячеек в выражения вставляются на основе технологии визуального программирования).

При нажатии кнопки “Выполнить” в ячейках I22:I25 формируется вектор решения задачи линейного программирования (см. рис. 3.8). Кроме этого в ячейке F22 формируется значение целевой функции при найденном векторе решения. А в ячейках F24:F26 вычисляются значения левых частей ограничений при найденном векторе решения задачи линейного программирования.

Рис. 3.8. Решение задачи линейного программирования

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. Какие функции в MS Excel предназначены для реализации операций линейной алгебры?

2. Что произойдет, если попытаться вычислить обратную матрицу для неквадратной исходной матрицы?

3. С помощью какой функции в MS Excel можно получить обратную матрицу?

4. С помощью какой функции в MS Excel можно умножить матрицы?

5. С помощью какой функции в MS Excel можно умножить матрицу на вектор?

6. С помощью какой функции в MS Excel можно вычислить определитель матрицы?

7. Дайте определение задачи оптимизации.

8. Что представляет собой целевая функция в задачах линейного программирования?

9. Что представляет собой целевая функция в задачах математического программирования?

10. Обоснуйте правомерность использования метода “Поиск решения…” MS Excel для решения систем линейных алгебраических уравнений.

11. Для чего необходимо окно “Поиск решения” в задачах оптимизации?

12. Изложите суть метода Крамера решения систем линейных алгебраических уравнений.

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

14. Для чего необходимо окно “Надстройки” в MS Excel?

15. На основе рассмотренных информационных технологий решить СЛАУ из четырех уравнений.

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