ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Наиболее простым и наглядным методом линейного программирования (ЛП) является графический метод. Он применяется для решения задач ЛП с двумя переменными. Рассмотрим задачу ЛП в стандартной форме:

max f(x₁, x₂, ..., x_n) = ,

, i = 1, 2, …, m,

x_j 0, j = 1, 2, …, n.

Положим n=2 и будем рассматривать задачу на плоскости. Пусть система неравенств совместна (имеет хотя бы одно решение).

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой а_i1х₁ + а_i2х₂ = b_i, i = 1, 2,…,m. Условия неотрицательности определяют полуплоскости с гра­ничными прямыми х₁ = 0, х₂ = 0 соответственно. Система со­вместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, где ко­ординаты каждой точки являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, ограниченным и неограни­ченным многоугольником.

Таким образом, геометрически ЗЛП представляет собой отыс­кание такой точки многоугольника решений, координаты которой доставляют линейной функции цели максимальное (минимальное) значение, причем допустимыми решениями являются все точки многоугольника решений.

Линейное уравнение описывает множество точек, лежащих на одной прямой. Линейное неравенство описывает некоторую об­ласть на плоскости. Определим, какую часть плоскости описыва­ет неравенство 2х₁+ Зх₂ 12.

Во-первых, построим прямую 2х₁ + Зх₂ = 12. Она проходит через точки (6; 0) и (0; 4). Для того чтобы определить, какая полуплоскость удовлетворяет неравенству, необходимо выбрать любую точку на графике, не принадлежащую прямой, и подставить ее координаты в неравенство. Если неравенство будет вы­полняться, то данная точка является допустимым решением, и полуплоскость, содержащая точку, удовлетворяет неравенству. Для подстановки в неравенство удобно использовать точку начала координат. Подставим х₁ = х₂ = 0 в неравенство 2х₁ + Зх₂ 12. Получим 2х0 + 3х0 12. Данное утверждение является верным, следовательно, неравенству 2х₁ + Зх₂ 12 соответствует нижняя полуплоскость, содержащая точку (0; 0). Это отражено на графике, изображенном на рис. 1.1.

Аналогично графически можно изобразить все ограничения задачи ЛП.

Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений, или областью определения. Необходимо помнить, что область допустимых решений удовлетворяет условиям неотрицательности (х_j 0, j = 1, 2, …, n). Координаты любой точки, принадлежащей области определения, являются допустимым решением задачи.

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

Этот вектор показывает направление наискорейшего измене­ния целевой функции. Прямая с₁х₁ + с₂х₂ = f(х₀), перпендикуляр­ная вектору-градиенту, является линией уровня целевой функции. В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине «а». Меняя значение «а», получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.

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

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

Графический метод решения ЗЛП состоит из следующих этапов.

1.Строится многоугольная область допустимых решений (ОДР) ЗЛП.

2.Строится вектор-градиент целевой функции (ЦФ) в какой-нибудь точке х₀, принадлежащей ОДР:

3. Линия уровня с₁х₁ + с₂х₂ = а (а - постоянная величина) - прямая, перпендикулярная вектору-градиенту , - передви­гается в направлении этого вектора в случае максимизации f(x₁, х₂) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точ­кой максимума f(x₁, х₂).

4. Для нахождения координат точки максимума достаточно решить два уравнения прямых, получаемых из соответствую­щих ограничений и дающих в пересечении точку максимума. Значение f(x₁, х₂), найденное в получаемой точке, является мак­симальным.

При минимизации (максимизации) функции f(x₁, х₂) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая, соответствующая линии уровня, при своем движении не покидает ОДР, то минимум (максимум) функ­ции f(x₁, х₂) не существует.

Если линия уровня параллельна какому-либо функциональ­ному ограничению задачи, то оптимальное значение ЦФ будет достигаться в любой точке этого ограничения, лежащей между двумя оптимальными угловыми точками, и, соответственно, любая из этих точек является оптимальным решением ЗЛП. Возможные ситуации графического решения задач ЛП представлены в табл. 1.3.

Таблица 1.3

№	Вид ОДР	Вид оптимального решения	Примечания
	Многоугольная замкнутая	Единственное решение
	Единственное решение
	Бесконечное множество решений
	Многоугольная	ЦФ не ограничена снизу
	ЦФ не ограничена сверху
	Многоугольная незамкнутая	Единственное решение
	Бесконечное множество решений
	Отрезок	Единственное решение

Рассмотрим графическое решение задач линейного программирования на следующем примере.

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

Намечается выпуск двух видов костюмов – мужских и женских. На женский костюм требуется 1м шерсти, 2м лавсана и 1 чел./день трудозатрат. На мужской костюм – 3,5м шерсти, 0,5м лавсана и 1 чел./день трудозатрат. Всего имеется 350м шерсти, 240м лавсана и 150 чел./дней трудозатрат. Требуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского – 20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.

Экономико-математическая модель задачи

Введем следующие обозначения: х₁ - число женских костюмов; х₂ – число мужских костюмов. Прибыль от реализации женских костюмов составляет 10х₁ , а от реализации мужских - 20х₂ , т.е. необходимо максимизировать целевую функцию:

= 10х₁ + 20х₂

Ограничения задачи имеют вид:

х₁ + х₂ 150,

2 х₁ + 0,5х₂ 240,

х₁ + 3,5х₂ 350,

х₂ 60,

х₁ 0.

Первое ограничение по труду х₁ + х₂ 150. Прямая х₁ + х₂ = 150 проходит через точки (150; 0) и (0; 150) (рис. 1.2).

Второе ограничение по лавсану 2 х₁ + 0,5х₂ 240. Прямая 2 х₁ + 0,5х₂ = 240 проходит через точки (120; 0) и (0; 480). Третье ограничение по шерсти х₁ + 3,5х₂ 350. Добавим четвертое ограничение по количеству мужских костюмов х₂ 60. Решением этого неравенства является полуплоскость, лежащая выше прямой х₂ = 60. На рис. 1.3 заштрихована область допустимых решений. Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными целевой функции, т.е.

Чтобы построить такой вектор, нужно соединить точку (10;20) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации – в противоположном направлении. Для удобства можно строить вектор, пропорциональный вектору . Так, на рис. 1.4 изображен вектор-градиент (30;60).

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

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

х₁ + 3,5х₂ = 350,

х₁ + х₂ = 150.

Отсюда легко записать решение исходной ЗЛП: max f(x) = 2300 и достигается при х₁ = 70 и х₂ = 80 (см. рис. 1.4).

1.3.ТЕХНОЛОГИЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ НАДСТРОЙКИ ПОИСК РЕШЕНИЯ В СРЕДЕ EXCEL

1.3.1. Общие сведения о работе с табличным процессором Excel

Рассмотрим некоторые аспекты работы с табличным процессором Excel, которые позволят упростить расчеты, необ­ходимые для решения оптимизационных задач. Табличный процессор - это программный продукт, предназначенный для ав­томатизации обработки данных табличной формы.

Элементы экрана Excel. После запуска Excel на экране появля­ется таблица, вид которой показан на рис 1.5.

Это изображение называют рабочим листом. Оно представляет собой сетку строк и столбцов, пересечения которых образуют пря­моугольники, называемые ячейками. Рабочие листы предназначены для ввода данных, выполнения расчетов, организации информа­ционной базы и т.п. Окно Excel отображает основные программные элементы: строку заголовка, строку меню, строку состояния, кноп­ки управления окнами.

Работа с формулами. В программах электронных таблиц формулы служат для выполнения множества разнообразных расчетов. С помощью Excel можно быстро создать формулу. Формула состоит из трех основных частей:

1) знака равенства;

2) совокупности значений или ссылок на ячейках, с которыми выполняются расчеты;

3) операторов.

4) Если знак равенства отсутствует, то Excel интерпретирует данные не как формулу, а как ввод данных в ячейку. Формулы можно вводить непосредственно в ячейку или в строку формул – как текст, так и число. При этом нужно выполнить следующие действия:

· выделить ячейку, которая должна содержать формулу и ввести знак (=);

· ввести оператор или знак действия;

· выделить другую ячейку, включаемую в формулу;

· опять ввести оператор и так далее, пока не завершится ввод формулы;

· нажать на клавишу Enter.

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

Использование в формулах функций. Чтобы облегчить ввод формул, можно воспользоваться функциями Excel. Функции - это встроенные в Excel формулы. Excel содержит множество формул. Они сгруппированы по различным типам: логические, математи­ческие, инженерные, статистические и др.

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

Различные функции выполняют разные типы вычислений по определенным правилам. Когда функция является единичным объектом в ячейке рабочего листа, она начинается со знака (=), далее следует название функции, а затем — аргументы функции, заключенные в скобки.

Поиск решения - это надстройка Excel, которая позволяет решать оптимизационные задачи. Если в меню Сервис отсутствует коман­да Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду Сервис => Надстройки и активизируйте над­стройку Поиск решения. Если же этой надстройки нет в диалоговом окне Надстройки, то вам необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и уда­ление программ и с помощью программы установки Excel (или Office) установить надстройку Поиск решения.

После выбора команд Сервис => Поиск решения появится диало­говое окно Поиск решения.

В диалоговом окне Поиск решения есть три основных пара­метра;

• Установить целевую ячейку.

• Изменяя ячейки.

• Ограничения.

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

Второй важный параметр средства Поиск решения - это пара­метр Изменяя ячейки. Здесь указываются ячейки, значения в которых будут изменяться для того, чтобы оптимизировать ре­зультат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К этим ячейкам предъявляется два основ­ных требования: они не должны содержать формул и изменение их значений должно отражаться на изменении результата в целе­вой ячейке. Другими словами, целевая ячейка зависит от изменя­емых ячеек.

Третий параметр, который нужно вводить на вкладке Поиск решения, - это ограничения.

Для решения задачи необходимо:

1) указать адреса ячеек, в которые будет помещен результат реше­ния (изменяемые ячейки);

2) ввести исходные данные;

3) ввести зависимость для целевой функции;

4) ввести зависимости для ограничении,

5) запустить команду Поиск решений;

6) назначить ячейку для целевой функции (установить целевую ячейку);

7) ввести ограничения;

8) ввести параметры для решения ЗЛП.

Рассмотрим технологию решения, используя условия примера 1.1 (задача о костюмах).

Экономико-математическая модель задачи

Пусть х₁ — число женских костюмов; х₂ — число мужских костюмов,

= 10 х х₁ + 20 х х₂ max

Ограничения задачи имеют вид:

х₁ + х₂ 150 - ограничение по труду;

2 x х₁ + 0,5 х х₂ 240 - ограничение по лавсану;

х₁ + 3,5 х х₂ 350 - ограничение по шерсти;

х₂ 60 - ограничение по мужским костюмам;

х₁ 0 - ограничение по женским костюмам.

Решение

1. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).

Обозначьте через x₁, х₂ количество костюмов каждого типа. В нашей задаче оптимальные значения вектора = (х₁, х₂) будут помещены в ячейках А2:В2, оптимальное значение целевой функ­ции - в ячейке СЗ.

2. Ввести исходные данные.

Введите исходные данные задачи, как показано на рис. 1.6.

3. Ввести зависимость для целевой функции.

· Поместить курсор в ячейку «СЗ», произойдет выделение ячейки.

· Поместить курсор на кнопку Мастер функций, расположенную на панели инструментов.

· Ввести Enter. На экране появляется диалоговое окно Мастер функ­ций шаг 1 из 2.

· В окне Категория выбрать категорию Математические.

· В окне Функции выбрать строку СУММПРОИЗВ (рис. 1.7). На экране

· появляется диалоговое окно СУММПРОИЗВ (рис. 1.8).

· В строку Массив 1[2] ввести А2:В2.

· В строку Массив 2 ввести АЗ:ВЗ.

Массив 1 будет использоваться при вводе зависимостей для ограничений, поэтому на этот массив надо сделать абсолютную ссылку[3]. На рис. 1.9 показано, что в ячейку СЗ введена функция.

5. Ввести зависимости для ограничений (рис 1.10).

· Поместить курсор в ячейку СЗ.

· На панели инструментов кнопка Копировать в буфер.

· Поместить курсор в ячейку С4.

· На панели инструментов кнопка Вставить из буфера.

· Поместить курсор в ячейку С5.

· На панели инструментов кнопка Вставить из буфера.

· Поместить курсор в ячейку Сб.

· На панели инструментов кнопка Вставить из буфера.

· Поместить курсор в ячейку С7.

· На панели инструментов нажать кнопку Вставить из буфера. (Содержимое ячеек С4-С7 необходимо проверить. Они обяза­тельно должны содержать информацию, как это показано для примера на рис. 1.11; в качестве примера представлено содер­жимое ячейки С5.)

· В строке Меню указатель мышки поместить на Сервис. В развер­нутом меню выбрать команду Поиск решения. Появляется диа­логовое окно Поиск решения (рис. 1.12).

5. Запустить команду Поиск решения.

6.Назначить ячейку для целевой функции (установить целевую ячейку), указать адреса изменяемых ячеек.

7.

· Поместить курсор в строку Установить целевую ячейку.

· Ввести адрес ячейки $С$3.

· Ввести тип целевой функции в зависимости от условия вашей задачи. Для этого отметьте, чему равна целевая функция - Максимальному значению или Минимальному значению.

· Поместить курсор в строку Изменяя ячейки.

· Ввести адреса искомых переменных А$2:В$2 (рис. 1.13).

7. Ввести ограничения.

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

· В строке Ссылка на ячейку ввести адрес $С$4.

· Ввести знак ограничения.

· В строке Ограничение ввести адрес $D$4 (рис. 1.14).

· Поместить указатель мыши на кнопку Добавить. На экране вновь появится диалоговое окно Добавление ограничения.

· Ввести остальные ограничения задачи по вышеописанному алгоритму.

· После введения последнего ограничения нажать на кнопку ОК. На экране появится диалоговое окно Поиск решения с введенны­ми условиями (рис. 1.15).

8. Ввести параметры для решения задачи линейного программирования.

· В диалоговом окне поместить указатель мышки на кнопку Пара­метры. На экране появится диалоговое окно Параметры поиска решения (рис. 1.16).

· Установить флажки в окнах Линейная модель (это обеспечит применение симплекс-метода) и Неотрицательные значения.

· Поместить указатель мыши на кнопку ОК. На экране появится диалоговое окно Поиск решения.

· Поместить указатель Мыши на кнопку Выполнить.

Через непродолжительное время появятся диалоговое окно Результаты поиска решения и исходная таблица с заполненными ячейками АЗ:ВЗ для значений х_i и ячейка СЗ с максимальным значением целевой функции (рис. 1.17).

Если указать тип отчета Устойчивость, то можно получить до­полнительную информацию об оптимальном решении (рис. 1.18).

В результате решения задачи был получен ответ: необходимо сшить 70 шт. женских костюмов и 80 шт. мужских костюмов, чтобы получить максимальную прибыль 2300 у.е.

1.4. ДВОЙСТВЕННОСТЬ В ЗАДАЧАХ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. АНАЛИЗ ПОЛУЧЕННЫХ ОПТИМАЛЬНЫХ РЕШЕНИЙ

В 1975 г. наш соотечественник Л.В. Канторович был удостоен Нобелевской премии по экономике (совместно с американским экономистом Т. Купмансом) за разработку теории оптимального использования ресурсов (см. Приложение 1).

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

Переменные двойственной задачи y_i называются объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.

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

Двойственная задача по отношению к исходной составляется согласно следующим правилам:

1) целевая функция исходной задачи формулируется на макси­мум, а целевая функция двойственной задачи - на минимум, при этом в задаче на максимум все неравенства в функцио­нальных ограничениях имеют вид ( ), в задаче на минимум — вид ( );

2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная мат­рица А^Т в двойственной задаче получаются друг из друга транс­понированием;

3) число переменных в двойственной задаче равно числу функци­ональных ограничений исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной;

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

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

Модель исходной (прямой) задачи в общем виде может быть записана следующим образом:

i=1,2, …, m,

x_j 0, j= 1, 2,…, n,

а модель двойственной задачи -

у_j 0.

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

Первая теорема двойственности. Для взаимно двойственных за­дач имеет место один из взаимоисключающих случаев.

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

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

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

4. Обе из рассматриваемых задач имеют пустые допустимые мно­жества.

Вторая теорема двойственности (теорема о дополняющей неже­сткости). Пусть = (x₁,х₂,..., х_п) — допустимое решение прямой задачи, a = (у₁,у₂,…,у_т) — допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соот­ветственно прямой и двойственной задач, необходимо и достаточ­но, чтобы выполнялись следующие соотношения:

(1.4)

(1.5)

Условия (1.4) и (1.5) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное реше­ние другой задачи.

Рассмотрим еще одну теорему, выводы которой будут исполь­зованы в дальнейшем.

Теорема об оценках. Значения переменных y_i в оптимальном реше­нии двойственной задачи представляют собой оценки влияния сво­бодных членов b_i системы ограничений (неравенств) прямой задачи на величину

Решая ЗЛП симплекс-методом, мы одновременно решаем двой­ственную ЗЛП. Переменные двойственной задачи y_i называют объективно обусловленными оценками.

Рассмотрим экономическую интерпретацию двойственной за­дачи на примере задачи о коврах.

Пример 1.2. Используя постановку задачи о коврах, выполнить следующие задания.

1. Сформулировать экономико-математическую модель задачи о коврах на максимум общей стоимости продукции, используя данные табл. 1.1.

2. Используя Поиск решения, найти такой план выпуска продук­ции, при котором общая стоимость продукции будет макси­мальной.

3. Сформулировать экономико-математическую модель двой­ственной задачи к задаче о коврах.

4. Найти оптимальный план двойственной задачи, используя теоремы двойственности, пояснить равенство нулю Х₁ и Х₄.

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

6. Определить, как изменится общая стоимость и план выпуска продукции при увеличении запаса ресурса труб на 12 ед.

Решение

1. Сформулируем экономико-математическую модель задачи.

Обозначим через Х₁, Х₂, Х₃, Х₄ число ковров каждого типа. Целевая функция имеет вид

F(X) = ЗХ₁ + 4Х₂ + ЗХ₃ + Х₄ max,

а ограничения по ресурсам

7Х₁ + 2Х₂ + 2Х₃ + 6Х₄ 80,

5Х₁ + 8Х₂ + 4Х₃ + ЗХ₄ 480,

2Х₁ +4Х₂ + Х₃ + 8X₄ 130,

Х₁, X₂, X₃, Х₄ 0.

2. Поиск оптимального плана выпуска.

Решение задачи выполним с помощью надстройки Excel Поиск решения. Технология решения задачи была подробно рассмотрена в задаче о костюмах. В нашей задаче оптимальные значения вектора Х=( Х₁, X₂, X₃, Х₄) будут помещены в ячейках ВЗ:ЕЗ, оптимальное значение целевой функции - в ячейке F4.

Введем исходные данные. Сначала опишем целевую функцию с помощью функции - СУММПРОИЗВ (рис. 1.19). А потом введем данные для левых частей ограничений. В Поиске решения введем направление целевой функции, адреса искомых переменных, до­бавим ограничения. На экране появится диалоговое окно Поиск решения с введенными условиями (рис. 1.20).

После ввода параметров для решения ЗЛП следует нажать кнопку Выполнить. На экране появится сообщение, что решение найдено (рис. 1.21).

Полученное решение означает, что максимальный доход 150 тыс. руб. фабрика может получить при выпуске 30 ковров второго вида и 10 ковров третьего вида. При этом ресурсы «труд» и «оборудование» будут использованы полностью, а из 480 кг пряжи (ресурс «сырье») будет использовано 280 кг.

Создание отчета по результатам поиска решения. Excel позволяет представить результаты поиска решения в форме отчета (табл. 1.4). Существует три типа таких отчетов:

· Результаты (Answer). В отчет включаются исходные и конечные значения целевой и изменяемых ячеек, дополнительные све­дения об ограничениях.

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

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

Таблица 1.4