Элементы линейного программирования

ГЛАВА I ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Лекция 1 ВВЕДЕНИЕ Определение 1. Линейное программирование – наука о методах исследования и отыскания экстремальных значений линейной функции, на неизвестные которой наложены линейные ограничения. Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений. Определение 2. Математическое выражение целевой функции и системы ограничений называется математической моделью экономической задачи. Определение 3. Допустимым решением задачи линейного программирования называется вектор , удовлетворяющий системе ограничений. Определение 4. Допустимое решение, при котором целевая функция достигает своего экстремального значения, называется оптимальным решением задачи линейного программирования и обозначается . Определение 5. Если все ограничения системы заданы уравнениями и переменные неотрицательные, то такая модель задачи называется канонической. Если хотя бы одно ограничение является неравенством, то модель задачи ЛП является неканонической. 1. ЭЛЕМЕНТЫ АНАЛИТИЧЕСКОЙ ГЕОМЕТРИИ В п-МЕРНОМ ПРОСТРАНСТВЕ 1.1. Основные понятия и определения Определение 1. Множество точек п-мерного пространства, координаты которых удовлетворяют уравнению , где хотя бы одно из чисел отлично от нуля, называется гиперплоскостью п-мерного пространства. Определение 2. Множество точек п-мерного пространства, координаты которых одновременно удовлетворяют каждому уравнению системы , называется пересечением гиперплоскостей. Определение 3. Множество точек п-мерного пространства, координаты которых удовлетворяют неравенству , называется полупространством п-мерного пространства, расположенным по одну сторону от гиперплоскости . Определение 4. Множество точек п-мерного пространства, содержащее вместе с любыми двумя точками А и В и все точки отрезка АВ, называется выпуклым телом (областью, фигурой). Определение 5. Точка А называется внутренней точкой выпуклой области, если в сколь угодно малой окрестности этой точки содержатся только точки этой области (рис. 1.1). Определение 6. Точка В называется граничной точкой выпуклой области, если в сколь угодно малой окрестности этой точки содержатся как точки данной области, так и не принадлежащие ей (рис. 1.1). Определение 7. Точка С называется угловой точкой выпуклой области, если она является граничной и не лежит внутри отрезка, соединяющего две другие точки этой области (рис. 1.1). Определение 8. Если область включает все свои граничные точки, то она называется замкнутой. Определение 9. Ограниченной называется область, если существует такое число М > 0, что радиус-вектор , соединяющий начало координат с любой точкой области, по абсолютной величине не больше М, т. е. . Определение 10. Если найдутся точки области, сколь угодно удалённые от начала координат, то область называется неограниченной. Определение 11. Выпуклая замкнутая ограниченная область, имеющая конечное число угловых точек, называется выпуклым п-мерным многогранником. Определение 12. Выпуклая замкнутая неограниченная область, имеющая конечное число угловых точек, называется выпуклой п-мерной многогранной областью. Определение 13. Линейная комбинация S векторов , в которой коэффициенты удовлетворяют условиям , называется выпуклой линейной комбинацией. Определение 14. Пересечением выпуклых областей называется множество точек, являющееся общей частью этих областей. Теорема 1. Пересечение выпуклых областей есть выпуклая область. Теорема 2. Множество точек выпуклого п-мерного многогранника совпадает с множеством любых выпуклых линейных комбинаций его угловых точек. 1.2. Решение систем т линейных уравнений с двумя переменными Дана система . Прямая линия , а также остальные прямые, соответствующие неравенствам данной системы, называются граничными прямыми. Определение 15. Решением каждого неравенства системы является полуплоскость, которая содержит граничную прямую и располагается по одну сторону от неё. Определение 16. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью решения системы (ОР). Определение 17. Область решения системы, удовлетворяющая условиям , называется областью неотрицательных, или допустимых, решений (ОДР). Лекция 2 Пример 1. Найти ОР и ОДР системы неравенств и определить координаты угловых точек ОДР РЕШЕНИЕ. Найдём ОР первого неравенства: . Построим прямую линию (рис. 1.2). Подставим координаты точки (0, 0) в неравенство: так как координаты точки (0, 0) не удовлетворяют ему, то решением неравенства (1.1) является полуплоскость, не содержащая точку (0.0). Аналогично найдём решения остальных неравенств системы. Получим, что ОР и ОДР системы неравенств является выпуклый многогранник АВСD. Найдём угловые точки многогранника. Точку А определим как точку пересечения прямых Решая систему, получим А(3/7, 6/7). Точку В найдём как точку пересечения прямых Из системы получим В(5/3, 10/3). Аналогично найдём координаты точек С и D: C(11/4, 9/4), D(21/10; 3/10). Пример 2. Найти ОР и ОДР системы неравенств РЕШЕНИЕ. Построим прямые и определим решения неравенств (1.5)-(1.7). ОР и ОДР являются неограниченные многогранные области ACFM и ABDEKM соответственно (рис. 1.3). Пример 3. Найти ОР и ОДР системы неравенств РЕШЕНИЕ. Найдём решения неравенств (1.8)-(1.10) (рис. 1.4). ОР представляет неограниченную многогранную область АВС; ОДР – точка В. Пример 4. Найти ОР и ОДР системы неравенств РЕШЕНИЕ. Построив прямые, найдём решения неравенств системы. ОР и ОДР не существует (рис. 1.5). 2. ГРАФИЧЕСКИЙ МЕТОД 2.1. Постановка задачи 2.2. Алгоритм решения задач 1. Находим область допустимых решений системы ограничений задачи. 2. Строим вектор , координатами которого являются коэффициенты целевой функции. 3. Проводим линию уровня , которая перпендикулярна. 4. Линию уровня перемещаем по направлению вектора для задач на максимум и в направлении, противоположном , для задач на минимум. Перемещение линии уровня производится до тех пор, пока у неё не окажется только одна общая точка с областью допустимых решений. Эта точка, определяющая единственное решение задачи ЛП, и будет точкой экстремума. Если окажется, что линия уровня параллельна одной из сторон ОДР, то в таком случае экстремум достигается во всех точках соответствующей стороны, а задача ЛП будет иметь бесчисленное множество решений. Говорят, что такая задача ЛП имеет альтернативный оптимум, и её решение находится по формуле , где , и - оптимальные решения в угловых точках ОДР. Задача ЛП может быть неразрешима, когда ограничения, определяющие её, окажутся противоречивыми. 5. Находим координаты точки экстремума и значение целевой функции в ней. 2.3. Выбор оптимального варианта выпуска изделий Фирма выпускает сливочное и шоколадное мороженое. Для изготовления мороженого используются два исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы даны в табл. Исходный продукт Расход исходных продуктов на 1 кг мороженого Запас, кг Сливочное Шоколадное Молоко 0,8 0,5 400 Наполнители 0,4 0,8 365 Суточный спрос на сливочное мороженое превышает спрос на шоколадное мороженое не более чем на 100 кг. Спрос на шоколадное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого 16 р., шоколадного – 14 р. Какое количество мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным? РЕШЕНИЕ. Обозначим: х1 – суточный объём выпуска сливочного мороженого, кг; х2 – суточный объём выпуска шоколадного мороженого, кг. Составим математическую модель задачи. Целевая функция будет иметь вид при ограничениях: Областью допустимых решений является OABDEF (рис. 2.1). Строим вектор . Линия уровня L0 задаётся уравнением Перемещаем линию по направлению вектора . Точкой выхода L0 из области допустимых решений является точка D, её координаты определяются как пересечение прямых, заданных уравнениями: Решая систему, получим координаты точки D(312,5; 300), в которой и будет оптимальное решение, т. е. , при этом Таким образом, фирма должна выпускать в сутки 312,5 кг сливочного мороженого и 300 кг шоколадного мороженого, при этом доход от реализации составит 9200 р. Лекция 3 3. СИМПЛЕКСНЫЙ МЕТОД 3.1. Общая постановка задачи Опорным решением задачи называется допустимое неотрицательное решение. Идея симплексного метода заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному решению. 3.2. Алгоритм симплексного метода 1. Математическая модель должна быть канонической. Если она неканоническая, то её надо привести к каноническому виду. 2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу. Все строки таблицы 1-го шага, за исключением строки ∆j заполняем по данным системы ограничений и целевой функции: Таблица 3.1 сi БП с1 с2 … cm cm+1 … cn x1 x2 … xm xm+1 … xn bi c1 x1 1 … h1,m+1 … h1n f1 c2 x2 1 … h2.m+1 … h2n f2 … … … … … … … … … … cm xm … 1 hm,m+1 … hmn fm ∆j … ∆m+1 … ∆n Индексная строка для переменных находится по формуле и по формуле для свободного члена. Возможны следующие случаи при решении задачи на максимум: - если все оценки , то найденное решение оптимальное; - если хотя бы одна оценка , но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращаем, так как , т. е. целевая функция неограниченна в области допустимых решений; - если хотя бы одна оценка отрицательна, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению; - если отрицательных оценок в индексной строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка. Если хотя бы одна оценка , то к-й столбец принимаем за ключевой. За ключевую строку принимаем ту, которой соответствует минимальное отношение свободных членов (f0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000i) к положительным коэффициентам к-го столбца. Элемент, находящийся на пересечении ключевой строки и ключевого столбца, называется ключевым элементом. 3. Заполняем симплексную таблицу 2-го шага: - переписываем ключевую строку, разделив её на ключевой элемент; - заполняем базисные столбцы; - остальные коэффициенты таблицы находим по правилу «прямоугольника». Оценки можно считать по приведённым выше формулам или по правилу «прямоугольника». Получаем новое опорное решение, которое проверяем на оптимальность, и т. д. Правило «прямоугольника» заключается в следующем. Пусть ключевым элементом 1-го шага является элемент 1-й строки (m+1)-го столбца h1,m+1. Тогда элемент i-й строки (m+2)-го столбца 2-го шага – обозначим его согласно правилу «прямоугольника» выражается формулой , где hi,m+2, hi,m+1, h1,m+1 – элементы 1-го шага. Примечание 1. Если целевая функция требует нахождения минимального значения, то критерием оптимальности задачи является следующее условие: Примечание 2. Если в правой части какого-нибудь неравенства из системы ограничений стоит отрицательное число, то обе части этого неравенства нужно разделить на (-1), а потом приводить это неравенство к каноническому виду. Примечание 3. Пусть модель каноническая, но нет переменных, которые можно использовать в качестве базисных (т. е. таких, которые в одном уравнении стоят с коэффициентом 1, а в других вообще отсутствуют). Тогда нужно по своему усмотрению выбирать базисные переменные, определять ключевой столбец и строку, пересчитывать элементы таблицы по правилу «прямоугольника», не заполняя оценочной строки. Это нужно проделывать до тех пор, пока не будут найдены все базисные переменные. Затем заполнить оценочную строку и определить, является ли найденное решение оптимальным. Если нет, то пересчитать таблицу. Лекция 3. 3.3. Анализ эффективности использования производственного потенциала предприятия Предприятие располагает тремя производственными ресурсами (сырьём, оборудованием, электроэнергией) и может организовать производство продукции двумя различными способами. Расход ресурсов за один месяц и общий ресурс при каждом способе производства даны в табл. (в условных ед.). Таблица 3.2 Производственные ресурсы Расход ресурсов за 1 месяц при работе Общий ресурс 1-м способом 2-м способом Сырьё Оборудование Электроэнергия 1 1 2 2 1 1 4 3 8 При первом способе производства предприятие выпускает за один месяц 3 тыс. изделий, при втором – 4 тыс. изделий. Сколько месяцев должно работать предприятие каждым из этих способов, чтобы при наличных ресурсах обеспечить максимальный выпуск продукции? РЕШЕНИЕ. Составим математическую модель задачи. Обозначим: х1 – время работы предприятия первым способом, х2 – время работы предприятия вторым способом. Математическая модель имеет вид при ограничениях: Приведём задачу к каноническому виду: при ограничениях: Составляем симплексную таблицу 1-го шага (табл. 3.3). Таблица 3.3 ci БП 3 4 x1 x2 x3 x4 x5 bi x3 x4 x5 1 1 2 2 1 1 1 1 1 4 3 8 -3 -4 Получим решение: В индексной строке имеются две отрицательные оценки, значит, найденное решение не является оптимальным и его можно улучшить. В качестве ключевого столбца следует принять столбец базисной переменной х2, а за ключевую строку взять строку переменной х3, так как Ключевым элементом является 2. Вводим в столбец базисной переменной х2 и выводим х3. Составляем симплексную таблицу 2-го шага (табл. 3.4). Таблица 3.4 ci БП 3 4 x1 x2 x3 x4 x5 bi 4 x2 x4 x5 1/2 1/2 3/2 1 1/2 -1/2 -1/2 1 1 2 1 6 -1 2 8 Получим решение В индексной строке имеется одна неотрицательная оценка. Полученное решение можно улучшить. Ключевым элементов является 1/2. Составляем симплексную таблицу 3-го шага (табл. 3.5). Составляем симплексную таблицу 3-го шага. Таблица 3.5 ci БП 3 4 x1 x2 x3 x4 x5 bi 4 3 x2 x1 x5 1 1 1 -1 1 -1 2 -3 1 1 2 3 1 2 10 Все оценки свободных переменных , следовательно, найденное опорное решение является оптимальным: Таким образом, по первому способу предприятие должно работать два месяца, по второму – один месяц, при этом максимальный выпуск продукции составит 10 тыс. ед. 3.4. Альтернативный оптимум Критерием альтернативного оптимума при решении задач симплексным методом является равенство нулю хотя бы одной оценки свободной переменной Если оценка свободной переменной равна нулю, то решение находится по формуле , где Пример. Дана задача линейного программирования при ограничениях: РЕШЕНИЕ. Составим симплексную таблицу (табл. 3.6). Таблица 3.6 ci БП 2 -4 2 x1 x2 x3 x4 x5 bi x1 x4 1 3 -2 -1 4 1 2 7 12 -2 4 -2 В индексной строке имеется одна положительная оценка. Полученное решение можно улучшить. Ключевым элементом является 4. Составляем симплексную таблицу 2-го шага (табл. 3.7). Таблица 3.7 ci БП 2 -4 2 x1 x2 x3 x4 x5 bi -4 x1 x3 1 5/2 -1/2 1 1/4 1/4 2 1/2 10 3 -1 -2 -12 Получаем Так как , то задача имеет альтернативный оптимум. Найдём ещё одно оптимальное решение, введя вместо базисной переменной х1 свободную переменную х2 (табл. 3.8). Таблица 3.8 ci БП 2 -4 2 x1 x2 x3 x4 x5 bi 2 -4 х2 x3 2/5 1/5 1 1 1/10 3/10 4/5 9/10 4 5 -1 -4 -12 Получаем Найдём координаты оптимального решения задачи: Давая t значения из [0, 1], получим различные , при которых Лекция 4 4. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ Произвольную задачу линейного программирования можно определённым образом сопоставить с другой задачей линейного программирования, называемой двойственной. 4.1. Виды двойственных задач и составление их математических моделей Симметричные двойственные задачи Дана исходная задача при ограничениях: Задача дана в неканоническом виде. Составим математическую модель двойственной задачи, для этого: • каждому неравенству системы ограничений исходной задачи приводим в соответствие переменную yi; • составляем целевую функцию, коэффициентами которой являются свободные члены системы ограничений исходной задачи. Функция стремится к минимуму, если в исходной задаче целевая функция стремилась к максимуму, и наоборот; • составляем систему ограничений. Коэффициенты системы ограничений образуют транспонированную матрицу коэффициентов системы ограничений исходной задачи. Знаки неравенств зависят от целевой функции: если она в двойственной задаче стремится к минимуму, то знаки неравенств «», и наоборот; • свободными членами системы ограничений являются коэффициенты целевой функции исходной задачи. Все переменные двойственной задачи неотрицательные. Математическая модель двойственной задачи имеет вид при ограничениях: Несимметричные двойственные задачи Дана исходная задача при ограничениях: Задача дана в каноническом виде. Составим математическую модель двойственной задачи. Для её составления пользуются тем же правилом, что и при составлении симметричной задачи, с учётом следующих особенностей: • ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства , если максимум, то ; • переменные yi – произвольные по знаку Математическая модель двойственной задачи имеет вид при ограничениях: yi – произвольные по знаку, Смешанные двойственные задачи Математическая модель исходной задачи имеет условия симметричных и несимметричных задач. При составлении двойственной задачи необходимо выполнять правила симметричных и несимметричных задач: та переменная, которая соответствует равенству в исходной задаче, может быть произвольного знака в двойственной задаче, а та переменная, которая соответствует неравенству, должна быть в двойственной задаче неотрицательной. 4.2. Основные теоремы двойственности ТЕОРЕМА 1. Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причём для любых оптимальных решений и выполняется равенство . Если одна из двойственных задач неразрешима ввиду того, что (или ), то другая задача не имеет допустимых решений. ТЕОРЕМА 2. Для оптимальности допустимых решений и пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений Теоремы позволяют определить оптимальное решение одной из пары задач по решению другой. Лекция 5 4.3. Решение двойственных задач Решение симметричных задач Рассмотрим решение задач с использованием теорем двойственности. Исходная задача при ограничениях: Двойственная задача при ограничениях: Решим исходную задачу графическим методом, получим , при этом На основании 1-й теоремы двойственности Так как , >0, то по второй теореме двойственности систему ограничений двойственной задачи можно записать в виде равенств: Подставим в систему ограничений исходной задачи: Тогда система ограничений двойственной задачи примет вид Откуда , при этом Пусть дано решение двойственной задачи , , найдём решение исходной. По 1-й теореме двойственности Так как , > 0, то по 2-й теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства: Откуда , при этом Рассмотрим решение задач методом, основанным на взаимно однозначном соответствии между переменными: основным переменным исходной задачи соответствуют балансовые переменные двойственной, и наоборот. Для этого решим двойственную задачу симплексным методом: при ограничениях: Из табл. 4.1 следует, что , . Таблица 4.1 bj БП 2 2 5 y1 y2 y3 y4 y5 cj -2 1 1 -2 1 1 -1 -1 1 -1 bj БП 2 2 5 y1 y2 y3 y4 y5 cj 2 y2 -2 -3 1 1 3 -1 -2 -1 1 1 bj БП 2 2 5 y1 y2 y3 y4 y5 cj 2 5 y2 y3 -1 -1 1 1 -1/3 -2/3 1/3 -1/3 2/3 1/3 ∆i -9 -4 -1 3 На основании 1-й теоремы двойственности получаем Решение другой задачи найдём по соответствию между переменными: Основные переменные Балансовые переменные Исходная задача x1 x2 x3 x4 x5 Двойственная y4 y5 y1 y2 y3 Балансовые переменные Основные переменные Значение xj определяем по последней симплексной таблице в строке ∆i в соответствующем столбце, причём значения xj берутся по модулю:. Таким образом, решение двойственной задачи: , . Если исходная задача решена симплексным методом, то решение двойственной задачи может быть найдено по формуле где С – матрица-строка коэффициентов при базисных переменных целевой функции в оптимальном решении исходной задачи; А-1 – обратная матрица для матрицы А, являющейся матрицей коэффициентов системы ограничений исходной задачи для базисных переменных в оптимальном решении. Решим симплексным методом исходную задачу вида при ограничениях: Таблица 4.2 сi БП 1 -1 х1 х2 х3 х4 х5 bi x3 x4 x5 -2 1 1 1 -2 1 1 1 1 2 2 5 ∆j -1 1 сi БП 1 -1 х1 х2 х3 х4 х5 bi 1 x3 x1 x5 1 -3 -2 3 1 2 1 -1 1 6 2 3 ∆j -1 1 2 сi БП 1 -1 х1 х2 х3 х4 х5 bi 1 -1 x3 x1 x2 1 1 1 1 1/3 -1/3 1 2/3 1/3 9 4 1 ∆j 2/3 1/3 3 Из табл. 4.2 следует, что , при этом Матрицы записываются в виде , , тогда . =. Таким образом, решение двойственной задачи следующее: , при этом . Решение несимметричных задач Рассмотрим решение задач с использованием теорем двойственности. Исходная задача Двойственная задача у1, у2 – произвольные по знаку. Решив двойственную задачу графическим методом, получим , при этом По 1-й теореме двойственности Подставим в систему ограничений двойственной задачи: 3=3, 1=1, -21/2<3 , -3<1 Так как х3 = х4 = 0, то система исходной задачи примет вид Решая данную систему, получим , при этом Рассмотрим решение задач с использованием обратной матрицы. Пусть решение исходной задачи , при этом Решение двойственной задачи найдём по формуле где , , =. Таким образом, , . Решение смешанных двойственных задач Смешанные двойственные задачи можно решать с использованием теорем двойственности. Исходная задача Двойственная задача у1 – произвольная по знаку, у2 Найдём оптимальное решение двойственной задачи, решив сначала исходную симплексным методом: , при этом По 1-й теореме двойственности Так как х1 > 0, x3 > 0, то по 2-й теореме двойственности первое и третье ограничения двойственной задачи выполняются в виде равенств: , откуда у1 = -5/3, у2 = 4/3, т. е. Лекция 6 5. ТРАНСПОРТНАЯ ЗАДАЧА 5.1. Общая постановка задачи В общем виде задачу можно представить следующим образом: в т пунктах производства А1, А2, …, Ат имеется однородный груз в количестве соответственно а1, а2, …, ат. Этот груз необходимо доставить в п пунктов назначения В1, В2, …, Вп в количестве соответственно b1, b2, …, bn. Стоимость перевозки единицы груза (тариф) из пункта Аi в пункт Вj равна сij. Требуется составить план перевозок, позволяющий вывезти все грузы и имеющий минимальную стоимость. Определение 1. Если , то задача называется закрытой. Если , то открытой. Обозначим через хij количество груза, перевозимого из пункта Аi в пункт Вj. Рассмотрим закрытую транспортную задачу. Её условия запишем в распределительную таблицу, которую будем использовать для нахождения решения. Таблица 5.1 Bj Ai B1 B2 … Bj … Bn b1 b2 … bj … bn A1 a1 c11 x11 c12 x12 … c1j x1j … c1n x1n A2 a2 c21 x21 c22 x22 … c2j x2j … c2n x2n … … … … … … … Ai ai ci1 xi1 ci2 xi2 … cij xij … cin xin … … … … … … … Am am cm1 xm1 cm2 xm2 … cmj xmj … cmn xmn Математическая модель закрытой транспортной задачи имеет вид при ограничениях: Оптимальным решением задачи является матрица , которая удовлетворяет системе ограничений и доставляет минимум целевой функции. Для решения транспортной задачи разработан специальный метод, имеющий те же этапы, что и симплексный метод, а именно: - нахождение исходного опорного решения; - проверка этого решения на оптимальность; - переход от одного опорного решения к другому. 5.2. Нахождение исходного опорного решения Клетки, в которые поместим грузы, называются занятыми, им соответствуют базисные переменные опорного решения. Остальные клетки незанятые, или пустые, им соответствуют свободные переменные. В верхнем правом углу каждой клетки будем записывать тарифы. Рассмотрим способ нахождения исходного опорного решения, который называется методом минимального тарифа. Согласно этому методу, грузы распределяются в первую очередь в те клетки, в которых находится минимальный тариф перевозок cij. Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учётом оставшихся запасов у поставщиков и удовлетворения спроса потребителей. Процесс распределения продолжают до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены. При распределении грузов может оказаться, что количество занятых клеток меньше, чем m+ n – 1 (вырожденная задача). В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми. Нулевые поставки помещают в незанятые клетки с учётом наименьшего тарифа таким образом, чтобы в каждых строке и столбце было не менее чем по одной занятой клетке. 5.3. Определение эффективного варианта доставки изделий к потребителю На складах А1, А2, А3 имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители В1, В2, В3 должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей (усл. ед.) Проверим, является ли данная транспортная задача закрытой: т, т, Следовательно, данная транспортная задача закрытая. Найдём исходное опорное решение по методу минимального тарифа. Таблица 5.2 bj ai 1 2 3 140 300 160 1 90 2 90 5 2 2 400 4 1 300 5 100 3 110 3 50 6 8 60 Число занятых клеток в табл. 5.2 равно m+ n – 1 = 3 + 3 – 1 = 5, т. е. задача невырожденная. Получили исходное решение: Х1 = . Стоимость перевозки при исходном оперном решении составляет усл. ед. 5.4. Проверка найденного опорного решения на оптимальность Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система т + п действительных чисел ui и vj, удовлетворяющих условиям ui+vj-cij≤0 для свободных клеток. Числа ui и vj называют потенциалами. В распределительную таблицу добавляют строку vj и столбец ui. Потенциалы ui и vj находят из равенства , справедливого для занятых клеток. Одному из потенциалов даётся произвольное значение, например , тогда остальные потенциалы определяются однозначно. Обозначим . Эту оценку называют оценкой свободных клеток. Если , то опорное решение является оптимальным. Если хотя бы одна из оценок , то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому. Проверим найденное опорное решение на оптимальность. Полагая , запишем это значение в последнем столбце таблицы и проставим остальные потенциалы, ориентируясь только на занятые клетки. Таблица 5.3 Рассмотрим занятую клетку первой строки, которая расположена в первом столбце (1, 1), для неё выполняется условие , откуда . Это значение запишем в последней строке таблицы. Далее надо рассматривать ту из занятых клеток таблицы, для которой один из потенциалов известен. Рассмотрим занятую клетку (3, 1): , откуда . Для клетки (3, 3): Для клетки (2, 3): Для клетки (2, 2): Найденные значения потенциалов заносим в таблицу. Вычисляем оценки свободных клеток. Получили одну оценку , следовательно, исходное опорное решение не является оптимальным и его можно улучшить. 5.5. Переход от одного опорного решения к другому Для перераспределения грузов будем перемещать их из занятых клеток в свободные. Свободная клетка становится занятой, а одна из ранее занятых клеток – свободной. Для свободной клетки, у которой строится цикл, все вершины которого кроме одной находятся в занятых клетках; углы прямые, число вершин чётное. Около свободной клетки цикла ставится знак (+), затем поочерёдно проставляются знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т. д. до тех пор, пока не получим оптимальное решение. Рассмотрим переход от одного опорного решения к другому на заданном примере. Строим цикл для клетки (1, 3), имеющей положительную оценку. У вершин цикла ставим знаки (+) и (-) и записываем грузы: У вершин со знаком (-) выбираем минимальный груз, он равен 60. Его прибавляем к грузам, стоящим у положительных вершин, и отнимаем от грузов, стоящих у отрицательных вершин. Получаем новый цикл: Новое опорное решение: Проверим полученное решение на оптимальность. Для этого запишем его в распределительную таблицу, найдём потенциалы занятых и оценки свободных клеток (табл. 5.4). Таблица 5.4 bi ai 1 2 3 ui 140 300 160 1 90 2 30 5 2 60 2 400 4 1 300 5 100 3 3 110 3 110 6 8 1 vj 2 -2 2 Имеем Построим цикл для клетки с положительной оценкой : Произведём перераспределение грузов: Получим новое решение, которое занесём в табл. 5.5. Проверим его на оптимальность. Таблица 5.5 bj ai 1 2 3 ui 140 300 160 1 90 2 5 2 90 2 400 4 30 1 300 5 70 3 3 110 3 110 6 8 2 vj 1 -2 2 Получим Все оценки свободных клеток отрицательные, следовательно, решение оптимальное. Итак, Стоимость транспортных расходов равна усл. ед. По сравнению с исходным опорным решением транспортные расходы уменьшились на 1610-1280=330 усл. ед. 5.6. Альтернативный оптимум в транспортных задачах Признаком наличия альтернативного оптимума в транспортной задаче является равенство нулю хотя бы одной из оценок свободных переменных в оптимальном решении (). Сделав перераспределение грузов относительно клетки, имеющей , получим новое оптимальное решение (), при этом значение целевой функции не изменится. Если одна оценка свободных переменных равна нулю, то оптимальное решение находится в виде , где . Пример. На трёх складах имеется мука в количестве 60, 130 и 90 т, которая должна быть в течение месяца доставлена четырём хлебозаводам в количестве: 30, 80, 60, 110 т соответственно. Составить оптимальный план перевозок, имеющий минимальные транспортные расходы, если стоимость доставки 1 т муки на хлебозаводы задана матрицей . РЕШЕНИЕ. Составим распределительную таблицу 5.6. Таблица 5.6 bj ai 1 2 3 4 ui 30 80 60 110 1 60 6 20 8 15 4 40 2 130 9 15 2 60 3 70 -1 3 90 6 10 12 80 7 10 vj 6 12 3 4 По методу минимального тарифа найдём исходное решение. Определим потенциалы строк и столбцов. Найдём оценки свободных клеток: Так как , то перераспределим грузы относительно клетки (1, 2): Занесём полученное перераспределение грузов в распределительную таблицу и вычислим потенциалы занятых и оценки свободных клеток (табл. 5.7). Таблица 5.7 bj ai 1 2 3 4 ui 30 80 60 110 1 60 6 8 20 15 4 40 2 130 9 15 2 60 3 70 -1 3 90 6 30 12 60 7 10 4 vj 2 8 3 4 Получим Так как , то задача имеет альтернативный оптимум и одно из решений равно . Стоимость транспортных расходов составляет: усл. ед. Произведём перераспределение грузов относительно клетки (3, 3): Занесём в распределительную таблицу полученное перераспределение грузов, вычислим потенциалы занятых и оценки свободных клеток (табл. 5.8): Таблица 5.8 bj ai 1 2 3 4 ui 30 80 60 110 1 60 6 8 60 15 4 2 130 9 15 2 20 3 110 -1 3 90 6 30 12 20 7 40 10 4 vj 2 8 3 4 Получили ещё одно решение: . Стоимость транспортных расходов составит усл. ед. Данная задача имеет два оптимальных решения и , общее решение находится по формуле , где Найдём элементы матрицы общего решения: Итак, . Стоимость транспортных расходов составляет 1550 усл. ед. Вырожденность в транспортных задачах При решении транспортной задачи может оказаться, что число занятых клеток меньше, чем m + n – 1. В этом случае задача имеет вырожденное решение. Для возможного его исключения нужно ввести в свободную клетку с наименьшей оценкой нулевую поставку. Нуль помещают в такую клетку, чтобы в каждой строке и каждом столбце было не менее одной занятой клетки. Пример. Фирма осуществляет поставку бутылок на 4 завода, занимающиеся производством прохладительных напитков. Она имеет три склада, причём на складе 1 находится 6000 бутылок, на складе 2 – 3000 бутылок и на складе 3 – 4000 бутылок. Первому заводу требуется 4000 бутылок, второму заводу – 5000 бутылок, третьему заводу – 1000 бутылок и 4 – 3000. Матрицей задана стоимость перевозки одной бутылки от каждого склада к каждому заводу. Как следует организовать доставку бутылок на заводы, чтобы стоимость перевозки было минимальной? РЕШЕНИЕ. Запишем исходные данные в распределительную таблицу, найдём исходное опорное решение по методу минимального тарифа. Число заполненных клеток равно 5, m+n–1=6, следовательно, задача является вырожденной. Для исключения вырожденности необходимо в какую-то клетку ввести нулевую поставку. Такая клетка становится условно занятой, она нужна для вычисления потенциалов занятых клеток. Эта клетка должна иметь наименьший тариф по сравнению с другими клетками, которые могут быть условно занятыми. Поместим нулевую поставку в клетку (3, 2), после чего появится возможность вычислить все потенциалы. Bj Ai 1 2 3 4 ui 4000 5000 1000 3000 1 6000 6 4 3000 9 8 3000 2 3000 5 3 2000 2 1000 8 -1 3 4000 2 4000 3 6 8 -1 vj 3 4 3 8 Все оценки свободных клеток отрицательные, следовательно, получили оптимальное решение: . Стоимость транспортных расходов при данном оптимальном решении составит 52000 усл. ед. Открытая транспортная задача При открытой транспортной задаче сума запасов не совпадает с суммой потребностей, т. е. . При этом: а) если , то объём запасов превышает объём потребления, все потребители будут удовлетворены полностью и часть запасов останется на складах. Для решения задачи вводят фиктивного (п + 1)-го потребителя, потребности которого . Модель такой задачи будет иметь вид при ограничениях: б) если , то объём потребления превышает объём запасов, часть потребностей останется неудовлетворённой. Для решения задачи вводят фиктивного (т + 1)-го поставщика, потребности которого . Модель такой задачи будет иметь вид при ограничениях: При введении фиктивного поставщика или потребителя открытая транспортная задача становится закрытой и решается по ранее рассмотренному алгоритму для закрытых транспортных задач, причём тарифы, соответствующие фиктивному поставщику или потребителю, больше или равны наибольшему из всех транспортных тарифов, иногда их считают равными нулю. В целевой функции фиктивный поставщик или потребитель не учитываются. Определение оптимального варианта перевозки грузов Задача. Составить оптимальный план перевозки грузов от трёх поставщиков с грузами 240, 40, 110 т к четырём потребителям с запросами 90, 190, 40 и 130 т. Стоимость перевозок единицы груза от каждого поставщика к каждому потребителю даны матрицей . РЕШЕНИЕ. Запасы грузов у поставщиков: т. Запросы потребителей: т; так как , то вводим фиктивного поставщика с грузом а4ф = 450 – 390 = 60 т. Тариф фиктивного поставщика 4ф примем равным 20 усл. ед. Bj Ai 1 2 3 4 ui 90 190 40 130 1 240 7 13 130 9 8 110 2 40 14 8 7 40 10 -5 3 110 3 90 15 20 6 20 -2 4ф 60 20 20 60 20 20 7 vj 5 13 12 8 Так как т + п – 1 = 7, а число занятых клеток равно 6, то для исключения вырожденности введём в клетку (2, 2) нулевую поставку. Оценки свободных клеток: , . Оценка свободной клетки (1, 3) больше нуля, перераспределим грузы: Запишем полученное перераспределение грузов в табл. : Bj Ai 1 2 3 4 ui 90 190 40 130 1 240 7 13 90 9 40 8 110 2 40 14 8 40 7 10 -5 3 110 3 90 15 20 6 20 -2 4ф 60 20 20 60 20 20 7 vj 5 13 9 8 Имеем , , , , , , , , . Получили оптимальное решение: Стоимость транспортных расходов – 3120 усл. ед. Приложение транспортных моделей к решению некоторых экономических задач. Алгоритм и методы решения транспортных задач могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов cij имеют различный смысл в зависимости от конкретной экономической задачи. Виды подобных задач: - оптимальное закрепление за станками операций по обработке деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком; - оптимальные назначения, или проблема выбора. Имеется т механизмов, которые могут выполнять т различных работ с производительностью cij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности; - задача о сокращении производства с учётом суммарных расходов на изготовление и транспортировку продукции; - увеличение производительности автомобильного транспорта за счёт минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность; - решение задач с помощью метода запрещения перевозок. Используется в том случае, если груз от некоторого поставщика по каким-то причинам не может быть направлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки. Выбор оптимального варианта использования производственного оборудования Задача. На предприятии имеется три группы станков, каждая из которых может выполнять пять операций по обработке деталей (операции могут выполняться в любом порядке). Максимальное время работы каждой группы станков соответственно равно 100, 250, 180 ч. Каждая операция должна выполняться соответственно 100, 120, 70, 110, 130 ч. Определить, сколько времени и на какую операцию нужно использовать каждую группу станков, чтобы обработать максимальное количество деталей. Производительность каждой группы станков на каждую операцию задана матрицей . РЕШЕНИЕ. Воспользуемся алгоритмом решения закрытой транспортной задачи. Так как в задаче требуется найти максимум, а согласно алгоритму транспортной задачи находится минимум, тарифы умножим на (-1). Bj Ai 1 2 3 4 5 ui 100 120 70 110 130 1 100 -3 40 -5 -11 -10 -5 60 2 250 -5 60 -10 120 -15 70 -3 -2 -2 3 180 -4 -8 -6 -12 110 -10 70 -5 vj -3 -8 -13 -7 -5 Находим оценки свободных клеток: , , . Так как > 0, перераспределим грузы, получим Полученное перераспределение грузов занесём в табл. Bj Ai 1 2 3 4 5 ui 100 120 70 110 130 1 100 -3 40 -5 -11 -10 60 -5 2 250 -5 60 -10 120 -15 70 -3 -2 -2 3 180 -4 -8 -6 -12 50 -10 130 -2 vj -3 -8 -13 -10 -8 Оценки свободных клеток составляют , , , , , , , . Найденное решение является оптимальным, так как все оценки свободных клеток отрицательные. Итак, Таким образом, на первой группе станков целесообразно выполнять операции 1 и 4 продолжительностью 40 и 60 ч соответственно, на второй группе – операции 1, 2 и 3 продолжительностью 60, 120 и 70 ч соответственно, на третьей группе – операции 4 и 5 продолжительностью 50 и 130 ч соответственно. При этом максимальное число обработанных деталей составит 5170 шт. Лекция 10 Целочисленное программирование Общая формулировка задачи В общем виде математическая модель задачи целочисленного программирования имеет вид при ограничениях: целое, Оптимальное решение задачи, найденное симплексным методом, часто не является целочисленным. Его можно округлить до ближайших целых чисел. Однако такое округление может дать решение, не лучшее среди целочисленных решений, или привести к решению, не удовлетворяющему системе ограничений. Поэтому для нахождения целочисленного решения существует специальный алгоритм, который предложен Гомори. Симплексным методом находят оптимальное решение задачи. Если решение целочисленное, то задача решена. Если же оно содержит хотя бы одну дробную координату, то накладывают дополнительное ограничение по целочисленности и вычисления продолжают до получения нового решения. Если и оно является нецелочисленным, то вновь накладывают дополнительное ограничение по целочисленности. Вычисления продолжают до тех пор, пока не будет получено целочисленное решение или показано, что задача не имеет целочисленного решения. x1 1 … … h1,r+1 … h1,n f1 x2 1 … … h2.r+1 … h2,n f2 … … … … … … … … … … … xi … 1 … hi,r+1 … hi,n fi … … … … … … … … … … … xr … … 1 hr,r+1 … hr,r+1 fr где r – ранг системы ограничений; hi,r+1 – коэффициенты симплексной таблицы i-й строки, (r+1)-го столбца; fi – свободный член i-й строки. Пусть fi и хотя бы одно hij ( ) – дробные числа. Обозначим через [fi] и [hij] целые части чисел fi и hij. Определение 1. Целой частью числа fi называют наибольшее целое число, не превосходящее числа fi. Дробную часть чисел fi и hij обозначим { fi } { hij }, она определяется следующим образом: { fi } = fi - [fi], { hij } = hij - [hij]. Пример. Если fi и хотя бы одно значение hij дробны, то с учётом введённых обозначений целых и дробных чисел дополнительное ограничение по целочисленности примет вид Примечания. 1) Если fi – дробное число, а все hij – целые числа, то задача линейного программирования не имеет целочисленного решения. 2) Ограничение целочисленности может быть наложено не на все переменные, а лишь на их часть. В этом случае задача является частично целочисленной. Графический метод решения задач При наличии в задаче линейного программирования двух переменных, а в системе ограничений – неравенств она может быть решена графическим путём. В системе координат Х1ОХ2 находят область допустимых решений, строят и линию уровня. Перемещая линию уровня по направлению для задач на максимум, находим наиболее удалённую от начала координат точку и её координаты. В том случае, когда координаты этой точки нецелочисленные, в области допустимых решений строят целочисленную решётку и находят на ней такие целые числа, которые удовлетворяют системе ограничений и при которых значение целевой функции наиболее близко к экстремальному целочисленному решению. Координаты такой вершины и являются целочисленным решением. Аналогично решается задача на минимум. Прогнозирование эффективного использования производственных площадей Задача. Для улучшения финансового положения фирма приняла решение об увеличении выпуска конкурентоспособной продукции, для чего принято решение об установке в одном из цехов дополнительного оборудования, занимающего 19/3 м2 площади. На приобретение дополнительного оборудования фирма выделила 10 усл. ед., при этом она может купить оборудование двух видов. Приобретение 1-го комплекта оборудования 1-го вида стоит 1,0 усл. ед., 2-го вида – 3 усл. ед. Приобретение одного комплекта оборудования 1-го вида позволяет увеличить выпуск продукции в смену на 2 шт., а одного комплекта оборудования 2-го вида – на 4 шт. Зная, что для установки одного комплекта оборудования 1-го вида требуется 2 м2 площади, а для оборудования 2-го вида – 1 м2 площади, определить такой набор дополнительного оборудования, который даёт возможность максимально увеличить выпуск продукции. РЕШЕНИЕ. Составим математическую модель задачи. Предположим, что фирма приобретает х1 комплектов дополнительного оборудования 1-го вида и х2 комплектов оборудования 2-го вида. Математическая модель задачи будет иметь вид при ограничениях: - целые. Получим задачу целочисленного программирования, так как неизвестных только два, то решение задачи найдём графическим способом. ОТВЕТ. Фирме следует приобрести один комплект оборудования 1-го вида и три комплекта оборудования 2-го вида, что обеспечит её при имеющихся ограничениях на производственные площади и денежные средства максимальное увеличение выпуска продукции, равное 14 усл.ед. в смену. Метод Гомори Решим эту же задачу методом Гомори. сi БП 2 4 х1 х2 х3 х4 bi x3 x4 2 1 1 3 1 1 19/3 10 ∆j -2 -4 4 x3 x2 5/3 1/3 1 1 -1/3 1/3 3 10/3 ∆j -2/3 4/3 40/3 2 4 x1 x2 1 1 3/5 -1/5 -1/5 2/5 9/5 41/15 ∆j 2/5 6/5 218/15 Получим Найдём дробные части чисел 9/15 и 41/15: Учитывая дробные части чисел 3/5 и -1/5: составляем дополнительное ограничение целочисленности для 1-й строки: или которое вводим в таблицу: сi БП 2 4 х1 х2 х3 х4 х5 bi 2 4 x1 x2 1 1 3/5 -1/5 3/5 -1/5 2/5 4/5 -1 9/5 41/15 4/5 2 4 x1 x2 х3 1 1 1 -1 2/3 4/3 1 -1/3 -5/3 1 3 4/3 ∆j 2/3 2/3 14 Получили Параметрическое программирование 1. Постановка задачи Общая задача линейного программирования имеет вид при ограничениях: целое, где cj, aij, bi – постоянные величины. Однако на практике сталкиваются с тем, что эти величины изменяются в некоторых интервалах. Также, определив оптимальное решение экономической задачи при заданных cj, aij, bi, целесообразно знать, в каких допустимых пределах можно их менять, чтобы решение осталось оптимальным. Поэтому возникает необходимость исследовать поведение оптимального решения задачи линейного программирования в зависимости от изменения коэффициентов её целевой функции и системы ограничений. Рассмотрим зависимость оптимального решения от изменения коэффициентов целевой функции. 2. Линейное программирование с параметром в целевой функции Пусть коэффициент cj целевой функции изменяется в некоторых пределах, тогда его можно заменить выражением , где - постоянные; - параметр, который изменяется в некоторых пределах. В общем случае задача линейного программирования с параметром в целевой функции записывается так: при ограничениях: , Для каждого значения в промежутке , где и - произвольные действительные числа, нужно найти вектор , удовлетворяющий системе ограничений и обращающий в максимум (минимум) целевую функцию. Решая задачу на максимум симплексным методом, и исследуя её решение в зависимости от изменения параметра , применяют следующие выражения для определения нижнего и верхнего его значений: где - оценка симплексной таблицы, содержащая параметр ; - оценка симплексной таблицы, не содержащая параметр . Если для целевой функции отыскивается min, то границы изменения и определяются следующим образом: Алгоритм решения 1) Задача решается симплексным методом при конкретном значении параметра до получения оптимального решения. 2) Вычисляются значения параметров , . 3) Определяется множество значений параметра , для которых полученное решение является оптимальным. 4) В случае необходимости в базис вводим переменную, соответствующую столбцу, из которого определялось значение параметра . 5) Выбирается ключевая строка и ключевой элемент. 6) Определяется новое оптимальное решение. 7) Находится новое множество значений , для которых решение остаётся оптимальным. 8) Процесс вычисления повторяется до тех пор, пока весь отрезок не будет исследован. Геометрический смысл задачи Пусть . ABCDEF – область допустимых решений. При строим вектор и, перемещая линию уровня MN по направлению вектора , получим в точке D оптимальное решение. Таким образом, - оптимальное решение, при котором имеем . При различных значениях линия , Параллельная линии уровня MN, будет определённым образом поворачиваться вокруг точки D. Пусть при прямая проходит через сторону CD многоугольника допустимых решений, а при - через сторону DE. Тогда значения и не изменятся до тех пор, пока . Такая картина будет повторяться до получения нового оптимального решения, соответствующего новой целевой функции, для которой существует свой диапазон изменения . 3. Определение диапазона оптимального решения выпуска продукции при изменении условий реализации Задача. Предприятие должно выпустить два вида продукции А и В, для изготовления которых используются три вида сырья. Нормы расхода сырья каждого вида на производство единицы данного вида приведены в таблице. В ней указаны такие запасы сырья каждого вида, которые могут быть использованы на производство единицы продукции данного вида. Известно, что цена единицы может изменяться для изделия А от 2 до 12 усл. ед., а для изделия В – от 13 до 3 усл. ед., причём эти изменения определяются выражениями и , где . Для каждого из возможных значений цены единицы продукции данного вида найти такой план их производства, при котором общая стоимость продукции является максимальной. Вид сырья Нормы расхода сырья на единицу продукции, т Запасы сырья, т А В I II III 4 2 6 1 2 3 16 22 36 РЕШЕНИЕ. Обозначим через х1 количество единиц продукции А, через х2 – количество единиц продукции В. Математическая модель имеет вид при ограничениях: Область допустимых решений – многоугольник ОАВСD. Полагая , , строим . Перемещая линию уровня по направлению , находим, что в точке А(0, 11) задача имеет оптимальное решение. Таким образом, при , . Если уравнение прямой имеет вид , то угловой коэффициент равен k=-A/B. Угловой коэффициент линии уровня, перпендикулярной , при произвольном значении равен Найдём область оптимальности : будет оставаться оптимальным для всех , при которых соответствующая линия уровня находится внутри угла, образованного прямыми и (2). Угловой коэффициент прямой (2) k=-2/2=-1. По условию откуда Решение остаётся оптимальным при При линия уровня совпадает с прямой (2) и оптимальными будут все точки, лежащие на прямой (2), в том числе и точка В(1, 10), лежащая на пересечении прямых (2) и (3). Оптимальное решение будет сохраняться до тех пор, пока при изменении линия уровня не совпадёт с прямой (3), что будет соответствовать новому оптимальному решению . Найдём новый диапазон изменения : , так как k3=-2. Откуда . Получили при =(1, 10), Аналогично определяем, что при =(2, 8), Таким образом, при необходимо производить только 11 изделий В, при этом стоимость продукции будет максимальной и равной усл. ед.; при необходимо производить одно изделие А и 10 изделий В, при этом стоимость продукции является максимальной и равной усл. ед.; при необходимо производить 2 изделия А и 8 изделий В, при этом стоимость продукции будет максимальной и равной усл. ед. Найдём решение этой задачи симплексным методом, для чего приведём задачу к каноническому виду: при ограничениях: ci БП bi x1 x2 x3 x4 x5 x3 x4 x5 4 2 6 1 2 3 1 1 1 16 22 36 13- x3 x2 x1 3 1 3 1 1 -1/2 1/2 -3/2 1 5 11 3 Получим , так как все Таким образом, . ci БП bi x1 x2 x3 x4 x5 x3 x2 x1 1 1 1 1 1 -1/2 -1 -1/3 1/3 2 10 1 132-9 Получим Таким образом, . ci БП bi x1 x2 x3 x4 x5 X4 x2 x1 1 1 1 -1 1/2 1 -1 2/3 -1/6 2 8 2 108- Получим Таким образом, . ; ; . Транспортная параметрическая задача Задача формулируется следующим образом: для всех значений параметра , где - произвольные действительные числа, найти такие значения , которые обращают в минимум функцию при ограничениях: Пользуясь методом потенциалов, решаем задачу при до получения оптимального решения. Признаком оптимальности является условие: для незанятых клеток и для занятых клеток, где - потенциалы строк, столбцов распределительной таблицы. Условие совместимости транспортной задачи записывается в виде Значения и определяются из условия где определяются из систем уравнений Значения находятся в пределах : Алгоритм решения. 1. Задачу решаем при конкретном значении параметра до получения оптимального решения. 2. Определяем и 3. Вычисляем значения параметра . 4. Если , производим перераспределение поставок и получаем новое оптимальное решение. Если , то процесс решения окончен. Нахождение оптимальных путей транспортировки грузов при нестабильной загрузке дорог Имеются три поставщика однородного товара с объёмами поставок: а1 = 100 т, а2 = 200 т, а3 = 100 т и четыре потребителя с объёмами потребления b1 = 80 т, b2 = 120 т, b3 = 150 т, b4 = 50 т. Стоимость транспортных расходов изменяется в определённом диапазоне в зависимости от загрузки дороги и задана матрицей Определить оптимальное решение перевозок, обеспечивающее минимальные транспортные затраты. РЕШЕНИЕ. В матрицу расходов введём параметр , где . Получим . Полагая , решаем задачу методом потенциалов, определим оптимальное решение перевозок. Распределительная таблица этого решения будет иметь вид: bj ai 80 120 150 50 ui 100 30 4- 70 8 200 4 50 7 150 100 5 3 50 6 50 vj В таблице ui и vj – потенциалы строк и столбцов. Для занятых клеток они определяются из условия Полагая u1 = 0, , получаем , откуда или откуда или Аналогично находим, что Оценки свободных клеток находим по формуле Имеем Аналогично находим, что Решение, полученное при , является оптимальным для всех значений параметра , удовлетворяющих условию или Имеем Так как по условию задачи , то оптимальное решение сохраняется при При этом минимальная стоимость транспортных расходов составляет Таким образом, при и . Чтобы получить оптимальное решение при , перераспределим поставки товаров в клетку (3, 1), где . Вновь полученное распределение представлено в табл.: bj ai 80 120 150 50 ui 100 4- 100 8 200 4 50 7 150 100 5 30 3 20 6 50 vj Находим оценки свободных клеток: . Определим пределы изменения : Полученное в таблице оптимальное решение сохраняется при При этом . Итак, . Перераспределим поставки грузов в клетку (3, 3), где . Получим новое распределение: bj ai 80 120 150 50 ui 100 4- 100 8 200 4 80 7 120 100 5 3 20 6 30 50 vj Находим оценки свободных клеток: . Определим пределы изменения : Оптимальное решение сохраняется при При этом . Итак, . Перераспределим поставки грузов в клетку (1, 4), где . bj ai 80 120 150 50 ui 100 4- 50 8 50 200 4 80 7 120 100 5 3 70 6 30 vj Оценки свободных клеток: . Пределы изменения : Полученное в предыдущей таблице оптимальное решение сохраняется при При этом . Итак, . Перераспределим поставки грузов в клетку (2, 4), где . bj ai 80 120 150 50 ui 100 4- 100 8 200 4 80 7 70 50 100 5 3 20 6 80 vj Оценки свободных клеток: . Пределы изменения : Оптимальное решение сохраняется при При этом . Итак, . Лекция Задача о назначениях Задача заключается в выборе такого распределения ресурсов по объектам, при котором минимизируется стоимость назначений. Предполагается, что каждый ресурс назначается ровно один раз и каждому объекту приписывается ровно один ресурс. Матрица стоимостей С имеет вид С = (сij), где сij – затраты, связанные с назначением i-го ресурса на j-й объект, i = j = , где п – число объектов или ресурсов. Обозначим: Таким образом, решение задачи может быть записано в виде X = (xij). Допустимое решение называется назначением. Оно строится путём выбора ровно одного элемента в каждой строке матрицы X = (xij) и ровно одного элемента в каждом столбце этой матрицы. Элементы сij матрицы С, соответствующие элементам xij = 1 матрицы Х будем отмечать кружками: С = (сij) = , X = (xij) = Математическая постановка задачи: при ограничениях: xij = 0 или 1. Алгоритм решения задачи Рассмотрим метод, называемый венгерским алгоритмом. Он состоит из следующих шагов: 1) преобразование строк и столбцов матрицы; 2) определение назначения; 3) модификация преобразованной матрицы. 1-й шаг. Цель данного шага – получение максимально возможного числа нулевых элементов в матрице С. Для этого из всех элементов каждой строки вычитаем минимальный элемент соответствующей строки, а из всех элементов каждого столбца вычитаем минимальный элемент соответствующего столбца.. 2-й шаг. Если после выполнения 1-го шага в каждой строке и каждом столбце матрицы С можно выбрать по одному нулевому элементу, то полученное решение будет оптимальным назначением. 3-й шаг. Если допустимое решение, состоящее из нулей, не найдено, то проводим минимальное число прямых через некоторые столбцы и строки так, чтобы все нули оказались вычеркнутыми. Выбираем наименьший невычеркнутый элемент. Этот элемент вычитаем из каждого невычеркнутого элемента и прибавляем к каждому элементу, стоящему на пересечении проведённых прямых. Если после проведения 3-го шага оптимальное решение не достигнуто, то процедуру проведения прямых следует повторять до тех пор, пока не будет получено допустимое решение. Пример. Распределить ресурсы по объектам. РЕШЕНИЕ. 1-й шаг. Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, 5, 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим 2-й шаг. Ни одно назначение не получено, необходимо провести модификацию матрицы стоимостей. 3-й шаг. Вычёркиваем столбец 1, строку 3, строку 2 (или столбец 2). Значение минимального невычеркнутого элемента равно 2: min = 2. Вычитаем его из всех невычеркнутых элементов и, складывая его со всеми элементами, расположенными на пересечении двух линий, получим Итак, Ответ. Первый ресурс направляем на 3-й объект, второй – на 2-й объект, четвёртый – на 1-й объект, третий ресурс – на 4-й объект. Стоимость назначения: 9 + 4 + 11 + 4 = 28. Примечания. 1. Если исходная матрица не является квадратной, то нужно ввести фиктивные ресурсы или фиктивные объекты, чтобы матрица стала квадратной. 2. Если какой-либо ресурс не может быть назначен на какой-то объект, то соответствующая стоимость полагается равной достаточно большому числу М. 3. Если исходная задача является задачей максимизации, то все элементы матрицы С следует умножить на (-1) и сложить их с достаточно большим числом так, чтобы матрица не сдержала отрицательных элементов. Затем задачу следует решать как задачу минимизации. 4. Если число линий, необходимое для того, чтобы вычеркнуть нулевые элементы, равно числу строк или столбцов (квадратной матрицы), то существует назначение нулевой стоимости. Планирование загрузки оборудования с учётом максимальной производительности станков На предприятии пять станков различных видов, каждый из которых может выполнять пять различных операций по обработке деталей. Известна производительность каждого станка при выполнении каждой операции, заданная матрицей . Определить, какую операцию и за каким станком следует закрепить, чтобы суммарная производительность была максимальной при условии, что за каждым станком закреплена только одна операция. РЕШЕНИЕ. Так как в задаче требуется определить max, а алгоритм метода дан для задач на min, умножим матрицу С на (-1). Сложим полученную матрицу, имеющую отрицательные коэффициенты, с положительным числом, например, с числом 10. Получим Минимальные элементы в строчках есть 3, 4, 4, 6, 4. Вычтем их из соответствующих элементов матрицы, получим Так как назначение не получено, вычёркиваем строку 2, столбцы 2, 4, 5: Минимальный элемент равен 1. Вычитаем его из всех невычеркнутых элементов и складываем со всеми элементами, расположенными на пересечении двух линий. Получаем Оптимальное решение, соответствующее последней матрице, равно Суммарная производительность: 6 + 6 + 3 + 6 + 7 = 28. Таким образом, на первом станке надо делать 5-ю операцию, на втором – 1-ю операцию, на третьем – 4-ю операцию, на четвёртом – 3-ю операцию, на пятом – 2-ю операцию. Суммарная производительность: 28 деталей в единицу времени. Нелинейное программирование Общая постановка задачи Математическая модель задачи нелинейного программирования в общем виде формулируется следующим образом: найти вектор , удовлетворяющий системе ограничений и доставляющий экстремум целевой функции где xj – переменные, - заданные функции от п переменных, bi – фиксированные значения. Для задачи нелинейного программирования в отличие от линейных задач нет единого метода решения. В зависимости от вида целевой функции и системы ограничений разработаны специальные методы решения, к которым относятся методы множителей Лагранжа, квадратичное и выпуклое программирование, градиентные методы, приближённые методы решения, графический метод. Графический метод Рассмотрим примеры решение задач нелинейного программирования с двумя переменными, причём их целевые функции и системы ограничений могут быть заданы в линейном и нелинейном виде. Так же как и в задачах линейного программирования, они могут быть решены графически. Задача с линейной целевой функцией и нелинейной системой ограничений Пример 1. Найти глобальные экстремумы функции при ограничениях: ОТВЕТ. Глобальный минимум, равный нулю, достигается в точке О(0, 0), глобальный максимум, равный , - в точке Задача с нелинейной целевой функцией и линейной системой ограничений Пример 2. Найти глобальные экстремумы функции при ограничениях.: ОТВЕТ. Глобальный максимум, равный 58, достигается в точке D(9, 0), глобальный минимум, равный нулю, - в точке О1(2, 3). Пример 3. Найти глобальные экстремумы функции при ограничениях.: ОТВЕТ. Глобальный максимум, равный 52, находится в точке О(0, 0). Глобальный минимум, равный 1053/169, находится в точке Е(51/13б21/13). Задача с нелинейной целевой функцией и нелинейной системой ограничений Пример 4. Найти глобальные экстремумы функции при ограничениях: ОТВЕТ. Глобальный минимум, равный нулю, достигается в точке О1(2, 1), глобальный максимум, равный 13, находится в точке А(0, 4). Пример 5. Найти глобальные экстремумы функции при ограничениях.: ОТВЕТ. Целевая функция имеет два глобальных минимума, равных 17, в точках А(1, 4) и В(4, 1), глобальный максимум, равный 2417/49, достигается в точке Е(7, 4/7). Дробно-линейное программирование Дробно-линейное программирование относится к нелинейному программированию, так как имеет целевую функцию, заданную в нелинейном виде. Задача дробно-линейного программирования в общем виде записывается следующим образом: при ограничениях: где - постоянные коэффициенты и Рассмотрим задачу дробно-линейного программирования в виде при ограничениях: Пусть Для решения этой задачи найдём область допустимых решений, определяемую заданными ограничениями. Пусть эта область не является пустым множеством. Из выражения, задающего целевую функцию, найдём х2: где Прямая x2 = kx1 проходит через начало координат. При некотором фиксированном значении L угловой коэффициент k тоже фиксирован, и прямая займёт определённое положение. При изменении значений L прямая x2 = kx1 будет поворачиваться вокруг начала координат. Установим, как будет вести себя угловой коэффициент k при монотонном возрастании L. Найдём производную от k по L: Знаменатель производной всегда положителен, а числитель от L не зависит. Следовательно, производная имеет постоянный знак, и при увеличении L угловой коэффициент будет только возрастать или только убывать, а прямая будет поворачиваться в одну сторону. Если имеет положительное значение, то прямая вращается против часовой стрелки, при отрицательном значении - по часовой стрелке. Установив направление вращения, находим вершину или вершины многогранника, в которых функция принимает max (min) значение, либо устанавливаем неограниченность задачи. При этом возможны следующие случаи. 1. Область допустимых решений ограничена, максимум и минимум достигаются в её угловых точках (рис. а). 2. Область допустимых решений неограниченна, однако существуют угловые точки, в которых целевая функция принимает максимальное и минимальное значения (рис. б). 3. Область допустимых решений неограниченна, имеется один из экстремумов. Например, минимум достигается в одной из вершин области и имеет так называемый асимптотический максимум (рис. в). 4. Область допустимых решений неограниченна. Максимум и минимум являются асимптотическими (рис. г). Алгоритм решения 1. Находим область допустимых решений. 2. Определяем угловой коэффициент k и устанавливаем направление поворота целевой функции. 3. Находим точку max (min) целевой функции или устанавливаем неразрешимость задачи. Экономическая интерпретация задач дробно-линейного программирования Математическая модель задачи дробно-линейного программирования может быть использована для определения рентабельности затрат на производство изделий, рентабельности продаж, затрат в расчёте на рубль выпускаемой продукции, себестоимости изделий. Обозначим: - прибыль предприятия от реализации единицы изделия j-го вида; - количество выпущенной продукции j-го вида; cj - себестоимость производства единицы изделия j-го вида; dj – затраты на производство одного изделия j-го вида. Задача рентабельности (Рз) затрат на производство изделий имеет вид Задача рентабельности (Рп) продаж имеет вид Задача определения затрат (Зр) в расчёте на рубль товарной продукции записывается в виде Задача нахождения себестоимости изделия записывается как Применение дробно-линейного программирования для определения себестоимости изделий Пример 6. Для производства двух видов изделий А и В предприятие использует три типа технологического оборудования. Каждое из изделий должно пройти обработку на каждом из типов оборудования. Время обработки каждого из изделий, затраты, связанные с производством одного изделия, даны в таблице. Оборудование I и III типов предприятие может использовать не более 26 и 39 ч соответственно, оборудование II типа целесообразно использовать не менее 4 ч. Определить, сколько изделий каждого вида следует изготовить предприятию, чтобы средняя себестоимость одного изделия была минимальной. Тип оборудования Затраты времени на обработку одного изделия, ч А В I II III Затраты на производство Одного изделия, тыс. р. 2 1 12 2 8 1 3 3 РЕШЕНИЕ. Составим математическую модель задачи. Пусть х1 – количество изделий вида А, которое следует изготовить предприятию, х2 – количество изделий вида В. Общие затраты на их производство составят (2х1 + 3х2) / (х1 + х2). Математическая модель задачи примет вид при ограничениях:  АВС – область допустимых решений. Найдём х2: , Угловой коэффициент прямой равен , тогда Так как , то функция возрастает. Это соответствует вращению прямой против часовой стрелки. Следовательно, в точке С целевая функция будет иметь наименьшее значение. Найдём координаты точки С. Решая систему х1 = 3, х2 = 1, получим С(3, 1), Следовательно, предприятию следует выпускать 3 изделия вида А и 1 изделие вида В. При этом средняя себестоимость одного изделия будет минимальной и равной 2,25 тыс. р. Сведение экономико-математической модели дробно-линейного программирования к задаче линейного программирования Задачу дробно-линейного программирования можно свести к задаче линейного программирования и решить симплексным методом. Обозначим при условии и введём новые переменные Тогда задача примет вид при ограничения: После нахождения оптимального решения полученной задачи, используя вышеуказанные соотношения, найдём оптимальное решение исходной задачи дробно-линейного программирования. Пример 7. Дана задача дробно-линейного программирования при ограничениях: РЕШЕНИЕ. Обозначим: тогда Обозначим: Преобразуем систему ограничений, умножив обе части всех ограничений на у0, и перейдём к переменным Задача примет вид при ограничениях После решения задачи симплексным методом получим тогда ОТВЕТ. 4. Метод множителей Лагранжа Дана задача нелинейного программирования при ограничениях: Предположим, что функции и непрерывны вместе со своими частными производными. Для решения задачи составляется функция Лагранжа где - множители Лагранжа. Затем определяются частные производные: Приравняв к нулю частные производные, получим систему Решая систему, получим множество точек, в которых целевая функция L может иметь экстремальные значения. Условия рассмотренной системы являются необходимыми, но недостаточными. Поэтому не всякое полученное решение определяет точку экстремума целевой функции. Применение метода бывает оправданным, когда заранее предполагается существование глобального экстремума, совпадающего с единственным условным экстремумом целевой функции. Пример 8. Найти точку условного экстремума целевой функции При ограничениях: Решение. Составим функцию Лагранжа Найдя частные производные и приравняв их к нулю, решим систему Откуда Определим характер экстремума, изменяя значения переменных. Изменённые значения должны удовлетворять заданной системе ограничений. Возьмём , например , тогда из системы ограничений получим Возьмём , например , тогда получим Следовательно, - минимальное значение функции. Ответ. Точка экстремума , при этом минимальное значение функции . Расчёт экономико-математической модели при нелинейных реализациях продукции Пример 9. Мукомольный комбинат реализует муку двумя способами: в розницу через магазин и оптом через торговых агентов. При продаже кг муки через магазин расходы на реализацию составляют ден. ед., а при продаже кг муки посредством торговых агентов - ден. ед. Определить, сколько килограммов муки следует продавать каждым способом, чтобы затраты на реализацию были минимальными, если в сутки выделяется для продажи 5000 кг муки. Динамическое программирование Динамическое программирование – один из разделов оптимального программирования, в котором процесс принятия и управления может быть разбит на отдельные этапы. Экономический процесс является управляемым, если можно влиять на ход его развития. Под управлением понимается совокупность решений, принимаемых на каждом этапе для влияния на ход развития процесса. Например, выпуск продукции предприятием – управляемый процесс. Совокупность решений, принимаемых в начале года по обеспечению предприятия сырьём, замене оборудования, финансированию и т. д., является управлением. Необходимо организовать выпуск продукции так, чтобы принятые решения на отдельных этапах способствовали получению максимально возможного объёма продукции или прибыли. Одним из основных методов динамического программирования является метод рекуррентных соотношений, который основывается на использовании принципа оптимальности, разработанного американским математиком Беллманом. Принцип состоит в том, что, каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придёт система в конце данного шага. Использование данного принципа гарантирует, что управление, выбранное на любом шаге, лучше с точки зрения процесса в целом. В некоторых задачах, решаемых методом динамического программирования, процесс управления разбивается на шаги. При распределении на несколько лет ресурсов деятельности предприятия шагом считается временной период; при распределении средств между предприятиями – номер очередного предприятия. Оптимальная стратегия замены оборудования Одной из важнейших экономических проблем является определение оптимальной стратегии в замене старых станков, агрегатов, машин на новые. Старение оборудования включает его физический и моральный износ, в результате чего растут производственные затраты по выпуску продукции на старом оборудовании, увеличиваются затраты на ремонт и обслуживание, снижаются производительность и ликвидная стоимость. Вполне возможно, что старое оборудование выгоднее продать, заменить новым, чем эксплуатировать его; причём его можно заменить новым оборудованием того же вида или новым, более совершенным. Оптимальная стратегия замены оборудования состоит в определении оптимальных сроков замены. Критерием оптимальности при этом может служить прибыль от эксплуатации оборудования, которую следует оптимизировать, или суммарные затраты на эксплуатацию в течение рассматриваемого промежутка времени, подлежащие минимизации. Будем использовать обозначения: r(t) – стоимость продукции, производимой за один год на единице оборудования возраста t лет; u(t) – ежегодные затраты на обслуживание оборудования возраста t лет; s(t) – остаточная стоимость оборудования возраста t лет; Р – покупная цена оборудования. Рассмотрим период N лет, в пределах которого требуется определить оптимальный план замены оборудования. Обозначим через fN(t) максимальный доход, получаемый от оборудования возраста t лет за оставшиеся N лет цикла использования оборудования при условии оптимальной стратегии. Возраст оборудования отсчитывается в направлении течения процесса. Так, t = 0 соответствует случаю использования нового оборудования. Временные же стадии процесса нумеруются в обратном направлении по отношению к ходу процесса. Например, N = 1 относится к одной временной стадии, остающейся до завершения процесса. На каждом этапе N-стадийного процесса должно быть принято решение о сохранении или замене оборудования. Выбранный вариант должен обеспечивать получение максимальной прибыли. Уравнения, помогающие выбрать оптимальное решение, имеют вид: Первое уравнение описывает N-стадийный процесс, а второе – одностадийный. Оба уравнения состоят из двух частей: верхняя строка определяет доход, получаемый при сохранении оборудования; нижняя – доход, получаемый при замене оборудования и продолжении процесса работы на новом оборудовании. В первом уравнении функция r(t) - u(t) есть разность между стоимостью произведённой продукции и эксплуатационными издержками на N – й стадии процесса. Функция fN-1(t+1) характеризует суммарную прибыль от (N - 1) оставшихся стадий для оборудования, возраст которого в начале осуществления этих стадий составляет (t + 1) лет. Нижняя строка уравнения 1 характеризуется следующим образом: функция s(t) – P представляет чистые издержки по замене оборудования, возраст которого t лет. Функция r(0) выражает доход, получаемый от нового оборудования возраста 0 лет. Предполагается, что переход от работы на оборудовании возраста t лет к работе на новом оборудовании совершается мгновенно, т. е. период замены старого оборудования и переход на работу на новом оборудовании укладываются в одну и ту же стадию. Последняя функция fN-1(1) в первом уравнении представляет собой доход от оставшихся N – 1 стадий, до начала осуществления которых возраст оборудования составляет один год. В уравнении для одностадийного процесса нет слагаемого вида f0(t + 1), так как N принимает значения 1, 2, …, N. Равенство f0(t) = 0 следует из определения функции fN (t). Рассмотренные уравнения являются рекуррентными соотношениями, которые позволяют определить величину fN (t) в зависимости от fN-1(t+1). Данные уравнения показывают, что при переходе от одной стадии процесса к следующей возраст оборудования увеличивается с t до (t+1) лет, а число оставшихся стадий уменьшается с N до (N – 1). Уравнения позволяют оценить варианты замены и сохранения оборудования, с тем, чтобы принять тот из них, который предполагает больший доход. Эти соотношения позволяют выбрать линию поведения при решении вопроса о сохранении и замене оборудования, а также определить прибыль, получаемую при принятии каждого из этих решений. Пример. Определить оптимальный цикл замены оборудования при следующих исходных данных: Р = 10, S(t ) = 0, f(t) = r(t) - u(t), представленных в таблице. t 1 2 3 4 5 6 7 8 9 10 11 12 f(t) 10 9 8 7 6 5 4 3 2 1 РЕШЕНИЕ. Запишем уравнения в следующем виде: . Для N=1 ………………………………………………… Для N=2 ………………………………………………… Вычисления продолжаются до тех пор, пока не будет выполнено условие f1(1) > f2(2), т. е. в данный момент оборудование необходимо заменить, так как величина прибыли, получаемая в результате замены оборудования, больше, чем в случае использования старого. Результаты расчётов помещаются в таблицу, момент замены отмечается звёздочкой, после чего дальнейшие вычисления по строке прекращаются. t fN(t) 1 2 3 4 5 6 7 8 9 10 11 12 N N-1 11 10 9 8 7 6 5 4 3 2 1 f1(t) 10 9 8 7 6 5 4 3 2 1 f2(t) 19 17 15 13 11 9 9* f3(t) 27 24 21 18 17* f4(t) 34 30 26 24 24* f5(t) 40 35 32 31 30 30* f6(t) 45 41 39 37 36 35 35* f7(t) 51 48 45 43 41 41* f8(t) 58 54 51 48 48* f9(t) 64 60 56 55 54 54* f10(t) 70 65 63 61 60 60* f11(t) 75 72 69 67 66 65* f12(t) 82 78 75 73 72* По результатам вычислений и по линии, разграничивающей области решений сохранения и замены оборудования, находим оптимальный цикл замены оборудования. Для данной задачи он составляет 4 года. Ответ. Для получения максимальной прибыли от использования оборудования в двенадцатиэтапном процессе оптимальный цикл состоит в замене оборудования через каждые 4 года. Сетевые модели Современное сетевое планирование начинается с разбиения программы работ на операции. Определяются оценки продолжительности операций и строится сетевая модель. Построение сетевой модели позволяет проанализировать все операции и внести улучшения в структуру модели до начала её реализации. Строится календарный график, определяющий начало и окончание каждой операции, а также взаимосвязи с другими операциями графика. Календарный график выявляет критические операции, которым надо уделять особое внимание, чтобы закончить все работы в положенный срок. По некритическим операциям календарный план позволяет определить резервы времени, которые можно выгодно использовать. Основные операции сетевой модели Сетевая модель – графическое изображение плана выполнения комплекса работ, состоящего из нитей (работ) и узлов (событий), которые отражают логическую взаимосвязь всех операций. В основе сетевого моделирования лежит изображение планируемого комплекса работ в виде графа. Граф – схема, состоящая из заданных точек (вершин), соединённых системой линий. Отрезки, соединяющие вершины, называются рёбрами графа. Ориентированным называется такой граф, на котором стрелкой указаны направления всех его рёбер, что позволяет определить, какая из двух его граничных вершин является начальной, а какая – конечной. Работа – это активный процесс, требующий затрат ресурсов, либо пассивный, приводящий к достижению намеченного результата. Фиктивная работа – это связь между результатами работ, не требующая затрат времени и ресурсов. Событие – это результат выполнения одной или нескольких предшествующих работ. Путь – это любая непрерывная последовательность работ и событий. Контур – путь, у которого начальная вершина совпадает с конечной. Сетевой график – это ориентированный граф без контуров. Критический путь – это путь, не имеющий резервов и включающий самые напряжённые работы комплекса. Работы, расположенные на критическом пути, называют критическими. Все остальные работы являются некритическими и обладают резервами времени, которые позволяют передвигать сроки их выполнения, не влияя на общую продолжительность выполнения всего комплекса работ. При построении сетевых моделей необходимо соблюдать следующие правила. 1. Сеть изображается слева направо, и каждое событие с большим порядковым номером изображается правее предыдущего. Общее направление стрелок, изображающих работы, также в основном должно быть расположено слева направо, при этом каждая работа должна выходить из события с меньшим номером и входить в событие с большим номером. 2. Два соседних события могут объединяться лишь одной работой. Для изображения параллельных работ вводятся промежуточное событие и фиктивная работа (рис 1). 3. В сети не должно быть тупиков, т. е. промежуточных событий, из которых не выходит ни одна работа (рис 2). 4. В сети не должно быть промежуточных события, которым не предшествует хотя бы одна работа (рис. 3). 5. В сети не должно быть замкнутых контуров, состоящих из взаимосвязанных работ, создающих замкнутую цепь (рис. 4). Для правильной нумерации событий поступают следующим образом: нумерация событий начинается с исходного события, которому даётся номер 1. Из исходного события 1 вычёркивают все исходящие из него работы, на оставшейся сети вновь находят событие, в которое не входит ни одна работа. Этому событию даётся номер 2. Затем вычёркивают работы, выходящие из события 2, и вновь находят на оставшейся части сети событие, в которое не входит ни одна работа, ему присваивается номер 3, и так продолжается до завершающего события. Пример нумерации сетевого графика (рис. 5). Рассмотрим программу создания нового бытового прибора, пользующегося спросом у населения. Необходимые данные приведены в таблице. Операции Наименование работы Непосредственно предшествующие операции Продолжительность, неделя А, Б В, Г Д Е Ж З, К И Разработка технической документации (ТД) на прибор и его электронную часть Разработка технологической документации на прибор и его электронную часть Передача ТД на прибор Изготовление приборов Изготовление электронной части прибора Разработка ТД на эксплуатацию прибора и электронную часть Сборка и испытания прибора - А, Б А В, Д Д, Г Г, В Е, Ж А – 3, Б – 2 В – 2, Г – 2 3 7 3 З – 5, К – 2 6 На основании данных таблицы построен сетевой график создания прибора с учётом вышеизложенных рекомендаций. Расчёт временных параметров сетевого графика Основным временным параметром сетевого графика является продолжительность критического пути. Расчёт критического пути включает два этапа. Первый называется прямым проходом. Вычисления начинают с исходного события и продолжают до тех пор, пока не будет достигнуто завершающее событие. Для каждого события определено одно число, представляющее ранний срок его наступления. На втором этапе, называемом обратным проходом, вычисления начинают с завершающего события и продолжают, пока не будет достигнуто исходное событие. Для каждого события вычисляется поздний срок его наступления. Прямой проход: - ранний срок начала всех операций, выходящих из события i. Если i = 0, то = 0; - ранний срок начала всех операций, выходящих из j. Тогда для всех (i, j), где tij – продолжительность операции (i, j); Обратный проход: - поздний срок окончания всех операций, входящих в событие i. Если i = п, где п – завершающее событие сети, то является отправной точкой обратного прохода; для всех операций (i, j); ; Используя результаты вычислений при прямом и обратном проходах, можно определить операции критического пути. Операция (i, j) принадлежит критическому пути, если она удовлетворяет условиям: Для рассматриваемого примера критический путь включает операции (0, 2), (2, 3), (3, 4), (4, 5), (5, 6). Операции связаны ещё двумя сроками: - поздний срок начала работы. Он является наиболее поздним из допустимых моментов начала данной работы, при котором ещё возможно выполнение всех последующих работ в установленный срок: - ранний срок окончания работы. Он является наиболее ранним из возможных моментов окончания работы при заданной продолжительности работ: Различают два вида резервов времени: полный резерв (rп) и свободный резерв (rсв). Полный резерв времени показывает, на сколько может быть увеличена сумма продолжительности всех работ относительно критического пути. Он представляет собой разность между максимальным отрезком времени, в течение которого может быть выполнена операция, и её продолжительностью (tij) и определяется как Свободный резерв времени – максимальное время, на которое можно отсрочить начало или увеличить продолжительность работы при условии, что все события наступают в ранние сроки: Результаты расчёта критического пути и резервов времени некритических операций представлены в таблице. Критические операции должны иметь нулевой полный резерв времени, при этом свободный резерв также должен быть равен нулю. ТАБЛИЦУ!!!!!! Построение сетевого графика и распределение ресурсов Конечным результатом выполняемых на сетевой модели расчётов является сетевой график. При построении сетевого графика необходимо учитывать наличие ресурсов, так как одновременное выполнение некоторых операций из-за ограничений, связанных с рабочей силой, оборудованием и другими видами ресурсов, иногда оказывается невозможным. Именно в этом отношении представляют ценность полные резервы времени некритических операций. Сдвигая некритическую операцию в том или ином направлении, но в пределах её полного резерва времени, можно добиться снижения максимальной потребности в ресурсах. Однако даже при отсутствии ограничений на ресурсы полные резерв времени обычно используются для выравнивания потребностей в ресурсах на протяжении всего срока реализации программы работ. Это означает, что работы удастся выполнить более или менее постоянным составом рабочей силы. На рисунке 1 показан график рассмотренного примера. Роль полных и свободных резервов при выборе сроков объясняется двумя правилами: 1) если полный резерв равен свободному, то календарные сроки некритической операции можно выбрать в любой точке между её ранним началом и поздним окончанием; 2) если свободный резерв меньше полного, то срок начала некритической операции можно сдвинуть по отношению к раннему сроку её начала не более чем на величину свободного резерва. В данном примере правило 2 применимо к операции (0, 1), а сроки всех остальных операций выбираются по правилу 1. На рисунке 2 показана потребность в рабочей силе при условии выбора в качестве календарных сроков некритических операций начала их ранних сроков, на рисунке 3 – потребность в рабочей силе при выборе наиболее поздних сроков. Жирной линией представлена потребность критических операций, которая должна быть удовлетворена, если нужно выполнить все работы в минимально возможный срок. Оптимальное решение задачи равномерного использования ресурсов представлено на рисунке 4, уточнённый график выполнения работ на рисунке 5. Учёт стоимостных факторов при реализации сетевого графика Стоимостные факторы при реализации сетевого графика учитываются путём определения зависимости «затраты - продолжительность» для каждой операции. При этом рассматриваются прямые затраты, а косвенные типа административных или управленческих расходов не принимаются во внимание. На рис. 6 показана линейная зависимость стоимости операции от её продолжительности. Точка (DB, CB), где DB – продолжительность операции, а CB – её стоимость, соответствует нормальному режиму выполнения операции. Продолжительность операции можно уменьшить (сжать), увеличив интенсивность использования ресурсов, а следовательно, увеличив стоимость операции. Однако существует предел, называемый минимальной продолжительностью операции. За точкой, соответствующей этому пределу (точка максимального интенсивного режима), дальнейшее увеличение интенсивности использования ресурсов ведёт лишь к увеличению затрат без сокращения продолжительности операции. Этот предел обозначен на рис. 6 точкой А с координатами (DА, CА). Для удобства зависимость «затраты - продолжительность» принимается линейной, так как её можно определить для любой операции по двум точкам. Если зависимость не линейная, то её использовать гораздо сложнее, и поэтому её можно аппроксимировать (приблизить) кусочно-линейной зависимостью (рис. 7), когда операция разбивается на части, каждая из которых соответствует одному линейному отрезку. Наклоны этих отрезков при переходе от точки нормального режима к точке максимального режима возрастают. Если это условие не выполняется, то аппроксимация не имеет смысла. Определив зависимость «затраты - продолжительность» для всех операций сети принимают нормальную продолжительность. Далее рассчитывается сумма затрат на все операции сети при этой продолжительности работ. На следующем этапе рассматривается возможность сокращения продолжительности работ. Этого можно достичь за счёт уменьшения продолжительности какой-либо критической операции. Анализу следует подвергать только критические операции. Чтобы добиться сокращения продолжительности выполнения работ при минимально возможных затратах, необходимо в максимально допустимой степени сжать ту критическую операцию, у которой наклон кривой «затраты - продолжительность» наименьший. В результате сжатия критической операции получается новый календарный график, возможно, с новым критическим путём. Стоимость работ при новом календарном графике будет выше стоимость работ по предшествующему графику. На следующем этапе тот новый график вновь подвергается сжатию за счёт следующей критической операции с минимальным наклоном кривой «затраты - продолжительность» при условии, что продолжительность этой операции не достигла минимального значения. Данная процедура повторяется, пока все критические операции не будут находиться в режиме максимальной интенсивности. Полученный оптимальный календарный график соответствует минимуму прямых затрат. Обоснование привлекательности проекта по выпуску продукции Для финансирования проектов по строительству и наладке изготовления конкурентоспособной продукции в большинстве случаев фирмам требуются инвестиции. Включение в проект материалов с оптимизацией сетевых моделей в части обоснования сроков возврата инвестиций делает проект более привлекательным и способствует принятию инвестором положительного решения. Пример. Предприятие решило для улучшения финансового состояния наладить выпуск конкурентоспособной продукции (мороженого). Для переоборудования цеха под выпуск этой продукции необходимо выполнить: 1) подготовку технического задания на переоборудование участка (30 дн.); 2) заказ и поставку нового оборудования (60 дн.); 3) заказ и поставку нового электрооборудования (50 дн.); 4) демонтаж старого и установку нового оборудования (90 дн.); 5) демонтаж старого и установку нового электрооборудования (80 дн.); 6) переобучение персонала (30 дн.); 7) испытания и сдачу в эксплуатацию оборудования для производства мороженого (20 дн.). Ожидается, что производительность после ввода новой линии составит 20 т мороженого в смену. Прибыль от реализации 1 т продукции составит 0,5 тыс. р. В смену. Деньги на покупку и переоборудование участка в размере 2 000 тыс. р.взяты в банке под 20% годовых (из расчёта 1 500 тыс. р. на закупку оборудования и 500 тыс. р. на работы по демонтажу старого оборудования и установке нового оборудования). Затраты на проведение работ в нормальном и максимальном режимах указаны в табл. Определить, через какое время может быть возвращён кредит в банк. Работа Нормальный режим Максимальный режим Продолжи- тельность, дн. Затраты, тыс. р. Продолжи- тельность, дн. Затраты, тыс. р. 1 2 3 4 5 6 7 30 60 50 90 80 30 20 20 40 30 70 60 25 20 25 45 40 70 65 20 17 30 60 40 100 70 25 25 Итого 360 265 282 350 РЕШЕНИЕ. 1. Составим график проведения работ по пуску новой линии: На проведение переоборудования необходимо 30 + 60 + 50 + 90 + 80 + 30 + 20 = 360 дн. 2. График можно улучшить, выполняя некоторые работы параллельно. На графике обозначены работы: 0, 1 – подготовка технического задания; 1, 2 – заказ и поставка нового оборудования; 1, 3 - заказ и поставка нового электрооборудования; 2, 4 – установка нового оборудования; 3, 4 - установка нового электрооборудования; 1, 4 – переобучение персона; 4, 5 – сдача в эксплуатацию новой линии. По графику путь (0, 1), (1, 2), 2, 4), (4, 5) имеет продолжительность 200 дн.; (0, 1), (1, 3), (3, 4), (4, 5) – 180 дн.; (0, 1), (1, 4), (4, 5) – 80 дн. Критическим путём графика является путь, на котором расположены работы (0, 1), (1, 2), 2, 4), (4, 5) продолжительностью 200 дн. График улучшился на 360 – 200 = 160 дн. Определим, через какое время после начала выпуска мороженого может быть возвращён кредит в банк. Через 200 дн. После начала работ предприятие истратит 1 500 тыс. р. На приобретение оборудования (по условию) и 265 тыс. р. На его установку и сдачу в эксплуатацию (из табл., столбец «Затраты» при нормальном режиме). В наличии у предприятия остаётся 2000 – 1500 – 265 = 235 тыс. р. Построим графики изменения кредита в зависимости от времени получения прибыли предприятием – от выпуска мороженого. Для построения графика изменения кредита в зависимости от времени составим уравнение. Через 360 дн. После выдачи банком кредита под 20% годовых долг предприятия составит 2400 тыс. р. Поэтому известны две точки прямой А (0, 2000), В (360, 2400). Составим уравнение прямой, проходящей через две точки: Решая уравнение, получим Найдём уравнение прибыли предприятия. Известно, что через 200 дн. После начала работ у предприятия осталось от кредита 235 тыс. р. Через 100 дн. После начала выпуска продукции предприятие получит прибыль тыс. р. и у него будет в наличии 1000 + 235 = 1235 тыс. р. Выбор оптимальной стратегии развития предприятия в условиях трансформации рынка Фирма может принять решение о строительстве среднего или малого предприятия. Малое предприятие впоследствии можно расширить. Решение определяется будущим спросом на продукцию, которую предполагается выпускать на сооружаемом предприятии. Строительство среднего предприятия экономически оправдано при высоком спросе. С другой стороны, можно построить малое предприятие и через два года его расширить. Фирма рассматривает данную задачу на десятилетний период. Анализ рыночной ситуации показывает, что вероятности высокого и низкого уровней спроса равны 0,7 и 0,3 соответственно. Строительство среднего предприятия обойдётся в 4 млн. р., малого – в 1 млн. р. Затраты на расширение через два года малого предприятия оцениваются в 3,5 млн. р. Ожидаемые ежегодные доходы для каждой из возможных альтернатив: - среднее предприятие при высоком (низком) спросе даёт 0,9 (0,2) млн. р.; - малое предприятие при низком спросе даёт 0,1 млн. р.; - малое предприятие при высоком спросе даёт 0,2 млн. р. в течение 10 лет; - расширенное предприятие при высоком низком) спросе даёт 0,8 (0,1) млн. р.; - малое предприятие без расширения при высоком спросе в течение первых двух лет и последующем низком спросе даёт 0,1 млн. р. в год за остальные восемь лет. Определить оптимальную стратегию фирмы в строительстве предприятий. РЕШЕНИЕ. Данная задача является многоэтапной, так как если фирма решит построить малое предприятие, то через два года она может принять решение о его расширении. В этом случае процесс принятия решения состоит из двух этапов: решение в настоящий момент времени о размере предприятия и решение о необходимости его расширения, принимаемое через два года. Принятие решения о замене оборудования в условиях неопределённости и риска Фирма может принять решение о замене старого оборудования на новое того же вида или его ремонте. Отремонтированное оборудование впоследствии можно частично заменить на новое, более современное, или отремонтировать его заново. Решение определяется будущим спросом на продукцию, которую производят на этом оборудовании. Полная замена оборудования экономически оправданна при высоком уровне спросе. С другой стороны, можно отремонтировать старое оборудование и через один год, например, заменить его на новое, более совершенное, или заново его отремонтировать. В данном случае процесс принятия решения состоит из двух этапов: решение в настоящий момент времени о замене или ремонте оборудования и решение, принимаемое через один год, относительно его частичной замены и ремонта. Пример. Рассмотрим задачу о замене оборудования фирмы, представив её в виде «дерева» решений. Предполагается, что спрос может оказаться высоким, средним и низким. Дерево имеет два типа вершин: «решающие» и «случайные». Начиная с «решающей» вершины 1 необходимо принять решение о полной замене оборудования или его ремонте. Вершины 2 и 3 являются «случайными». Фирма будет рассматривать возможность установления более совершенного оборудования или повторного ремонта старого в том случае, если спрос по истечении одного года установится на высоком уровне. Поэтому в вершине 4 принимается решение о частичной замене старого оборудования более совершенным или ремонте старого. Вершины 5 и 6 «случайные». Пусть фирма рассматривает эту задачу на пятилетний период. Анализ рыночной ситуации показывает, что вероятности высокого, среднего и низкого уровней спроса составляют 0,6, 0,3 и 0,1 соответственно. Замена новым оборудованием того же вида, что и старое, обойдётся в 2,5 млн. р., а ремонт старого – в 0,8 млн. р. Затраты на частичную замену оборудования на более совершенное, чем старое, оцениваются в 1,5 млн. р., а повторный ремонт старого – 0,8 млн. р. Ежегодные доходы для каждой стратегии фирмы следующие. 1. Замена старого оборудования на новое того же вида при высоком, среднем и низком уровнях спроса даёт ,95; 0,7 и 0,45 млн. р. соответственно. 2. Ремонт старого оборудования при высоком, среднем и низком уровнях спроса оценивается в 0,3; 0,15 и 0,1 млн. р. Соответственно. 3. Частичная замена оборудования на более совершенное при высоком, среднем и низком уровнях спроса составит 0,9; 0,6 и 0,4 млн. р. соответственно. 4. Повторный ремонт старого оборудования при высоком, среднем и низком уровнях спроса предполагается 0,3; 0,2 и 0,1 млн. р. соответственно. Определить оптимальную стратегию фирмы в замене оборудования. РЕШЕНИЕ. Оценим результаты каждой стратегии и определим, какие ешения следует принимать в «решающих» вершинах 1 и 4. Вычисления начнём с 2 этапа. Для последних 4 лет альтернативы, относящиеся к вершине 4, оцениваются так: млн. р., млн. р., где ДЧЗ – доход от частичной замены оборудования на более совершенное, ДДР – доход от замены оборудования, прошедшего дважды ремонт. Так как ДЧЗ > ДДР, то в вершине 4 выгоднее произвести частичную замену оборудования на более совершенное, при этом доход составит 1,54 млн. р. Для дальнейших расч1тов в вершине 4 можно оставить одну ветвь, которой соответствует доход в 1,54 млн. р. За 4 года. Вычислим доходы на 1-м этапе для «решающей» вершины 1: млн. р., млн. р., где ДЗН – доход от замены старого оборудования на новое того же вида, ДЗО – доход от отремонтированного оборудования и дальнейшей замены на более совершенное. Так как ДЗН > ДЗО, то оптимальным решение в вершине 1 является полная замена старого оборудования на новое того же вида. Элементы системы массового обслуживания (СМО) 1. Формулировка задачи и характеристики СМО Ожидание является следствием вероятностного характера возникновения потребностей в обслуживании и разброса показателей обслуживающих систем, которые называют системами массового обслуживания (СМО). Основными элементами СМО являются источники заявок, их входящий поток, каналы обслуживания и выходящий поток. Входящий поток: на практике наиболее распространённым является простейший поток заявок, обладающий свойствами стационарности, ординарности и отсутствия последействия. Стационарность характеризуется тем, что вероятность поступления определённого количества требований в течение некоторого промежутка времени зависит только от длины этого промежутка. Ординарность потока определяется невозможностью одновременного появления двух или более заявок. Отсутствие последействия характеризуется тем, что поступление заявки не зависит от того, когда и сколько заявок поступило до этого момента. В этом случае вероятность того, что число заявок, поступивших на обслуживание за промежуток времени t, равно k, определяется по закону Пуассона , где - интенсивность потока заявок, т. е. среднее число заявок в единицу времени: (чел./мин, р./ч, автом./дн., квт/ч), где - среднее значение интервала времени между двумя соседними заявками. Случайное время ожидания в очереди начала обслуживания находится по формуле: , где - интенсивность движения очереди, т. е. среднее число заявок, приходящих на обслуживание в единицу времени: , где - среднее значение времени ожидания в очереди. Выходящий поток заявок связан с потоком обслуживания в канале, где длительность обслуживания является случайной величиной и вычисляется по формуле , где - интенсивность потока обслуживания, т. е. среднее число заявок, обслуживаемых в единицу времени: (чел./мин, р./дн., кг/ч, докум./дн.), где - среднее время обслуживания. Важной характеристикой СМО, объединяющей и , является интенсивность нагрузки . 2. СМО с отказами Пример 1. В ОТК цеха работают три контролёра. Если деталь поступает в ОТК, когда все контролёры заняты обслуживанием ранее поступивших деталей, то она проходит непроверенной. Среднее число деталей, поступающих в ОТК в течение часа, равно 24, среднее время, которое затрачивает один контролёр на обслуживание одной детали, равно 5 мин. Определить вероятность того, что деталь пройдёт ОТК необслуженной, насколько загружены контролёры и сколько их необходимо поставить, чтобы . РЕШЕНИЕ. дет./ ч = 0,4 дет./ мин, = 5 мин, тогда 1. Вероятность простоя каналов обслуживания: , где 0! = 1. 2. Вероятность отказа в обслуживании: 3. Вероятность обслуживания: 4. Среднее число занятых обслуживанием каналов: 5. Доля каналов, занятых обслуживанием: 6. Абсолютная пропускная способность: При п = 3 Произведя аналогичные расчёты для п = 4, получим Так как то произведя расчёты для п = 5, получим Ответ. Вероятность того, что при п = 3 деталь пройдёт ОТК необслуженной, составляет 21%, и контролёры будут заняты обслуживанием на 53%. Чтобы обеспечить вероятность обслуживания более 95%, необходимо не менее пяти контролёров. 3. СМО с неограниченным ожиданием Пример 2. Сберкасса имеет трёх контролёров-кассиров (п = 3) для обслуживания вкладчиков. Поток вкладчиков поступает в сберкассу с интенсивностью чел./ч. Средняя продолжительность обслуживания контролёром-кассиром одного вкладчика мин. Определить характеристика сберкассы как объекта СМО. РЕШЕНИЕ. Интенсивность потока обслуживания , интенсивность нагрузки 1. Вероятность простоя контролёров-кассиров в течение рабочего дня: 2. Вероятность застать всех контролёров-кассиров занятыми: 3. Вероятность очереди: 4. Среднее число заявок в очереди: 5. Среднее время ожидания заявки в очереди: мин. 6. Среднее время пребывания заявки в СМО: мин. 7. Среднее число свободных каналов: где 8. Коэффициент занятости каналов обслуживания: 9. Среднее число посетителей в сберкассе: чел. Ответ. Вероятность простоя контролёров-кассиров равна 21% рабочего времени, вероятность посетителю оказаться в очереди составляет 11,8%, среднее число посетителей в очереди 0,236 чел., среднее время ожидания посетителями обслуживания 0,472 мин. 4. СМО с ожиданием и с ограниченной длиной очереди Пример 3. Магазин получает ранние овощи из пригородных теплиц. Автомобили с грузом прибывают в разное время с интенсивностью машин в день. Подсобные помещения и оборудование для подготовки овощей к продаже позволяют обрабатывать и хранить товар, привезённый двумя автомашинами (т = 2). В магазине работают три фасовщика (п = 3), каждый из которых в среднем может обрабатывать товар с одной машины в течение ч. Продолжительность рабочего дня при сменной работе составляет 12 ч. Определить, какова должна быть ёмкость подсобных помещений, чтобы вероятность полной обработки товаров была РЕШЕНИЕ. Определим интенсивность загрузки фасовщиков: авт./дн. 1. Найдём вероятность простоя фасовщиков при отсутствии машин (заявок): причём 0! = 1,0. 2. Вероятность отказа в обслуживании: 3. Вероятность обслуживания: Так как произведём аналогичные вычисления для т = 3, получим Так как примем т = 4. Получим 0,972 > 0,97, ёмкость подсобных помещений необходимо увеличить до т = 4. Для достижения заданной вероятности обслуживания можно увеличить число фасовщиков, проводя последовательно вычисления СМО для п = 4, 5 и т. д. Задачу можно решить, увеличивая ёмкость подсобных помещений, число фасовщиков, уменьшая время обработки товаров. Найдём остальные параметры СМО для рассчитанного случая при 4. Абсолютная пропускная способность: авт./дн. 5. Среднее число занятых обслуживанием каналов (фасовщиков): 6. Среднее число заявок в очереди: 7. Среднее время ожидания обслуживания: дн. 8. Среднее число машин в магазине: авт. 9. Среднее время пребывания машины в магазине: дн. Ответ. Ёмкость подсобных помещений магазина должна вмещать товар, привезённый 4 автомашинами (т = 4), при этом вероятность полной обработки товара будет