Решение задачи линейного программирования в ms - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Реферат "Решение задачи линейного программирования симплекс-методом"... 2 254.76kb.
Контрольные вопросы по курсу Основная задача линейного программирования. 1 45.33kb.
Решение следующей задачи т in f = 4 х 1 3 х 1 51.99kb.
Задание Задача нахождения оптимального плана 1 29.23kb.
Целочисленное программирование 1 46.82kb.
Решение задачи. Рассмотрим пример. Пусть имеется ряд предметов П1... 1 35.44kb.
Контрольные вопросы по курсу «математические модели в управлении» 1 21.29kb.
Решение план введение. Общая задача линейного программирования 1 207.96kb.
Задача о получении максимальной прибыли 1 95.43kb.
Некоторые понятия линейного программирования. Математическое программирование 1 180.65kb.
Некоторые понятия линейного программирования. Математическое программирование 1 236.25kb.
О. В. Романова, председатель пцк учетно- экономических, страховых... 1 91.18kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Решение задачи линейного программирования в ms - страница №1/1

Решение задачи линейного программирования в 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 руб.



_______________