Решение задачи линейного программирования в ms
| скачать Решение задачи линейного программирования в 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 с помощью решающего блока можно решить множество различных оптимизационных задач (задач на максимум и минимум) с ограничениями любого типа. При решении задачи целочисленного программирования необходимо добавить ограничение, показывающее, что переменные целочисленные. При решении других оптимизационных задач вводят целевую функцию и ограничения. ^ L = 5x1 - 2x3  min- 5x1 - x2 + 2x3 ≤ 2 - x 1+x3 + x4 ≤ 5 - 3x1 + 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 и установим опцию "равной минимальному значению". В поле Изменяя ячейки необходимо указать адреса ячеек, в которых хранятся изменяемые значения. В нашем случае это ячейки ^ . Для добавления ограничений необходимо щелкнуть по кнопке Добавить, появится диалоговое окно Добавить ограничение (рис. 2).
В поле ввода ^ необходимо ввести адрес ячейки, где хранится ограничение, затем, щелкнув по стрелке, выбрать знак и ввести значение ограничения в поле Ограничение. Щелчок по кнопке OK означает ввод очередного ограничения и возврат к диалоговому окну ^ . Щелчок по кнопке Добавить вводить очередное ограничение, находясь в окне Добавить ограничение. В нашем случае окно будет иметь вид, изображенный на рис. 3. Щелчок по кнопке Выполнить начнет процесс решения задачи, завершится который появлением диалогового окна, изображенного на рис. 4.
Щелчок по кнопке ^ приведет к появлению в ячейке С1 значения целевой функции L, а в ячейках A1:A4 - значений переменных x1-x4, при которых целевая функция достигает минимального значения. Если задача не имеет решения или неверно были заданы исходные данные, в окне ^ может появиться сообщение о том, что решение не найдено. Итак, назначение основных кнопок и окон диалогового окна Поиск решения:
Требуется составить такой рацион кормления животных тремя видами корма, при котором они получат необходимое количество питательных веществ A и B и себестоимость кормов будет минимальна. Цены кормов, требуемое количество питательных веществ и их содержание в каждом корме показаны в таблице.
Если обозначить X=(x1, x2, x3) — искомое количество кормов, то задача ЛП формулируется так:
Математическую формулировку задачи необходимо оформить в виде таблицы, отражающей основные зависимости (Рис. 5).  Рис. 5. Внешний вид условия в программе Excel. Ячейки таблицы имеют следующий смысл:
Вызов программы поиска решения выполняется через меню "Сервис\Поиск решения...". В открывшемся окне "Поиск решения" необходимо установить следующие параметры:
 Рис. 6. Окно для ввода исходных данных задачи ЛП в программе Excel
 Рис. 7. Окно для ввода параметров решения задачи ЛП Для запуска программы необходимо в окне "Поиск решения" нажать кнопку "Выполнить". Результаты вычислений будут записаны в изменяемые ячейки таблицы. В итоге таблица должна иметь следующий вид.  Рис. 8. Внешний вид условия и полученного решения в программе Excel Таким образом, животных следует кормить:
При таком рационе затраты на кормление одного животного составят 11,88 руб. _______________ 
| |||||||||||||||||||||||||||||||||||||||
принимает минимальное значение.плохо
2не очень плохо
1отлично
3 