Линейное программирование является разделом, с которого начала развиваться дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и других задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми. Задачи линейного программирования является удобной математической моделью для большого числа экономических задач (планирование производства, расходование материалов, транспортные перевозки и т.д.). Использование метода линейного программирования представляет собой важность и ценность - оптимальный вариант выбирается из достаточно значительного количества альтернативных вариантов. Также все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями.В электронных таблицах Excel с помощью функции поиска решения можно вести поиск значения в целевой ячейке, изменения значения переменных. При этом для каждой переменной можно задать ограничения, например верхнюю границу. Перед тем как запустить поиск решения, необходимо четко сформулировать в модели решаемую проблему, т.е. определить условия, выполняемые при оптимизации. Отправленной точкой при поиске оптимального решения является модель вычисления, созданная в рабочем листе. Программе поиска решения при этом необходимы следующие данные. 1. Целевая ячейка - это ячейка в модели вычисления, значения в которой должно быть максимизировано, минимизировано или же равняться определенному указанному значению. Она должна содержать формулу, которая прямо или косвенно ссылается на изменяемые ячейки, или же самой быть изменяемой. 2. Значения в изменяемых ячейках будут последовательно (методом итераций) изменяться до тех пор, пока не будет получено нужное значение в целевой ячейке. Эти ячейки, следовательно, прямо или косвенно должны влиять на значение целевой ячейки. 3. Вы можете задать как для целевой, так и для изменяемых ячеек, ограничения и граничные условия. Можно задать также ограничения для других ячеек. Прямо или косвенно присутствующих в модели. Программа предоставляет возможность задать специальные параметры, определяющие процесс поиска решения. После задания всех необходимых параметров можно запустить поиск решения. Функция поиска решения создаст по итогам своей работы три отчета, которые можно пометить в рабочую книгу.Ограничения - это условия, которые должны быть выполнены аппаратом поиска решения при оптимизации модели.

Изучение литературы показало, что:

1. Линейное программирование - это один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование».

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

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

Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки. Оптимальной считается точка, через которую проходит линия уровня, соответствующая наибольшему (наименьшему) значению функции. Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

Решим данную задачу графическим методом в табличном редакторе Microsoft Excel (рис. 1). Для построения ОДР, и линий уровня воспользуемся Мастером диаграмм . ОДР представляет собой многоугольник с вершинами в точках: (0;0), (0;6), (2;5), (4;3), (5;0).

При перемещении линии уровня в направлении вектора получаем оптимальное решение в точке с координатами (2;5).

Аналогичным образом можно решить данную задачу графическим методом в табличном редакторе OpenOffice.org Calc воспользовавшись пунктом меню Диаграмма .

Решение ЗЛП в Microsoft Excel и OpenOffice.org Calc с помощью встроенной функции Поиск решения

В табличном процессоре Microsoft Excel существует встроенная функция Поиск решения , с помощью которой можно решить задачу линейного программирования. Если данный модуль установлен, его можно запустить выбрав команду Сервис/Поиск решения (рис. 2). На экране появится диалоговое окно Поиск решения (рис. 3).

Р и с. 2. Р и с. 3.

Если такого пункта в меню Сервис не оказалось, следует загрузить соответствующую программу-надстройку. Для этого выберите команду Сервис/Надстройки (рис. 4) и в диалоговом окне Надстройки установите флажок в строке Поиск решения (рис. 5).

Разберем решение ЗЛП с помощью функции Поиск решения на примере задачи 1.

1. Создадим таблицу для ввода исходных данных: переменных, целевой функции, ограничений.

2. Введем начальные нулевые значения для и .

3. Зададим целевую функцию в ячейке D41 и ограничения в ячейках Е39, Е40 и E41 (рис. 6).

Р и с. 4. Р и с. 5.

4. Выберем команду Сервис/Поиск решения , в открывшемся окне Поиск решения установим целевую ячейку D41, зададим условие отыскания максимального значения (рис. 7).

5. В поле Изменяя ячейки установим ссылку на ячейки С40 и С41, которые будут изменены (можно ввести адреса или имена ячеек с клавиатуры или указать диапазон ячеек на рабочем листе с помощью мыши). При щелчке на кнопке Предположить автоматически выделяются ячейки, на которые есть прямая или косвенная ссылка в формуле целевой ячейки (рис. 7).

6. Определим ограничения, для этого щелчком по кнопке Добавить откроем диалоговое окно Добавление ограничения . Введем ограничения для ячеек E39, E40, E41. Ограничения можно задать как для изменяемых ячеек, так и для целевой ячейки, а также для других ячеек, прямо или косвенно присутствующих в модели (рис. 8, 9).

Р и с. 8. Р и с. 9.

7. Щелчком на кнопке Параметры откроем диалоговое окно Параметры поиска решения . В данном окне выберем линейную модель и неотрицательные значения (неотрицательные значения для ячеек С40 и С41 можно было также установить при определении ограничений). Подробнее узнать о задаваемых параметрах можно щелкнув на кнопке Справка (рис. 10).

8. После того как все параметры и ограничения заданы, запускаем поиск решения, щелкнув на кнопке Выполнить (рис. 9). По мере того как идет поиск, отдельные его шаги отражаются в строке состояния. Когда поиск будет закончен, в таблицу будут внесены новые значения и на экране появится диалоговое окно Результаты поиска решения , сообщающие о завершении операции (рис. 11).

Решение найдено. Все ограничения и условия оптимальности выполнены. Сохраним найденное решение. В этом случае таблица будет обновлена. В случае необходимости всегда можно будет восстановить исходные данные с помощью отчета. Для выбора типа отчета достаточно выделить название нужного отчета в списке Тип отчета (или несколько названий, удерживая нажатой клавишу Сtrl ). Они будут вставлены на отдельных листах в рабочую книгу перед листом с исходными данными.

Предлагаемые отчеты содержат следующую информацию:

отчет Результаты содержит сведения о начальных и текущих значениях целевой ячейки и изменяемых ячеек, а также о соответствии значений заданным ограничениям;

отчет Устойчивость отражает найденный результат, а также нижние и верхние предельные значения для изменяемых ячеек;

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

Если планируется использовать созданную модель в дальнейшем, найденное решение можно сохранить как сценарий. Для этого в диалоговом окне Результаты поиска решения необходимо щелкнуть на кнопке Сохранить сценарий .

Аналогично Поиск решения осуществляется в OpenOffice.org Calc.

Задание

1. Решить задачи 2 и 3 графическим методом.

2. Решить задачи 2 и 3 в редакторе Microsoft Excel или OpenOffice.org Calc используя встроенную функцию Поиск решения .

3. Сравнить и проанализировать полученные результаты.

4. Ответить на контрольные вопросы.

5. Оформить отчет.

Задача 2. Фармацевтическая фирма Ozark ежедневно производит не менее 800 фунтов некой пищевой добавки – смеси кукурузной и соевой муки, состав которой представлен в таблице 2.

Таблица 2

Диетологи требуют, чтобы в пищевой добавке было не менее 30% белка и не более 5% клетчатки. Фирма Ozark хочет определить рецептуру смеси минимальной стоимости с учетом требований диетологов.

Задача 3. Предприятие, специализирующееся на производстве трикотажного полотна двух видов, использует для своего производства четыре вида сырья (шерстяную, хлопковую, вискозную, и акриловую нити), запасы которого на планируемый период составляют соответственно 80, 80, 260 и 410 бобин. В приведенной ниже таблице даны технологические коэффициенты, т.е. расход каждого вида сырья на производство одного метра каждого вида трикотажа.

Таблица 3

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

Контрольные вопросы

1. Что означает составить математическую модель ЗЛП?

2. Из каких этапов состоит графический метод решения ЗЛП?

3. Какова геометрическая интерпретация решения системы линейных неравенств с двумя переменными?

4. Как определяется направление наискорейшего возрастания целевой функции?

5. Какое решение называется оптимальным решением ЗЛП?

6. В каком случае ЗЛП имеет множество решений?

7. При каких условиях ЗЛП может быть неразрешима?

8. Как установить модуль Поиск решения ?

9. Для чего предназначена кнопка Предположить в окне Поиск решения ?

10. Какие типы отчетов можно получить при решении ЗЛП с помощью встроенной функции Поиск решения ?

Лабораторная работа №2

Симплексный метод. Задача определения оптимального плана выпуска продукции. Использование встроенных функций редакторов Microsoft Excel и OpenOffice.org Calc для построения математической модели и решения ЗЛП.

Цель лабораторного занятия:

Приобретение навыков решения ЗЛП симплекс-методом. Освоение приемов записи математической модели ЗЛП с большим количеством неизвестных в табличных редакторах Microsoft Excel и OpenOffice.org Calc с помощью встроенной функций СУММПРОИЗВ. Приобретение навыков решения ЗЛП с большим количеством неизвестных с помощью функции Поиск решения .

Задачи лабораторного занятия:

1. Освоение симплекс-метода решения ЗЛП.

2. Построение математической модели задачи в табличных редакторах Microsoft Excel и OpenOffice.org Calc с помощью встроенной функций СУММПРОИЗВ.

3. Нахождение максимума (минимума) целевой функции с помощью команды Поиск решения .

4. Анализ полученных результатов.

5. Оформление отчета.

1. Краткие теоретические сведения.

2. Решение ЗЛП симплекс методом без использования табличных редакторов.

3. Решение ЗЛП на определение оптимального плана выпуска продукции в Microsoft Excel и OpenOffice.org Calc с помощью встроенной функции Поиск решения .

4. Задание.

5. Контрольные вопросы.

Краткие теоретические сведения

В основу симплекс-метода (симплексного метода) легла идея последовательного улучшения решения.

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

Реализация симплекс-метода предусматривает содержание трех основных элементов:

1. Определение какого-либо первоначального допустимого базисного решения задачи (базисное решение называется допустимым, если значения, входящих в него переменных неотрицательны);

2. Правила перехода к лучшему (точнее, не худшему) решению;

3. Критерий проверки оптимальности найденного решения.

Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений.

Практические расчеты при решении прикладных задач симплексным методом выполняются в настоящее время с помощью компьютерных программ, таких как табличный процессор Microsoft Excel, пакеты прикладных программ MathCAD, Math Lab и др. Однако, если расчеты осуществляются вручную, удобно использовать так называемые симплексные таблицы.

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

Инструментом для решений задач оптимизации в MS Excel служит надстройка «Поиск решения». Процедура поис­ка решения позволяет найти оптимальное значение фор­мулы, содержащейся в ячейке, которая называется целе­вой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во вли­яющих ячейках.

Если данная надстройка установлена, то «Поиск реше­ния»запускается из меню «Сервис». Если такого пункта нет, следует выполнить команду «Сервис - Надстройки...» и вы­ставить флажок против надстройки «Поиск решения».

Решение задачи оптимизации состоит из трёх этапов.

A. Создание модели задачи оптимизации.

B. Поиск решения задачи оптимизации.

C. Анализ найденного решения задачи оптимизации.

Рассмотрим подробнее эти этапы.

Этап А.

На этапе создания модели вводятся обозначения неиз­вестных, на рабочем листе заполняются диапазоны исход­ными данными задачи, вводится формула целевой функ­ции.

Этап В.

Команда «Сервис - Поиск решения» открывает диалоговое окно «Поиск решения», в котором, в свою очередь, имеются следующие поля:

«Установить целевую ячейку» - служит для указания целе­вой ячейки, значение которой необходимо максими­зировать, минимизировать или установить равным за­данному числу. Эта ячейка должна содержать форму­лу.

«Равной» - служит для выбора варианта оптимизации зна­чения целевой ячейки (максимизация, минимизация или подбор заданного числа). Чтобы установить чис­ло, введите его в поле.

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

«Предположить» - используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле «Установить целевую ячейку». Результат поиска отображается в поле «Изменяя ячейки».

«Ограничения» - служит для отображения списка гранич­ных условий поставленной задачи.

«Добавить» - служит для отображения диалогового окна «Добавить ограничение».

«Изменить» - служит для отображения диалоговое окна «Изменить ограничение».

«Удалить» – служит для снятия указанного ограничения.

«Выполнить» – служит для запуска поиска решения по­ставленной задачи.

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

«Параметры» - служит для отображения диалогового окна «Параметры поиска решения», в котором можно загрузить или сохранить оптимизируемую модель и ука­зать предусмотренные варианты поиска решения.

«Восстановить» - служит для очистки полей окна диалога и восстановления значений параметров поиска ре­шения, используемых по умолчанию.

Для решения задачи оптимизации выполните следую­щие действия.

1. В меню «Сервис» выберите команду «Поиск решения».

2. В поле «Установить целевую ячейку» введите адрес или имя ячейки, в которой находится формула оптимизируемой модели.

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

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

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

4. В поле «Изменяя ячейки» введите имена или адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.

Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку «Предположить».

5. В поле «Ограничения» введите все ограничения, накладываемые на поиск решения.

6. Нажмите кнопку «Выполнить».

Чтобы восстановить исходные данные, установите пере­ключатель в положение «Восстановить исходные значения».

Этап С.

Для вывода итогового сообщения о результате решения используется диалоговое окно «Результаты поиска реше­ния».

Диалоговое окно «Результаты поиска решения» содер­жит следующие поля:

«Восстановить исходные значения» - служит для восста­новления исходных значений влияющих ячеек моде­ли.

«Отчеты» - служит для указания типа отчета, размещаемо­го на отдельном листе книги.

«Результаты» - используется для создания отчета, состоя­щего из целевой ячейки и списка влияющих ячеек модели, их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях.

«Устойчивость» - используется для создания отчета, содер­жащего сведения о чувствительности решения к ма­лым изменениям в формуле (поле «Установить целе­вую ячейку», диалоговое окно «Поиск решения») или в формулах ограничений.

«Ограничения» - используется для создания отчета, состоя­щего из целевой ячейки и списка влияющих ячеек модели, их значений, а также нижних и верхних границ. Такой отчет не создается для моделей, зна­чения в которых ограничены множеством целых чи­сел. Нижним пределом является наименьшее значе­ние, которое может содержать влияющая ячейка, в то время как значения остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограни­чениям. Соответственно, верхним пределом называ­ется наибольшее значение.

«Сохранить сценарий» - служит для отображения диало­гового окна Сохранение сценария, в котором мож­но сохранить сценарий решения задачи, чтобы ис­пользовать его в дальнейшем с помощью диспетчера сценариев MS Excel.

Одной из возможных задач и моделей линейной оптимизации является задача о планировании производства.

Предприятие должно производить изделия видов: , причем количество каждого выпускаемого изделия не должно превысить спрос и одновременно не должно быть меньше за­планированных величин соответственно. На изготовление изделий идет m видов сырья , за­пасы которых ограничены соответственно величинами Известно, что на изготовление i -ro изделия идет единиц j -го сырья. Прибыль, получаемая от реализации изделий равна соответственно . Требуется так спланировать производство из­делий, чтобы прибыль была максимальной и при этом выполнялся план на производство каждого изделия, но не превышался спрос на него.

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

Если данная надстройка установлена, то Поиск реше­ния запускается из меню Сервис . Если такого пункта нет, следует выполнить команду Сервис → Надстройки... и вы­ставить флажок против надстройки
Поиск решения (рис.2.1).

Команда Сервис → Поиск решения открывает диалоговое окно «Поиск решения» .

В окне Поиск решения имеются следующие поля:

Установить целевую ячейку – служит для указания целевой ячейки, значение которой необходимо максими­зировать, минимизировать или установить равным за­данному числу. Эта ячейка должна содержать формулу .

Равной – служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или Подбор заданного числа). Чтобы установить число, введите его в поле.

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

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

Ограничения – служит для отображения списка граничных условий поставленной задачи.

Добавить - служит для отображения диалогового окна Добавить ограничение.

Изменить - Служит для отображения диалоговое окна Изменить ограничение.

Удалить - Служит для снятия указанного ограничения.

Выполнить – Служит для запуска поиска решения поставленной задачи.

Закрыть – Служит для выхода из окна диалога без запус­ка поиска решения поставленной задачи.

Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения.

Восстановить – Служит для очистки полей окна диалога и восстановления значений параметров поиска ре­шения, используемых по умолчанию.

Для решения задачи оптимизации выполните следующие действия.

1. В меню Сервис выберите команду Поиск решения.

2. В поле Установить целевую ячейку введите адрес или имя ячейки, в которой находится формула оптимизируемой модели.

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

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

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

4. В поле Изменяя ячейки введите имена или адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.

Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку Предположить.

5. В поле Ограничения введите все ограничения, накладываемые на поиск решения.

6. Нажмите кнопку Выполнить.

Чтобы восстановить исходные данные, установите переключатель в положение

Этап С. Анализ найденного решения задачи оптимизации.

Для вывода итогового сообщения о результате решения используется диалоговое окно Результаты поиска решения.

Диалоговое окно Результаты поиска решения содержит следующие поля:

Восстановить исходные значения – служит для восста­новления исходных значений влияющих ячеек моде­ли.

Отчеты – служит для указания типа отчета, размещаемого на отдельном листе книги.

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

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

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

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

2.4 Задача о планировании производства

Постановка задачи. Предприятие должно производить изделия n видов: и 1 ,и 2 ,...и п , причем количество каждого выпускаемого изделия не должно превысить спрос β 1 , β 2 ,..., β n и одновременно не должно быть меньше запланированных величин b 1 ,b 2 ,...,b n соответственно. На изготовление изделий идет m видов сырья s l ,s 2 ,...,s m , запасы которых ограничены соответственно величинами γ 1 , γ 2 ,..., γ m . Известно, что на изготовление i -го изделия идет а ij единиц j -го сырья. Прибыль, получаемая от реализации изделий u 1 , ,и 2 ,...и п равна соответственно с 1 ,с 2 ,...,с п. Требуется так спланировать производство изделий, чтобы прибыль была максимальной и при этом выполнялся план на производство каждого изделия, но не превышался спрос на него.

Математическая модель. Обозначим за х 1 ,х 2 ,...х n количества единиц изделий u 1 , ,и 2 ,...и п, выпускаемых предприятием. Прибыль, приносимая планом (целевая функция), будет равна:

z = z(x 1 ,x 2 ,...,x n) = с 1 x 1 + c 2 x 2 + ...+c n x n → max. Ограничения на выполнение плана запишется в виде: х i ≥β i для i = 1,2,...,n Чтобы не превысить спрос, надо ограничить выпуск изделий: x i ≤β i для i = 1,2,...n. И, наконец, ограничения на сырье запишутся в виде системы неравенств:

α 11 x 1 + α 12 x 2 +...+ α 1n x n ≤b 1

α 21 x 1 + α 22 x 2 +...+ α 2n x n ≤b 2

................................................

α m1 x 1 + α m2 x 2 +...+ α mn x n ≤b m

при условии, что х 1 ,х 2 ,...х п неотрицательны.

Пример 2.1:

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

Условие задачи. Предприятие выпускает два вида железобетонных изделий: лестничные марши и балконные плиты. Для производства одного лестничного марша требуется израсходовать 3,5 куб.м. бетона и 1 упаковку арматуры, а для производства плиты - 1 куб.м. бетона и 2 упаковки арматуры. На каждую единицу продукции при­ходится 1 человеко-день трудозатрат. Прибыль от прода­жи 1 лестничного марша составляет 200 руб., а одной плиты - 100 руб. На предприятии работает 150 человек, причем известно, что в день предприятие производит не более 350 куб.м. бетона и завозится не более 240 упаковок арматуры. Требуется составить такой производственный план, чтобы прибыль от производимой продукции была максимальной.

Решение.

1. На листе рабочей книги MS Excel заполните таблицу параметров задачи (рис. 2.2).

2. Создайте модель задачи и заполните ячейки для значений переменных (первоначально ячейки х { и х г заполняются произвольными числовыми значениями, например, значением 10), целевой функции (ячейка содержит формулу) и ограничений (ячейки содержат формулы)
(рис. 2.2)

3. Выполните команду Сервис Поиск решения и установите необходимые значения в полях диалогового окна Поиск решения, добавляя ограничения в окне Добавление ограничений.

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

4. Нажмите на кнопку Выполнить и установите параметры в окне Результаты поиска решения (переключатель Сохранить найденное решение или Восстановить исходные значения и Тип отчета).

Замечание: В случае ошибок в формулах, ограничениях или неверных параметрах модели в данном окне могут появиться следующие сообщения: «Значения целевой ячейки не сходятся», «Поиск не может найти решения» или «Условия линейной модели не выполняются». При этом переключатель следует установить в положение Восстановить исходные значения, проверить данные на листе и процедуру поиска решения проделать заново.

5. В результате в ячейках с переменными задачи по­явятся значения, соответствующие оптимальному плану (80 лестничных маршей и 70 плит перекрытия в день), а в ячейке для целевой функции - значение прибыли (23 000 руб.), соответствующее данному плану (рис. 2.3)

6. Вслучае если полученное решение является удовлетворительным, можно сохранить оптимальный план и ознакомиться с результатами поиска, которые выводятся на отдельный лист.

Упражнение:

Упр. 2.1. Предприятие выпускает телевизоры, стереосистемы и акустические системы, используя общий склад комплектующих. Запасы шасси на складе составляют 450 шт., кинескопов – 250 шт., динамиков – 800 шт., блоков питания – 450 шт., плат – 600 шт. На каждое изделие расходуется количество комплектующих, указанное в таблице:

Прибыль от производства одного телевизора составляет 90 у.е, одной стереосистемы – 50 и аудиосистемы – 45. Необходимо найти оптимальное соотношение объемов выпуска изделий, при котором прибыль от производства всей продукции будет максимальной.

Ввод условий задачи состоит из следующих основных шагов:

Создание формы для ввода условий задачи.

Ввод исходных данных.

Ввод зависимостей из математической модели.

Назначение целевой функции.

ввод ограничений и граничных условий.

Ход решения задачи:

Форма для ввода условий задачи:

		Переменные
	Значение
	Коэффициент в целевой функции			(формула)
		Ограничения
		Коэффициенты в ограничениях				Правая часть ограничения

Поочередно в представленную форму заносятся коэффициенты целевой функции, ограничений, их знаки, формулы описания целевой функции и ограничений, представленные в математической модели задачи.

Для описания формулы целевой функции и ограничений используется диалоговое окно Мастер функций; категория функций – математические; функция СУММПРОИЗВ. (в диалоговом окне в массиве 1 указывается интервал ячеек значения переменной В3:С3, в массиве 2 – коэффициенты при этих переменных. В функции это интервал ячеек В4:С4, в ограничениях – В8:C8, В9:C9 и т.д.)

Решение задачи осуществляется с использованием команд Сервис, Поиск решения…

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

Целевая функция: Е4

Равная: max (min)

Изменяя ячейки: указывается месторасположения переменных (В3:C3)

Ограничения: с использованием клавиши Добавить записываются адреса ячеек с указанием условий ограничений (например: D8>= F8 и т.д.). Обязательным является ввод ограничения целочисленного решения.

Если при вводе задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это осуществляется с помощью команд Изменить.., Удалить.

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

Максимальное время: 100 сек

Предельное число итераций: 100

Относительная погрешность 0,000001

Допустимое отклонение: 5%

Устанавливаем флажок Линейная модель, что обеспечивает применение симплекс-метода.

В появившемся окне Поиск решения выполняем команду Выполнить.

Решение найдено, результат оптимального решения приведен в исходной таблице.

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

Используя данные прямой двойственной задачи, решите ее в системе Excel, с помощью следующих таблиц

Переменные

Ограничения

Вид ресурса	Коэффициенты в ограничениях		Левая часть ограничения (формула)		Правая часть ограничения