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

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


Смотрите также:
Краснер Н. Я., Пастухов А. И., Щепина И. Н...
Название Лекция-семинар: Построение математических моделей целочисленного линейного...
Название Лекция-семинар: Построение математических моделей целочисленного линейного...
Название Лекция-семинар: Построение математических моделей целочисленного линейного...
Название Лекция-семинар: Построение математических моделей целочисленного линейного...
Задача линейного программирования. Симплекс-метод и его сходимость...
Программа вступительного испытания по предмету «Информационные системы в экономике»...
Задачи разбиения множества, как задача целочисленного линейного программирования...
Литература: [1,8-11,16,18]...
Краткий обзор моделей стохастического программирования и методов решения экономических задач...
Методологический базис тпр...
" " 2010 г. Вопросы государственного экзамена по специальности для студентов специальности...



Загрузка...
скачать
Решение задачи линейного программирования в MS Excel-2003


Цель работы: Изучение возможностей пакета MS Excel-2003 при решении задач линейного программирования. Приобретение навыков решения задач линейного программирования.

Общая формулировка задачи ЛП:

найти неотрицательное решение X системы линейных уравнений AX=B, при котором целевая функция f=CX принимает максимальное (минимальное) значение, где A — матрица коэффициентов; B — объемы ресурсов.

Экономический смысл системы AX=B заключается в задании ограничений на расходуемые ресурсы.

Экономический смысл целевой функции f=CX заключается в максимальной прибыли или минимальной себестоимости, получаемой от оптимального решения X.

Например, если X — вектор объемов выпуска продукции, а С - вектор прибыли, получаемой от единицы каждого вида продукции, то f — суммарная прибыль от выпуска всей продукции.

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



В задачи целочисленного программирования добавляется ограничение, что все xi должны быть целыми.

Excel имеет несколько программ-надстроек, выполняющих решение различных задач. Одной из надстроек является "Поиск решения", позволяющая решать оптимизационные задачи в Excel. Чаще всего это задачи линейного программирования (ЛП).

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

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

^ ПРИМЕР 1. Решить задачу линейного программирования:

L = 5x1 - 2x3 min
- 5x
1 - x2 + 2x3 ≤ 2
- x
1+x3 + x4 ≤ 5
- 3x
1 + 5x4 ≤ 7

Для решения подобных задач в MS EXCEL предназначена команда Поиск решения из меню Сервис.

Пусть значения x1, x2, x3, x4 хранятся в ячейки A1:A4, a значение функции L - в ячейке С1. Введем ограничения:

С2 = -5*A1 - A2 + 2*A3
С3 = -А1 +А3 + А4
С4 = -3*А1 + 5*А4.


Таким образом, было задано условие исходной задачи линейного программирования.


Примечание. Ниже приведен интерфейс для MS Office-2003. В MS Office-2007 – 2010 интерфейс программы Excel радикально изменился (другие пункты меню), но окна примерно похожи: см. рис.1.1., рис 1.2. Подробнее о работе в Excel 2007 – 2010 – см. Справку по теме «Поиск решения» в программе Excel соответствующей версии.

Ниже приводится ход решения применительно к Excel из MS Office-2003.




Рис. 1.1. Окно для ввода параметров «Поиск решения» для Excel из MS Office-2003.



Рис. 1.2. Окно для ввода параметров «Поиск решения» для Excel из MS Office-2010

Выполним команду из главного меню Сервис Поиск решения (рис.1.1.).

Устремим целевую функцию в ячейке C1 к минимуму. Для этого введем в поле. Установить целевую функцию значение С1 и установим опцию "равной минимальному значению".

В поле Изменяя ячейки необходимо указать адреса ячеек, в которых хранятся изменяемые значения. В нашем случае это ячейки ^ А1:А4.

Для добавления ограничений необходимо щелкнуть по кнопке Добавить, появится диалоговое окно Добавить ограничение (рис. 2).



Рис. 2

В поле ввода ^ Ссылка на ячейку необходимо ввести адрес ячейки, где хранится ограничение, затем, щелкнув по стрелке, выбрать знак и ввести значение ограничения в поле Ограничение.

Щелчок по кнопке OK означает ввод очередного ограничения и возврат к диалоговому окну ^ Поиск решения.

Щелчок по кнопке Добавить вводить очередное ограничение, находясь в окне Добавить ограничение.

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



Рис. 3





Рис. 4

Щелчок по кнопке ^ OK приведет к появлению в ячейке С1 значения целевой функции L, а в ячейках A1:A4 - значений переменных x1-x4, при которых целевая функция достигает минимального значения.

Если задача не имеет решения или неверно были заданы исходные данные, в окне ^ Результаты поиска решения может появиться сообщение о том, что решение не найдено.

Итак, назначение основных кнопок и окон диалогового окна Поиск решения:

  • Поле ^ Установить целевую ячейку - определяет целевую ячейку, значение которой необходимо максимизировать или минимизировать, или сделать равным конкретному значению.

  • Опции "минимальному значению", "максимальному значению" и "значению", определяют, что необходимо сделать со значением целевой ячейки - максимизировать, минимизировать или сделать равным конкретному значению.

  • Поле ^ Изменяя ячейки определяет изменяемые ячейки. Изменяемая ячейка - это ячейка, которая может быть изменена в процессе поиска решения для достижения нужного результата в ячейке из окна Установить целевую ячейку с удовлетворением поставленных ограничений.

  • Кнопка Предположить отыскивает все неформульные ячейки, прямо или непрямо зависящие от формулы в окне ^ Установить целевую ячейку, и помещает их ссылки в окно Изменяя ячейки.

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

  • кнопки Добавить, Изменить, Удалить позволяют добавить, изменить или удалить ограничение.

  • Кнопка Выполнить запускает процесс решения определенной задачи.

  • Кнопка Закрыть закрывает окно диалога, не решая проблемы. Сохраняются лишь изменения, сделанные при помощи кнопок Параметры, Добавить, Изменить и Удалить. Не сохраняются изменения, произведенные после использования данных кнопок.

  • Кнопка Параметры выводит окно диалога Параметры поиска решения, в котором можно контролировать различные аспекты процесса отыскания решения, а также загрузить или сохранить некоторые параметры, такие, как выделение ячеек и ограничений, для какой-то конкретной задачи на рабочем листе.

  • Кнопка Сбросить очищает все текущие установки задачи и возвращает все параметры к их значениям по умолчанию.
^

ПРИМЕР 2. Решить задачу.


Требуется составить такой рацион кормления животных тремя видами корма, при котором они получат необходимое количество питательных веществ A и B и себестоимость кормов будет минимальна.

Цены кормов, требуемое количество питательных веществ и их содержание в каждом корме показаны в таблице.

^ Питательные вещества

Корм 1

Корм 2

Корм 3

Требуемое количество
(ед. пит. вещества)


А (ед./кг)

10

6

12

50

Б (ед./кг)

7

10

11

45

Цена корма (руб/кг)

2,20

1,95

2,87

 

Если обозначить X=(x1, x2, x3) — искомое количество кормов, то задача ЛП формулируется так:

Найти решение X системы:




при котором целевая функция принимает минимальное значение.

Математическую формулировку задачи необходимо оформить в виде таблицы, отражающей основные зависимости (Рис. 5).




Рис. 5. Внешний вид условия в программе Excel.


Ячейки таблицы имеют следующий смысл:

  • диапазон A1:C2 — содержит матрицу A;

  • диапазон D1:D2 — содержит вектор ресурсов В;

  • диапазон A6:C6 — содержит вектор цен С;

  • диапазон A4:C4 — содержит вектор решений X, начальные значения которого заданы нулю и который будет оптимизирован программой;

  • диапазон E1:E2 — содержит выражения, вычисляющие произведение AX;

  • ячейка E6 — содержит выражение, вычисляющее f=CX.

Вызов программы поиска решения выполняется через меню "Сервис\Поиск решения...". В открывшемся окне "Поиск решения" необходимо установить следующие параметры:

  • "Установить целевую ячейку" — E6;

  • установить переключатель "Равной минимальному значению";

  • в поле "изменяя ячейки" указать диапазон A4:C4;

  • в области "Ограничения" нажать кнопку "Добавить" и в окне "Добавление ограничений" ввести ограничения: E1>=D1 и E2>=D2;




Рис. 6. Окно для ввода исходных данных задачи ЛП в программе Excel


  • нажать кнопку "Параметры..." и в открывшемся окне установить флажки "Линейная модель", "Неотрицательные значения" и выбрать переключатель "Оценка" — "Линейная".




Рис. 7. Окно для ввода параметров решения задачи ЛП


Для запуска программы необходимо в окне "Поиск решения" нажать кнопку "Выполнить". Результаты вычислений будут записаны в изменяемые ячейки таблицы. В итоге таблица должна иметь следующий вид.



Рис. 8. Внешний вид условия и полученного решения в программе Excel


Таким образом, животных следует кормить:

  • первым кормом в количестве 0,38 кг,

  • третьим — 3,85 кг,

  • второй корм – не использовать вообще.


При таком рационе затраты на кормление одного животного составят 11,88 руб.

_______________




Скачать 88,44 Kb.
оставить комментарий
Дата02.10.2011
Размер88,44 Kb.
ТипРешение, Образовательные материалы
Добавить документ в свой блог или на сайт

плохо
  2
не очень плохо
  1
отлично
  3
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх