Презентация "Решение задач линейного программирования в MS Excel" по информатике – проект, доклад

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

Общая задача линейного программирования решается симплексным методом Симплекс (лат. simplex - простой) – простейший выпуклый многогранник в n-мерном пространстве с n+1 вершиной (например, тетраэдр в 3-мерном пространстве)

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

На рисунке: оптимальное решение находится в одной из вершин многоугольника решений А, В, С, D

Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений к соседней, в которой целевая функция принимает лучшее (по крайней мере, не худшее) значение

Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г.

Джордж Бернард Данциг (1914-2005) – американский математик, разработал симплексный алгоритм, считается основоположником методов линейного программирования

Леонид Витальевич Канторович (1912-1986) – советский математик и экономист, лауреат Нобелевской премии по экономике 1975 года «за вклад в теорию оптимального распределения ресурсов». Один из создателей линейного программирования

Идеи симплексного метода были разработаны в 1939 г. российским ученым Л.В.Канторовичем

Симплексный метод позволяет решить любую задачу линейного программирования В настоящее время он используется для компьютерных расчетов Рассмотрим решение задачи линейного программирования в MS Excel

В MS Excel для решения задачи линейного программирования используется надстройка ПОИСК РЕШЕНИЯ

Сначала надстройку Поиск решения необходимо подключить (до первого использования) В MS Excel 2003: Сервис / Надстройки / Поиск решения / OK

После этого команда Поиск решения включена в меню Сервис

В MS Excel 2007: 1) Кнопка Office (левый верхний угол окна программы) 2) Кнопка Параметры Excel (внизу окна меню) 3) Надстройки

1 2 3

В MS Excel 2007: 4) Кнопка Перейти (внизу окна Параметры Excel)

4

В окне Надстройки установить флажок и нажать ОК

В MS Excel 2007 кнопка Поиск решения появится во вкладке Данные

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

СРС

Ответы:

1. Создадим область переменных

Ячейки В2:В6 будут играть роль переменных (пока они пусты)

2. Введем формулу вычисления значений целевой функции Например, в ячейку А8

3. Создадим область ограничений

В ячейках А11:А13 будем вычислять левые части ограничений в системе В ячейках В11:В13 введем правые части ограничений системы

В ячейках А11:А13 будем вычислять левые части ограничений в системе

Первое ограничение

Второе ограничение

Третье ограничение

4. Вызовем окно диалога Поиск решения

При этом удобно, если активной ячейкой является ячейка со значением целевой функции

Устанавливаем целевую ячейку А8 (там где вычисляется значение целевой функции) Указываем направление оптимизации – минимизация (по условию) В поле Изменяя ячейки указываем ячейки переменных В2:В6

Укажем ограничения 4) Нажимаем кнопку Добавить Появится окно Добавление ограничения

Укажем ограничения 5) Неотрицательность переменных: Нажать кнопку Добавить 6) Остальные ограничения: Нажать OK

Осталось нажать кнопку Выполнить

Результаты Ответ:

Литература

Кремер Н.Ш., Путко Б.А. Исследование операций в экономике. - М.: ЮНИТИ, 2003. - 407 с. Красс М.С., Чупрынов Б.П. Математика для экономистов. - СПб.: Питер, 2005. - 464 с.