Транспортная задача.

§2. Транспортная задача 2.1. Основные понятия, построение опорного плана перевозок Решение транспортной задачи (ТЗ) состоит из трех этапов: – составление математической модели; – нахождение опорного (первоначального) плана; – нахождение оптимального плана. Второй этап желательный, но не обязательный. Сформулируем условие ТЗ в общем виде. Имеется несколько пунктов производства или сосредоточения какогото однородного продукта (например, нефти или картофеля). Имеется некоторое количество пунктов, испытывающих потребность в этом продукте – пункты потребления. Запасы в каждом пункте известны. Транспортные издержки, связанные с произвольной перевозкой, заданы. Необходимо составить такой план перевозок продукта из пунктов производства в пункты потребления, при котором весь продукт был бы перевезен в пункты потребления, каждый пункт потребления был бы полностью удовлетворен и суммарные транспортные затраты оказались минимальными. Переведем условие задачи на математический язык. Введем обозначения. Пусть Ai – пункты производства (их число m), Bj – пункты потребления (их число n), ai – количество продукта в пункте Ai, bj – количество продукта в пункте Bj. Примем допущения, что стоимость перевозки продукции линейно зависит от количества перевозимой продукции. Пусть cij(x) – стоимость перевозки x единиц продукта из Ai в Bj. С учетом наших допущений имеем cij(x) = cijx, где cij – стоимость перевозки одной единицы продукта из Ai в Bj. В качестве параметров управления выберем xij – количество продукта, перевозимого из Ai в Bj. Тогда суммарные транспортные издержки (целевую функцию задачи) можно определить как m n f ( x)   cij xij . i 1 j 1 Составим ограничения. Необходимо вывести весь продукт из каждого пункта производства n  xij  ai , (i = 1, 2, …, m) и удовлетворить полностью j 1 потребность пунктов потребления m  xij  b j , (j = 1, 2, …, n). Поскольку i 1 перевозки идут из пунктов производства в пункты потребления, то добавим ограничения xij  0 для любых i и j ( i, j ). Составители: Балашов А.Н В данной задаче производство полностью удовлетворяет потребление (выполняется условие баланса) m n i 1 j 1  ai   b j . В результате мы имеем математическую модель ТЗ: m n f ( x)   cij xij  min, i 1 j 1  n   xij  ai , i  1, m,  jm1   xij  b j , j  1, n,  i 1  xij  0, i, j.  Для нахождения опорного плана обычно используют методы: – метод «северо-западного угла»; – метод добротностей; – метод наименьших стоимостей или минимального элемента; – метод двойного предпочтения. Транспортные задачи, в которых производство полностью удовлетворяет потреблению, получили название закрытыми или замкнутыми транспортными задачами с выполнением условия баланса. Пример 1.12. Имеются два пункта производства товара a1 = 10, a2 = 20 и два пункта потребления b1 = 5, b2 = 25. Стоимость перевозок единицы груза из пунктов производства в пункты потребления задана c11 = 1, c12 = 2, c21 = 3, c22 = 1. Необходимо составить математическую модель плана перевозок продукта из пунктов производства в пункты потребления, при котором весь продукт был бы перевезен в пункты потребления, каждый пункт потребления был бы полностью удовлетворен и суммарные транспортные затраты оказались минимальными. Решение. Поскольку условие баланса выполняется (10 + 20 = 5 + 25), то ТЗ является замкнутой и все ограничения записываются в виде равенств. Пусть xij – количество продукта, перевозимого из i-го пункта производства в j-ый пункт потребления. Тогда F(x) = x11 + 2x12 + 3x21 + x22  min,  x11  x12  10,  x  x  20, 22  21  x11  x21  5,  x  x  25, 22  12  xij  0, i, j. Составители: Балашов А.Н Первое ограничение показывает, что из 1-го пункта производства необходимо вывезти товар в 1-й и 2-й пункты потребления x11 + x12 в количестве a1 = 10. Аналогично 2-е ограничение. Третье ограничение показывает, что в 1-й пункт потребления необходимо привезти товар из 1-го и 2-го пунктов производств x11 + x21 в количестве b1 = 5. Аналогично 4-ое ограничение. Составим первоначальный план перевозок методом наименьших стоимостей с двойным предпочтением. Исходные данные ТЗ представим в виде транспортной таблицы 1.23. Таблица 1.23 ai/bj a1 =10 a2 = 20 ** b1 = 5 1 3 b2 = 25 2 1** Отмечаем клетки с наименьшими стоимостями перевозок по каждой строке и каждому столбцу. Клетки, имеющие две отметки, заполняем в первую очередь. В клетке a1b1 записываем число 5 и вычеркиваем полностью заполненный столбец b1. В клетке a2b2 записываем число 20 и вычеркиваем полностью заполненную строку a2 (табл. 1.24). Таблица 1.24 ai/bj a1 =10 a2 = 20 b1 = 5 5 b2 = 25 20 Заполняем клетки с одной отметкой с учетом заявок производителей и потребителей, затем заполняем клетки без отметок. Осталась одна клетка a1b2. В нее записываем число 5 (табл. 1.25). Таблица 1.25 ai/bj a1 =10 a2 = 20 b1 = 5 5 b2 = 25 5 20 Решение с помощью MS Excel дает [3, Лист 1]: f(x) = 35, x11 = 5, x12 = 5, x22 = 20. В нашем случае опорный план совпал с оптимальным решением. Рассмотрим транспортную задачу, в которой не выполняется условие баланса. Такую ТЗ задачу называют открытой. Пример 1.13. Имеются два пункта производства товара и два пункта потребления a1 = 10, a2 = 25, b1 = 10, b2 = 30, стоимость перевозок товара задана c11 = 4, c12 = 2, c21 = 3, c22 = 1. За недопоставку одной единицы товара первый пункт потребления терпит убыток в размере 1, а второй – 0,5. Необходимо составить математическую модель плана перевозок продукта из пунктов производства в пункты потребления, при котором Составители: Балашов А.Н весь продукт был бы перевезен в пункты потребления, а суммарные транспортные затраты и убытки оказались минимальными. Решение. Введем обозначения. Пусть xij – количество продукта, перевозимого из i-го пункта производства в j-й пункт потребления, z1  b1  x11  x21 , z 2  b2  x12  x22 – количество недопоставленного товара соответственно в 1-й и 2-й пункты потребления. Составим математическую модель. F(x) = 4x11 + 2x12 + 3x21 + x22 + z1 + 0,5z2  min,  x11  x12  10,  x  x  25, 22  21  x11  x21  10,  x  x  30, 22  12  xij  0, i, j. Прежде чем решать открытую ТЗ задачу ее необходимо сбалансировать (при решении задачи в MS Excel это можно не делать). Вводим дополнительный фиктивный пункт производства ai1 (в случае дефицита товара) или фиктивный пункт потребления b j 1 (в случае профицита товара). Мощность дополнительно введенного фиктивного пункта равна количеству недопоставленного или избыточного товара. Для нашего случая введем фиктивный пункт производства a3 = (30+10) – (25+10) = 5. Стоимость перевозок из фиктивного пункта производства равна нулю. Поэтому целевая функция не меняется, а система ограничений принимает вид:  x11  x12  10,  x  x  25, 21 22   x31  x32  5,   x11  x21  x31  10,  x12  x22  x32  30,  xij  0, i, j.  Решение с помощью MS Excel дает [3, Лист 2]: f(x) = 60, x12 = 10, x21 = 5, x22 = 20. Пример 1.14. Завод имеет три цеха A, B, C и четыре склада №№ 1, 2, 3, 4. Цех A производит 30 тыс. шт. изделий, цех B – 40 тыс. шт., цех C – 20 тыс. шт. за плановое время. Пропускная способность складов за то же время: склад № 1 – 20 тыс. шт., склад № 2 – 30 тыс. шт., склад №3 – 30 тыс. шт., склад №4 – 10 тыс. шт. Стоимости перевозок 1-й тыс. шт. изделий в склады №№ 1, 2, 3, 4 соответственно равны: из цеха A – 2, 3, 3, 4 ден. eд., из цеха B – 3, 2, 5, 1 ден. eд., из цеха C – 4, 3, 2, 6 ден. ед. Составители: Балашов А.Н Составить план перевозок, при котором расходы на перевозку всех изделий минимальны. Решение. Условие баланса выполняется 3 4 i 1 j 1  ai   b j  90 . Поэтому ТЗ является замкнутой и все ограничения записываем в виде равенств. Пусть xij (тыс. шт.) – количество изделий, перевозимых из i-го цеха в j-й склад. Тогда математическая модель задачи будет иметь вид: F(x) = 2x11 + 3x12 + 3x13 + 4x14 + 3x21 + 2x22 + 5x23 + x24 + + 4x31 + 3x32 + 2x33 + 6x34  min,  x11  x21  x31  20,  x  x  x  30,  x11  x12  x13  x14  30, 22 32  12  цеха:  x21  x22  x23  x24  40, склады:  x13  x23  x33  30,  x  x  x  10,  x  x  x  x  20, 24 34 32 33 34  31  14 xij  0.  Составим первоначальный план перевозок методом наименьших стоимостей с двойным предпочтением. Исходные данные ТЗ представим в виде транспортной таблицы. Отмечаем клетки с наименьшими стоимостями перевозок по каждой строке и каждому столбцу (табл. 1.26). Таблица 1.26 ai/bj b1 = 20 b2 = 30 b3 = 30 b4 = 10 2** 3 3 4 a1 =30 3 2* 5 1** 4 3 2** 6 a2 = 40 a3 = 20 Клетки, имеющие две отметки, заполняем в первую очередь с учетом заявок производителей и потребителей: x11 = 20 (вычеркиваем 1-й полностью заполненный столбец), x24 = 10 (вычеркиваем 4-й столбец), x33 = 20 (вычеркиваем 3-ию строку). Затем заполняем клетки с одной отметкой с учетом заявок производителей и потребителей: x22 = 30 (вычеркиваем 2-й столбец и 2-ю строку). Остается клетка a1b3 = x13 = 10 (табл. 1.27). Таблица 1.27 ai/bj a1 =30 a2 = 40 a3 = 20 b1 = 20 b2 = 30 b3 = 30 b4 = 10 2** 3 3 4 20 10 3 2* 5 1** 30 10 4 3 2** 6 20 Составители: Балашов А.Н Получили начальный план перевозок: x11 = 20, x13 = 10, x22 = 30, x24 = 10, x33 = 20, f(x) = 180 ден. ед. Нахождение оптимальнго плана перевозок описано в п. 2.3 данной главы. 2.2. Создание оптимального плана перевозок Для получения оптимального плана перевозок разработано несколько методов: – распределительный метод; – метод потенциалов; – дельта-метод; – аппроксимация Фогеля. Рассмотрим метод потенциалов, который широко применяется на практике и используется при программировании. На первом этапе составляют начальный план перевозок. На втором этапе строят систему потенциалов и проверяют начальный план на оптимальность. Каждому i-му поставщику устанавливается потенциал U i , который можно интерпретировать как цену продукта в пункте поставщика, а каждому j-му потребителю устанавливается потенциал V j , который характеризует цену продукта в пункте потребителя. Если начальный план является неоптимальным, то переходят к третьему этапу, суть которого заключается в корректировке плана прикрепления потребителей и поставщиков. После чего переходят снова ко второму этапу и т.д. Пример 1.15. Фирма должна отправить шкафы с трех складов в три магазина. На складах имеется соответственно 15, 25 и 10 шкафов, а для трех магазинов требуется соответственно 20, 12, и 18 шкафов. Стоимость перевозки C ij одного шкафа со склада ai в магазин b j приведена в табл. 1.28. Таблица 1.28 Склады a1 a2 a3 Магазины b1 b2 6 3 3 7 2 8 b3 4 2 6 Как следует спланировать перевозку, чтобы её стоимость была минимальной? Решение. Условие баланса выполняется 3 3 i 1 j 1  ai   b j  50 . Поэтому ТЗ является замкнутой и все ограничения записываем в виде равенств. На первом этапе получаем первоначальный план перевозок методом наименьших стоимостей с двойным предпочтением (табл. 1.29). Составители: Балашов А.Н Таблица 1.29 ai/bj 6 a1 =15 3 a2 = 25 2** a3 = 10 Vj Ui b2 = 12 b3 = 18 3** 4 U1  0 3 12 7 2** U2  3 7 18 8 6 U3  4 10 b1 = 20 V1  6 V2  3 V3  5 Начальный план: x11 = 3, x12 = 12, x21 = 7, x23 = 18, x31 = 10, f(x) = 131. На втором этапе построим систему потенциалов U i и V j для начального опорного плана. Для занятых клеток составляем систему линейных уравнений вида V j  U i  Cij : V1  U1  6 , V1 U 2  3 , V1 U 3  2 , V2 U1  3 , V3 U 2  2 . Полагаем U1  0 , тогда V1  6 , U 2  3 , U 3  4 , V2  3 , V3  5 . Найденные потенциалы указаны в табл. 1.29. Для того чтобы опорный план был оптимальным, необходимо и достаточно, чтобы система потенциалов U i и V j удовлетворяла следующему условию: V j  U i  Cij для xij  0 (для занятой клетки); V j  U i  Cij для xij  0 (для незанятой клетки). Для незанятых клеток проверим условие оптимальности: V2  3  U 2  C22  3  7  10 , V2  3  U 3  C32  4  8  12 , V3  5  U1  C13  0  4  4 , V3  5  U 3  C33  4  6  10 . Третье неравенство или клетка a1b3 не удовлетворяет условию оптимальности, поэтому переходим к третьему этапу. Для незанятых клеток, не удовлетворяющих условию оптимальности, находим наибольшую величину  ij  V j  U i  Cij : 13  V3  U1  C13  5  0  4  1. Клетка a1b3 является положительной вершиной цикла. Строим замкнутый контур, начальная вершина которого находится в выбранной клетке, а остальные вершины контура находятся в занятых клетках. Линии контура могут быть отрезки либо горизонтальные, либо вертикальные. Число отрезков и вершин будет четным. Первая вершина контура свободной клетки имеет знак «+», а в остальных вершинах контура расставляются поочередно знаки «–» и «+» как показано в табл. 1.30. Составители: Балашов А.Н Таблица 1.30 ai/bj b1 = 20 6 3 a1 =15 3 3 b3 = 18 4 2 7 2 a3 = 10 18 8 6 V2  3 U2  3 U3  4 10 V1  6 Ui U1  0 12 7 a2 = 25 Vj b2 = 12 V3  5 Выбираем наименьшее из величин в вершинах контура с отрицательным знаком min3, 18  3 .Уменьшаем на три единицы величину каждой вершины со знаком «–» и увеличиваем на три единицы величину каждой вершины со знаком «+». Результат получаем в табл. 1.40. Таблица 1.40 ai/bj b1 = 20 6 b2 = 12 3 a1 =15 3 7 8 10 V1  5 V2  3 Ui 3 U1  0 15 U2  2 2 10 2 Vj 4 12 a2 = 25 a3 = 10 b3 = 18 6 U3  3 V3  4 Новый опорный план: x12 = 12, x13 = 3, x21 = 10, x23 = 15, x31 = 10, f(x) = 128. Найдем потенциалы и проверим новый опорный план на оптимальность. Для занятых клеток составляем систему линейных уравнений вида V j  U i  Cij : V1 U 2  3 , V1 U 3  2 , V2 U1  3 , V3 U1  4 , V3 U 2  2 . Полагаем U1  0 , тогда V2  3 , V3  4 U 2  2 , V1  5 , U 3  3 . Найденные потенциалы указаны в табл. 1.40. Для незанятых клеток проверим условие оптимальности: V1  5  U1  C11  0  6  6 , V2  3  U 2  C22  2  7  9 , V2  3  U 3  C32  3  8  11, V3  4  U 3  C33  3  6  9 . Полученный новый опорный план удовлетворяет всем условиям оптимальности. Поэтому новый опорный план x12 = 12, x13 = 3, x21 = 10, x23 = 15, x31 = 10, f(x) = 128 является оптимальным. Составители: Балашов А.Н 2.3. Решение транспортной задачи с помощью MS Excel Решим пример 1.14 с применением стандартных средств табличного процессора MS Excel. Создадим экранную форму на листе MS Excel и введем данные задачи. В ячейках A2:A4 указаны производственные мощности цехов 1 – 3, в ячейках B1:E1 – производственные мощности складов 1 – 4, в ячейках B2:E4 – тарифы по перевозке тысячи единиц изделий, перевозимых из i-го цеха в j-й склад. Ячейки G2:J4 соответствуют численным значениям переменных xij , ячейки K2:K4 – левым частям ограничений для цехов, ячейки G5:J5 – левым частям ограничений для складов, ячейка F2 является целевой функцией f(x). В ячейки G2:J4 введем значения переменных начального плана: x11 = 20 (ячейка G2), x13 = 10 (ячейка I2), x22 = 30 (ячейка H3), x24 = 10 (ячейка J3), x33 = 20 (ячейка I4). В результате получим табл. 1.41: 1 2 3 4 5 A B C D E 30 40 20 20 2 3 4 30 3 2 3 30 3 5 2 10 4 1 6 F f(x) G H I J Таблица 1.41 K xij 20 10 30 10 20 Вводим зависимости из математической модели в ячейки K2:K4, G5:J5, F2 используя: окно диалога Мастер функций (fx Вставить функцию), категория Математические, в алфавитном списке Выберите функцию выбираем функцию СУММ для ячеек K2:K4, G5:J5 и СУММПРОИЗВ для целевой ячейки F2. Функция может быть введена непосредственно с клавиатуры. Содержимое ячеек: K2=СУММ(G2:J2), K3=СУММ(G3:J3), K4=СУММ(G4:J4), G5=СУММ(G2:G4), H5=СУММ(H2:H4), I5=СУММ(I2:I4), J5=СУММ(J2:J4), F2=СУММПРОИЗВ(B2:E4;G2:J4). В результате получим табл. 1.42: 1 2 3 4 5 A B C D E 30 40 20 20 2 3 4 30 3 2 3 30 3 5 2 10 4 1 6 F f(x) 180 G H I J Таблица 1.42 K xij 20 10 30 20 30 10 20 30 30 40 20 10 Составители: Балашов А.Н Для назначения целевой функции используем команду ДанныеǀПоиск решения. В диалоговом окне Поиск решения: В поле Установить целевую ячейку указываем ячейку целевой функции $F$2 (рис. 1.7). Если перед вызовом инструмента Поиск решения выделить ячейку с целевой функцией $F$2, то это поле уже будет заполнено. В элементе управления Равной выбираем максимальному значению (рис. 1.7). В элементе управления Изменяя ячейки указываем диапазон $G$2:$J$4 (рис. 1.7), в котором размещены численные значения переменных. Рис. 1.7 Ввод ограничений выполняется с помощью кнопки Добавить в списке Ограничения (см. рис. 1.7). На экране появится диалоговое окно (рис. 1.8). Вводим поочередно условие неотрицательности переменных: $G$2:$J$4 ≥ 0 (рис. 1.8), Добавить. Рис. 1.8 Вводим ограничения поставщиков продукции (объем производимых изделий каждым цехом): $K$2:$K$4 = $A$2:$A$4 (рис. 1.9), Добавить. Составители: Балашов А.Н Рис. 1.9 Аналогично добавляем ограничения потребителей продукции (объем пропускной способности изделий каждого склада): $G$5:$J$5 = $B$1:$E$1 (рис. 1.10), OK. Рис. 1.10 На этом ввод условий задачи заканчивается. Для решения используем кнопку Параметры диалогового окна Поиск решения. Устанавливаем флажок Линейная модель, что обеспечит применение симплекс-метода, и устанавливаем флажок Неотрицательные значения, что обеспечит условие неотрицательности переменных (рис. 1.11). Рис. 1.11 В диалоговом окне Поиск решения выбираем Выполнить. Составители: Балашов А.Н В диалоговом окне Результаты поиска решения приводятся результаты решения и даются типы отчета. Выбираем Сохранить найденное решение, OK.Решение с помощью MS Excel [3, Лист 3]: x11 = 20, x13 = 10, x22 = 30, x24 = 10, x33 = 20, f(x) = 180. 2.4. Приложение транспортной задачи Транспортная задача применяется при решении экономических задач, которые по своему характеру не имеют ничего общего с транспортировкой груза, поэтому величины Cij могут иметь различный смысл. Например, означать стоимость, расстояние, время, производительность и т.д. Рассмотрим постановку и математические модели некоторых задач. 1. Оптимальное закрепление за станками операций по обработке деталей. На предприятии имеется m видов станков, максимальное время работы которых соответственно равно ai (i = 1, 2,…, m) часов. Каждый из станков может выполнять n видов операций. Суммарное время выполнения каждой операции соответственно равно bj (j = 1, 2, …, n) часов. Известна производительность Cij i-го вида станка при выполнении j-й операции. Необходимо определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Пример 1.16. На предприятии имеются два различных станка, каждый из которых может выполнять три вида элементарных операций по обработке детали, причем операции могут производиться в любом порядке. Максимальное время работы каждого станка соответственно равно 380 и 400 ч; каждая операция должна выполняться соответственно в течение 336, 224 и 220 ч. Необходимо определить, сколько времени и на какой операции нужно использовать каждый станков, чтобы обработать максимальное количество деталей, производительность каждого станка Cij (i = 1, 2; j = 1, 2, 3) приведена в табл. 1.43. Таблица 1.43 Станки 4 3 Операции 3 4 6 3 Решение. Обозначим через xij время, которое i-й станок должен работать на j-ой операции. Тогда, количество деталей, обработанных на i-м станке, равно 3  Cij xij . Количество деталей, обработанных на всех станках, j 1 Составители: Балашов А.Н m n можно выразить целевой функцией f ( x)   Сij xij . Так как максимально i 1 j 1 возможное время работы i-го станка ограничено (a1 = 380, a2 = 400), то получаем ограничения 3  xij  ai . С другой стороны, время, отведенное на j 1 j-ю операцию, равно bj часов, поэтому m  xij  b j . i 1 В итоге получаем математическую модель, записанную в общем виде: m n f ( x)   Cij xij  max i 1 j 1 n m i 1 j 1  xij  a j ,  xij  bi , xij  0. С учетом численных значений имеем: f ( x)  4 x11  3x12  6 x13  3x21  4 x22  3x23  max ,  x11  x21  336,  x11  x12  x13  380,   x12  x22  224, xij  0.   x21  x22  x23  400,  x  x  220, 23  13 Поскольку суммарное время работы станков равно суммарному времени обработки деталей (380 + 400 = 336 + 224 + 220 = 780), то первую группу ограничений можно записать в виде равенств. Решение с помощью MS Excel [3, Лист 4]: f(x) = 3384, x11  160, x13  220, x21  176, x 22  224. 2. Оптимальные назначения или проблема выбора. Пусть имеются m лиц, которые могут выполнять различные m работ. Известна производительность Cij i-го лица при выполнении j-й работы. Необходимо определить, кого и на какую работу следует назначить, чтобы добиться максимальной суммарной производительности при условии, что каждое лицо может быть назначено только на одну работу. Для составления математической модели обозначим через xij назначение i-го лица на j-ю работу. Тогда, так как количество лиц равно количеству работ и каждое из них может быть назначено только на одну работу, xij принимает только два значения: 1, если i-е лицо назначается для выполнения j-й работы; 0, если i-е лицо не назначается для выполнения j-й работы. Поэтому m xij  1  i 1 и m  xij  1 . При назначении i-го лица на j-ю j 1 работу производительность равна Cijxij. Таким образом, приходим к программирования: следующей задаче линейного Составители: Балашов А.Н m m f ( x)   Cij xij  max i 1 j 1 m m i 1 j 1  xij  1,  xij  1, xij  0. Если количество лиц больше количества работ, то вводят либо фиктивную работу с нулевой производительностью, либо вторую часть ограничений записывают в виде неравенств. Пример 1.17. На предприятии 5 станков различных видов, каждый из которых может выполнять 5 различных операций по обработке деталей. В табл. 1.44 приведена производительность каждого станка при выполнении каждой операции. Необходимо определить, какую операцию и за каким станком следует закрепить, чтобы суммарная производительность была максимальной при условии, что за каждым станком закреплена только одна операция. Станки Таблица 1.44 5 6 4 3 5 3 2 3 4 6 Операции 4 6 5 3 3 6 4 6 4 2 7 5 6 3 5 Задача имеет несколько оптимумов. Решение с помощью MS Excel ([3, Лист 5] при использовании линейной модели): f(x) = 28, x15 = x23 = x34 = x41 = x52 = 1, f(x) = 28, x15 = x21 = x33 = x44 = x52 = 1, f(x) = 28, x15 = x21 = x34 = x43 = x52 = 1. 3. Задача об использовании мощностей или задача о загрузке оборудования. Предприятию задан план производства продукции по времени и номенклатуре: требуется за время T выпустить n1, n2, …, nk единиц продукции P1, P2, …, Pk. Продукция производится на станках S1, S2, …, Sm. Для каждого станка известны производительность aij (число единиц продукции Pj, которое можно произвести на станке Si) и затраты bij на изготовление продукции Pj на станках Si в единицу времени. Необходимо составить такой план работы станков, чтобы затраты на производство всей продукции были минимальными. Пример 1.18. Предприятию необходимо выпустить за месяц 1 200 изделий типа A и 1 000 изделий типа B. Предприятие имеет два станка. Первый станок за час производит 6 изделий типа A или 5 изделий типа B, а второй, соответственно, 4 или 3. При изготовлении изделий А типа на первом станке затраты составляют 10 ден. ед. в час, а на втором 8 ден. ед. в Составители: Балашов А.Н час. При изготовлении изделий В типа на первом станке затраты составляют 5 ден. ед. в час, а на втором 4 ден. ед. в час. Необходимо составить такой план работы станков, чтобы затраты на производство всей продукции были минимальными. Каждый станок может работать в две смены (каждая по 8 часов) в течение 20 дней. Решение. Обозначим через xij количество изделий j – типа изготовленных на i-м станке. Если на первом станке будет произведено x11 изделий типа А, то суммарное время, израсходованное первым станком на изготовление изделий типа А составляет x11/6 часов. Аналогично для изделия типа B – x12/5 часов, а для другого станка – x21/4 часов и x22/3 часов. Затраты на производство всей продукции составят: 10 4 f ( x)  x11  x12  2 x21  x22 . 6 3 Каждый станок может работать в две смены (каждая по 8 часов) в течение 20 дней, т.е. 2*8*20 = 320 часов. В итоге получаем два ограничения: x11 x12 x x   320 , 21  22  320 . 6 5 4 3 Предприятию необходимо выпустить за месяц 1 200 изделий типа A и 1000 изделий типа B: x11 + x21 = 1 200, x12 + x22 = 1 000. В итоге получаем математическую модель: 10 4 f ( x)  x11  x12  2 x21  x22  min , 6 3  x11 x12  x11  x21  1 200,  6  5  320,  1)  2)  x12  x22  1 000, x x   21  22  320, xij  N 0 .  4 3  Решение с помощью MS Excel [3, Лист 6]: f(x) = 3 113 ден. ед., x11 = 1 200, x12 = 600, x22 = 400. Составители: Балашов А.Н