Дайте понятие проблемы

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

Что понимается под критериями выбора?

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

Какое решение можно считать оптимальным?

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

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

Условием оптимальности при отыскании максимального значения целевой функции симплексным методом является отсутствие отрица­тельных коэффициентов в Z-строке симплексной таблицы, т.е. все сво­бодные члены (элементы столбца под 1) в симплекс-таблице неотрица­тельны, в Z-строке (кроме свободного члена) все коэффициенты при пе­ременных также неотрицательны, то полученное решение является опор­ным и оптимальным.

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

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

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

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

Если же в разрешающем столбце (столбец с отрицательным коэффи­циентом Z-строки) нет положительных коэффициентов, то целевая функция не ограничена сверху и оптимального решения не существует.

Пример 4.3

Для реализации трех видов товаров предприятие располагает тремя видами ресурсов b 1 = 180, b 2 = 50 и b 3 = 40 . Для продажи первой группы товаров на одну тысячу рублей товарооборота расходуется ресурсов пер­вого вида в количестве а 11 = 3 единицы, ресурсов второго вида а 21 = 2 еди­ницы и третьего а 31 = 2 единицы. Для продажи второй и третьей групп товаров на 1 тысячу рублей товарооборота расходуется соответственно:

a 2 l = 6 единиц, a l 3 = 4 единицы, а 22 = 1 единицу, a 23 = 2 единицы, а 32 =3 еди­ницы, а 33 = 1 единицу.

Прибыль, полученная от продажи трех групп товаров на единицу то­варооборота, составляет: с 1 = 6, с 2 = 5 и с 3 = 5.

Определить максимальную прибыль предприятия.

Математическая модель задачи имеет вид:

при ограничениях-неравенствах:

(4.21)

и условиях:

Решение

1. Вводим зависимые переменные y i ≥ 0 удовлетворяющие условиям:

и перепишем ограничения (4.16) и целевую функцию Z (4.20) в виде:

2. Составляем симплексную табл. №1, включая в нее независимые пере­менные -x 1 -x 2 ,-х 3 , на верху таблицы, зависимые переменные y 1 ,y 2 , у 3 и целевую функцию Z, записывая в левом столбце таблицы с соот­ветствующими знаками у коэффициентов - a ik . Ограничения на знак в таблицу не включаем.

Первоначальный план (исходное решение) является опорным, так как при х 1 = х 2 = х 3 = 0 (все переменные, расположенные на верху таблицы, равны нулю) и зависимые переменные у 1 = 180, у 2 = 50, у ъ = 40 удов­летворяют условиям у i ≥ 0 .

3. Определяем оптимальное (максимальное) решение задачи линейного программирования. Находим разрешающий элемент a rs . В качестве разрешающего выбираем столбец, содержащий наиболь­ший отрицательный по абсолютной величине коэффициент Z-строки, равный «-6». В табл. № 1 указано вертикальной стрелкой. Разрешающую строку определяем из условия min

Такой строкой будет третья (указана горизонтальной стрелкой). Сле­довательно a rs = а 31 = 2 .

Выполним шаг модифицированного жорданова исключения с раз­решающим элементом а 31 = 2 , отмечено квадратиком. Получим табл. №2 в виде:

Разрешающий элемент а 31 = 2 , заменяем обратной величиной, рав­ной 1/2. Все остальные элементы разрешающего столбца делим на «-2», получаем

Остальные элементы разрешающей строки делим на 2 и получаем:

Все элементы табл. №2 получаем, вычисляя по правилу «прямо­угольника».

Вычисления элементов таблицы запишем по строкам:

Решение, представленное табл. № 2, не является оптимальным, так как в Z-строке имеется отрицательный коэффициент, равный -2. Выпол­ним шаг модифицированного жорданова исключения с разрешающим элементом а 23 = 1 (третий столбец - разрешающий, а строка определена из условия min

и получим табл. № 3 в виде:

Вычисления для заполнения табл. № 3 выполняем, начиная с разре­шающих строки и столбца, а затем определяем элементы столбца сво­бодных членов и Z-строки. Так как свободные члены и коэффициенты Z-строки неотрицательны, то решение является оптимальным. Осталь­ные элементы симплекс-таблицы можно не вычислять.

Решение задачи выписываем из табл. № 3:

у 3 = х 2 = у 2 = 0 , так как все переменные, расположенные на верху табли­цы равны нулю. Тогда переменные, находящиеся в левом столбце таблицы равны соответствующим значениям свободных членов (элементы в столбце под «1»), то есть

Проверка.

Пример 4.4

Для заданной целевой линейной функции

Найти максимальное значение при линейных ограничениях-неравен­ствах:

и условиях:

Решение

1. Введем зависимые переменные, удовлетворяющие условиям у i > 0 , и перепишем систему ограничений (4.26) и целевую функцию (4.25) в виде:

2. Составляем симплексную табл. № 1, включая в нее зависимые y j не­зависимые переменные -х к (4.28) и целевую функцию Z (4.29). Огра­ничения на знак переменных х к в таблицу не включаем. Номера таб­лиц будем указывать в левом верхнем углу:

Исходный (первоначальный) план является неопорным, так как в третьей строке у з = -5 (свободный член, т.е. элемент табл. № 1 в столб­це под 1 величина отрицательная).

3. Определяем опорное решение, выполняя шаг модифицированного жорданова исключения с разрешающим элементом а 33 = -1 выбран­ным в соответствии с правилами, изложенными выше, т.е. в качест­ве разрешающего столбца берем коэффициент в третьей строке (свободный член равен -5) под переменной х 3 , а разрешающей будет строка с наименьшим положительным отношением свободных чле­нов к соответствующим коэффициентам разрешающего столбца, т.е.

Решение задачи, представленное табл. № 2, показывает, что план яв­ляется опорным, но неоптимальным, так как в Z-строке все коэффи­циенты отрицательные.

4. Определяем оптимальное решение, выполняя шаг модифицирован­ного жорданова исключения с разрешающим элементом а 21 = 1 . В ка­честве разрешающего столбца берем наибольший по модулю отрица­тельный коэффициент - 16, т.е. столбец под переменной х 1 (отмечен­ный вертикальной стрелкой), а разрешающей будет строка с единст­венным положительным коэффициентом равным 1. Следовательно, a 21 = 1 , а решение будет представлено табл. № 3:

Решение задачи, представленное табл. № 3, является оптимальным, так как все коэффициенты Z-строки - положительные величины. Выписываем решения задачи из табл. № 3:

Проверка зависимых переменных и целевой функции:

Пример 4.5

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

удовлетворяющие линейным ограничениям-неравенствам:

И условиям:

Решение

1. Введем зависимые переменные y t > 0 и ограничения (4.31) перепишем в виде:

Исключаем из табл. № 1 свободную независимую переменную x v вы­бирая в качестве разрешающего элемента любой коэффициент в этом столбце (под переменной х х ), так как согласно правилу выбора разрешаю­щего элемента при исключении свободной переменной ограничений на выбор его нет.

Разрешающий элемент отмечен квадратиком, а соответствующие раз­решающие строка и столбец указаны стрелками. Выполним шаг модифи­цированного жорданова исключения с разрешающим элементом а 31 = 1 и получаем табл. № 2:

(4.33)
Так как в случае равенства нулю отношений свободных членов к ко­эффициентам разрешающего столбца в качестве разрешающего элемента берем коэффициент с положительным знаком, получаем табл. № 4:

Полученное решение не является оптимальным, так как в Z-строке имеется отрицательный коэффициент, равный -8. Принимаем столбец с этим коэффициентом в качестве разрешающего, а строку определяем из условия:

Так как в отношении коэффициент, стоящий в знаменателе, отри­цательный, то в качестве разрешающей строки принимаем третью строку с коэффициента равным 7. Выполним шаг модифицированного жордано­ва исключения с а 31 = 7 и табл. № 5 будет иметь вид (вычисляем элементы разрешающего столбца, разрешающей строки, столбца свободных членов и Z-строки. Остальные элементы табл. № 5 можно не вычислять).

План, представленный табл. № 5, является оптимальным. Выписыва­ем решения задачи:

Вычисляем значение свободной переменной х 1 на основании (4.33):

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

Пример 4.6

Для заданной целевой функции найти максимальное значение:

и условиях:

Решение

1. Вводим зависимые переменные и перепишем условие задачи (4.34)-(4.36) в виде:

(4.38)

2. Составляем симплексную табл. № 1:

3. Исключаем свободную независимую переменную х 3 , выполняя шаг модифицированного жорданова исключения с разрешающим элемен­том а 43 = 1 . Получаем табл. № 2:

Выписываем значение переменной х 3:

и вычеркиваем четвертую строку в табл. № 2.

Получаем табл. № 3 в виде:

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

Следовательно, выполним шаг модифицированного жорданова ис­ключения с разрешающим элементом а 11 = -8 , получим табл. № 4:

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

Решение, полученное в виде табл. № 5, является опорным, но не оп­тимальным, поскольку в Z-строке коэффициент равный – 15/8 в первом столбце отрицательный, но в этом столбце нет положительных коэффи­циентов. Следовательно, целевая функция ограничений на максимум не имеет.

Управление производством предполагает постоянное принятие решений. Каждое принятое решение выбирается из определенного множества допустимых альтернатив. Задача менеджмента в данном случае состоит в том, чтобы выбрать оптимальное решение, то есть то решение, которое по определенным признакам предпочтительнее остальных. Решение будет считаться оптимальным, если оно приведет к максимально возможному положительному эффекту (например, росту прибыли предприятия).

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

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

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

1. пакет «Чистое стекло » стоимостью 3600 руб., в который входит комплекс работ по диагностике и осмотру автомобиля, очистка внутренней поверхности стекол автомобиля с применением специального спрея (плюс один флакон спрея в подарок); заливка в омывательный бачок стеклоочищающей жидкости (плюс одна бутыль стеклоочищающей жидкости в подарок);
2. 2) пакет «Свежий воздух » стоимостью 4300 руб., в который входит комплекс работ по диагностике и осмотру автомобиля, включая работы по очистке и дезинфекции кондиционера автомобиля с применением специального средства; очистка внутренней поверхности стекол автомобиля с применением специального спрея; заливка в омывательный бачок стеклоочищающей жидкости.

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

Таблица 1. Комплекс работ по диагностике и осмотру автомобиля (количество нормо-часов)

Работа	Пакет «Чистое стекло»	Пакет «Свежий воздух»
Проверка уровня моторного масла
Проверка уровня и плотности охлаждающей жидкости
Проверка уровня тормозной жидкости
Проверка состояния салонного фильтра
Визуальный контроль герметичности агрегатов
Визуальная проверка состояния тормозных дисков и колодок
Проверка тормозной системы на испытательном стенде
Корректировка давления в шинах
Функциональная проверка стеклоочистителей и стеклоомывателей
Проверка резиновых щеток стеклоочистителя на износ и наличие трещин
Проверка состояния радиатора охлаждения на предмет загрязнения
Проверка и корректировка фар
Проверка заряда аккумуляторной батареи
Короткий тест с помощью диагностической программы
Очистка и дезинфекция кондиционера
Итого

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

Проведение сезонных акций позволяет предприятию решить целый ряд задач :

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

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

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

Таблица 2. Ограничения по ресурсам на проведение сезонной акции

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

На проведение сезонной акции может быть выделено не более :

• 320 флаконов спрея для очистки внутренней поверхности стекла;
• 260 бутылей стеклоомывающей жидкости;
• 150 бутылей жидкости для очистки и дезинфекции кондиционера.

К тому же ограничено время работы механиков: в апреле 22 рабочих дня, продуктивный рабочий день механика - 7 ч в день. Следовательно, располагаемый фонд рабочего времени четырех механиков равен 616 ч (4 x 22 x 7).

Всего на один пакет «Чистое стекло » необходимо затратить:

• 2,5 ч работы механика;
• 2 флакона спрея для очистки внутренней поверхности стекла (один использовать, один - в подарок);
• 2 бутыли стеклоомывающей жидкости (одну использовать, одну - в подарок).

На пакет «Свежий воздух » необходимо затратить:

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

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

• X 1 - количество пакетов «Чистое стекло»;
• Х 2 - количество пакетов «Свежий воздух»;
• A - количество часов механика;
• B - количество флаконов спрея для внутренней очистки стекол;
• C - количество бутылей стеклоомывающей жидкости;
• D - количество бутылей жидкости для очистки и дезинфекции кондиционеров.

1) во-первых, количество пакетов не может быть отрицательным: Х1, Х2 ≥ 0;

2) во-вторых, расход ресурсов не должен превышать имеющиеся запасы. Это можно выразить при помощи неравенств:

• по ресурсу А : 2,5 x Х 1 + 3,6 x Х 2 ≤ 616;
• по ресурсу В : 2 x Х 1 + 1 x Х 2 ≤ 320;
• по ресурсу С : 2 x Х 1 + 1 x Х 2 ≤ 260;
• по ресурсу D : 0 x Х 1 + 1 x Х 2 ≤ 150.

Затем следует определиться с целевой функцией (направлением для оптимизации). Логично было бы распределить квоту на оказание пакетов услуг таким образом, чтобы предприятие получило максимальную прибыль. Для этого нужно рассчитать, сколько прибыли приносит продажа одного пакета услуг, то есть сопоставить цену реализации пакета и стоимость затрачиваемых ресурсов. Как уже говорилось выше, стоимость пакета «Чистое стекло» составляет 3600 руб., а пакета «Свежий воздух » - 4300 руб. Данные суммы необходимо сопоставить с затратами на выполнение услуг :

• тарифная часовая ставка механика составляет 350 руб. за нормо-час (включая налоги и взносы с ФОТ);
• стоимость флакона жидкости для очистки внутренней поверхности стекла - 661 руб.;
• стоимость бутыли стеклоочищающей жидкости - 250 руб.;
• стоимость бутыли жидкости для очистки и дезинфекции кондиционеров - 1589 руб.

Расчет прибыли от реализации каждого из пакетов на основании имеющихся данных представлен в табл. 3.

Таблица 3. Прибыль от реализации пакетов услуг, руб.

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

Итак, продажа одного пакета «Чистое стекло » принесет предприятию 903 руб. прибыли, а пакета «Свежий воздух » - 540 руб.

Целевая функция (Z ) в данном случае примет вид:

Z = 903 x Х 1 + 540 x Х 2.

Задача - найти максимум целевой функции с учетом существующих ограничений:

• 2,5 x Х 1 + 3,6 x Х 2 ≤ 616;
• 2 x Х 1 + 1 x Х 2 ≤ 320;
• 2 x Х 1 + 1 x Х 2 ≤ 260;
• 1 x Х 2 ≤ 150;
• Х 1, Х 2 ≥ 0.

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

Для решения нашей задачи симплекс-методом ее нужно привести к так называемому стандартному виду : преобразовать неравенства нашей системы ограничений в равенства, добавив в левую часть каждого из уравнений неотрицательные числа (назовем их Х 3, Х 4, Х 5 и Х 6), которые называются балансовыми переменными (переменные Х 1 и Х 2 называются свободными). Получится следующая система уравнений:

• 2,5 x Х 1 + 3,6 x Х 2 + Х 3 = 616;
• 2 x Х 1 + 1 x Х 2 + Х 4 = 320;
• 2 x Х 1 + 1 x Х 2 + Х 5 = 260;
• 1 x Х 2 + Х 6 = 150;
• Х 1, Х 2, Х 3, Х 4, Х 5, Х 6 ≥ 0.

Решить поставленную задачу симплекс-методом удобнее всего с помощью симплекс-таблицы. Этапы поиска оптимального решения следующие:

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

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

Z – 903 x Х 1 – 540 x Х 2 = 0.

Теперь строим первую симплекс-таблицу. Столбцами будут переменные Х 1–Х 6, а строками - имеющиеся ресурсы (А, В, С, D ). На пересечении строки и столбца находятся коэффициенты перед переменными по каждому виду ресурса в нашей системе ограничений. Так, по строке А (время работы механиков) в столбце Х 1 будет стоять коэффициент 2,5; в столбце Х 2 - 3,6; в столбце Х 3 - 1, а в Х 4–Х 6 - 0.

Также вводится дополнительный столбец (назовем его b ), в котором стоят ограничения по каждому из ресурсов. После этого вводится дополнительная строка Е , в которой содержатся коэффициенты в нашей целевой функции (Z – 903 x Х 1 – 540 x Х 2 = 0). Получилась следующая симплекс-таблица, представленная в табл. 4.

Таблица 4. Первая симплекс-таблица

Ресурс	X 1	X 2	X 3	X 4	X 5	X 6	b
A
B
C
D
Е

Значение функции Z равно числу, стоящему в правом нижнем углу табл. 4. Последующее преобразование симплекс-таблицы связано с выбором разрешающей строки и разрешающего столбца.

Разрешающим столбцом является тот столбец, у которого коэффициенты в целевой функции (строка Е) являются отрицательными и наибольшими по модулю. В данной таблице это будет столбец Х 1 , у которого по строке Е стоит значение –903. Следует заметить, что преобразование симплекс-таблиц будет происходить до тех пор, пока в строке Е не останется отрицательных значений.

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

Для нашей первой симплекс-таблицы разрешающей будет строка С , так как именно в ней наименьшее соотношение элемента столбца b и элемента разрешающего столбца Х 1 (260 / 2 = 130). Элемент таблицы, который находится на пересечении разрешающего столбца и разрешающей строки, называется разрешающим элементом (в табл. 4 ячейка данного элемента выделена цветом).

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

Преобразование осуществляется определенными методами :

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

Выполним предложенные преобразования. Чтобы приравнять разрешающий элемент к единице, разделим все элементы разрешающей строки на 2. Затем из элементов строки А С , умноженные на 2,5. Далее из элементов строки В отнимем элементы разрешающей строки С , умноженные на 2. Со строкой D никаких преобразований не производим (в разрешающем столбце итак стоит нулевое значение). К элементам строки Е С , умноженные на 903. Получилась вторая симплекс-таблица, которая представлена в табл. 5.

Таблица 5. Вторая симплекс-таблица

Ресурс	X 1	X 2	X 3	X 4	X 5	X 6	b
A
B
C
D
Е

Повторяем ту же процедуру, что и с табл. 4. Для начала находим разрешающий столбец (с наибольшим по модулю отрицательным коэффициентом перед целевой функцией). Разрешающим в данном случае будет столбец Х 2. Далее находим разрешающую строку. Это будет строка А , так как для нее выполняется условие минимальности соотношения элемента столбца b к соответствующему элементу разрешающего столбца Х 2 (291 / 2,35 = 123,83).

Элемент на пересечении строки А и столбца Х 2 будет разрешающим. Выполняем преобразование разрешающего элемента в единицу, а остальных элементов столбца Х 2 в нули. Все элементы строки А делим на 2,35. Со строкой В никаких преобразований не производим (в разрешающем столбце и так стоит нулевое значение). Из элементов строки С отнимем элементы разрешающей строки А , умноженные на 0,5 и деленные на 2,35. Из элементов строки D отнимем элементы разрешающей строки А , деленные на 2,35. К элементам строки Е прибавляем элементы разрешающей строки А , умноженные на 88,5 и деленные на 2,35. Получилась третья симплекс-таблица, которая представлена в табл. 6.

Таблица 6. Третья симплекс-таблица

Ресурс	X 1	X 2	X 3	X 4	X 5	X 6	b
A
B
C
D
Е

В полученной симплекс-таблице в строке Е , содержащей коэффициенты целевой функции, нет отрицательных значений, следовательно вычисление завершено. Значения переменных Х 1 и Х 2 расположены в столбце b на тех строках, в которых в столбцах Х 1 и Х 2 стоят единицы. Соответственно, Х 1 = 68,0851, а Х 2 = 123,8298. Значение целевой функции при таких переменных будет равно:

Z = 903 x 68,0851 + 540 x 123,8298 = 128 348,94.

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

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

Покажем это на наглядном примере. Для начала следует ввести все данные задачи в рабочий лист MS Excel (рис. 1).

Рис. 1. Ввод данных задачи оптимизации в MS Excel

Сначала следует ввести нормативы расхода имеющихся ресурсов на каждый из пакетов:

• в ячейки B3:B6 Чистое стекло »;
• в ячейки C3:C6 вводятся нормативы расхода всех ресурсов на продажу одного пакета «Свежий воздух »;
• в ячейки D3:D6 заносят запасы (лимиты расхода) по каждому из ресурсов.

Для того чтобы посчитать общий расход ресурсов и соотнести его с запасами, необходимо ввести данные о количестве проданных пакетов (ячейки В16 и С16 ). Для начала проставим там единичные значения (как будто продано по одному сезонному пакету). Общий расход ресурсов рассчитывается в диапазоне ячеек A8:D13 , в котором количество проданных пакетов (ячейки В16 и С16 ) умножается на норматив расхода (диапазоны B3:B6 и C3:C6 ). В диапазоне D10:D13 рассчитывается суммарный расход по каждому из ресурсов.

Так, например, расход нормо-часов механиков по пакету «Чистое стекло» производится в ячейке В10 путем умножения значений ячейки В16 Чистое стекло ») на ячейку В3 Чистое стекло »). Расход нормо-часов механиков по пакету «Свежий воздух » производится в ячейке С10 путем умножения значений ячейки С16 (количество проданных пакетов «Свежий воздух ») на ячейку С3 (норматив выполнения работ по пакету «Свежий воздух »).

Итоговое значение расхода часов механиков рассчитывается в ячейке D10 путем сложения значений ячеек В10 и С10 (сумма в ячейке D10 не должна превышать лимит, установленный в ячейке D3 ).

Также на рабочем листе идет расчет прибыли от продажи пакетов (ячейки В18 и С18 ). Для этого размер прибыли от продажи одного пакета (значения проставлены в ячейках В17 и С17 ) умножается на количество проданных пакетов (ячейки В16 и С16 ). В ячейке D18 стоит итоговое значение прибыли.

Цель - максимизировать значение, рассчитываемое в ячейке D18 при соблюдении всех ограничений задачи.

Воспользуемся инструментом «Поиск решения » (находим в меню «Данные» - «Анализ»). Диалоговое окно представлено на рис. 2.



Рис. 2. Диалоговое окно инструмента «Поиск решения»

По условиям поставленной задачи необходимо установить в целевую ячейку D18 (общая прибыль от продажи пакетов) максимальное значение, изменяя ячейки В16:С16 (количество проданных пакетов «Чистое стекло » и «Свежий воздух »).

При этом должны быть прописаны все ограничения нашей задачи:

• В16 и С16 >= 0 (количество проданных пакетов неотрицательно);
• D10 <= D3 (расход нормо-часов механиков не превышает имеющийся фонд рабочего времени);
• D11 <= D4 (расход спрея для очистки стекол не превышает складских остатков);
• D12 <= D5 (расход стеклоочищающей жидкости не превышает складских остатков);
• D13 <= D6 (расход жидкости для очистки и дезинфекции кондиционеров не превышает складских остатков).

После ввода ограничений нажимаем кнопку «Выполнить ». Ячейки В16 и С16 заполняются автоматически. В целевой ячейке D18 получается значение прибыли. На рис. 3 представлены результаты вычислений.



Рис. 3. Результаты вычислений

Как видно из рис. 3, результаты вычислений получились аналогичными тем, что были достигнуты при помощи симплекс-таблиц. Однако эти данные, как уже говорилось выше, не могут быть приняты по причине своей нецелочисленности. Чтобы устранить данный недостаток, необходимо в диалоговом окне инструмента «Поиск решения» прописать дополнительные условия (рис. 4).



Рис. 4. Диалоговое окно инструмента «Поиск решения» с добавлением условия целочисленности

Результаты вычисления после добавления условия целочисленности показаны на рис. 5.



Рис. 5. Результаты вычисления после добавления условия целочисленности

Полученные данные удовлетворяют всем заданным условия. Если руководство предприятия выделит на проведение сезонной акции 69 пакетов «Чистое стекло » и 122 пакета «Свежий воздух », то за счет имеющихся в распоряжении ресурсов будет получена максимальная прибыль, которая составит 128 187 руб.

Заключение

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

Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП

Линейное программирование - направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием оптимальности. Несколько слов о самом термине линейное программирование. Он требует правильного понимания. В данном случае программирование - это, конечно, не составление программ для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий. К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов. Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:

• - задача об оптимальном использовании ресурсов при производственном планировании;
• - задача о смесях (планирование состава продукции);
• - задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");
• - транспортные задачи (анализ размещения предприятия, перемещение грузов). Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:
• - математические модели большого числа экономических задач линейны относительно искомых переменных;
• - данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;
• - многие задачи линейного программирования, будучи решенными, нашли широкое применение;
• - некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования. Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных. В общем виде модель записывается следующим образом:
• - целевая функция:

C1x1 + c2x2 + ... + cnxn > max(min);- ограничения:

a11x1 + a12x2 + ... + a1nxn {? = ?} b1,

a21x1 + a22x2 + ... + a2nxn {? = ?} b2

am1x1 + am2x2 + ... + amnxn {? = ?} bm;

Требование неотрицательности:

При этом aij, bi, cj () - заданные постоянные величины. Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3). Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми. Вектор, удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программирования. План, при котором функция (2.1) достигает своего максимального (минимального) значения, называется оптимальным.

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

1. Задача об оптимальном использовании ресурсов при производственном планировании. Общий смысл задач этого класса сводится к следующему. Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц. Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида (). Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj. В планируемом периоде значения величин aij, bi и cj остаются постоянными. Требуется составить такой план выпуска продукции, при реализации которого прибыль преприятия была бы наибольшей. Далее приведем простой пример задачи такого класса.

Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В - 72 н-часа и участка С - 10 н-часов. Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?

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

По данному условию сформулируем задачу линейного программирования. Обозначим: x1 - количество выпускаемых ежедневно хоккейных клюшек, x2 - количество выпускаемых ежедневно шахматных наборов. Формулировка ЗЛП:

4x1 + 6x2 ? 120,

Подчеркнем, что каждое неравенство в системе функциональных ограничений соответствует в данном случае тому или иному производственному участку, а именно: первое - участку А, второе - участку В, третье - участку С.

Система переменных величин в задаче по оптимизации структуры посевных площадей с учётом севооборотов

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

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

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

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

Как известно, упорядоченная совокупность значений n переменных , , … представляется точкой n-мерного пространства . В дальнейшем эту точку будем обозначать Х =( , , … ).

В матричном виде задачу линейного программирования можно сформулировать так:

, A – матрица размера ,

Точка Х =( , , … ), удовлетворяющая всем условиям, называется допустимой точкой . Множество всех допустимых точек называется допустимой областью .

Оптимальным решением (оптимальным планом) задачи линейного программирования называется решение Х =( , , … ), принадлежащее допустимой области и при котором линейная функция Q принимает оптимальное (максимальное или минимальное) значение.

Теорема . Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

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

Точка Х называется выпуклой линейной комбинацией точек если выполняются условия

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

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

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

Базисным решением системы m линейных уравнений с n переменными называется решение, в котором все n-m неосновных переменных равны нулю. В задачах линейного программирования такие решения называют допустимыми базисными решениями (опорными планами).

Теорема . Каждому допустимому базисному решению задачи линейного программирования соответствует вершина многогранника решений, и наоборот, каждой вершине многогранника решений соответствует допустимое базисное решение.

Из приведенных теорем вытекает важное следствие:

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

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