5.1 Цель работы: изучение методики решения задач по распределению производственных программ о комплектном выпуске продукции.
5.2 Теоретическая часть
Все данные о задаче представим в виде таблицы 5.1.
Таблица 5.1 – Данные о задаче
| Станки | Количество обработанных на станке деталей вида | |||
| … | 
| |||
| 
| 
| … | 
|
| … | … | … | … | … |
| 
| 
| … | 
|
| Число деталей в одном комплекте | 
| 
| … | 
|
Составим математическую модель станковой задачи. Пусть 
– часть рабочего дня, в течение которой на 
-м станке обрабатываются детали 
-го вида, 
, 
. Тогда план работы станков можно представить матрицей
| X= | Станки | Детали вида | ||
| … | n | |||
|
| 
| 
| … | 
|
| … | … | … | … | … |
|
| 
| 
| … | 
|
Обозначим через 
число комплектов деталей, которое будет получено в соответствии с этим планом.
Принимая рабочий день за единицу, составим систему ограничений. Суммарное время работы каждого станка по обработке всех деталей не должно превышать рабочего дня, тогда
, . (5.1)
Время, затраченное каждым станком по обработке деталей каждого вида, не может принимать отрицательное значение, поэтому должны выполняться неравенства
, , . (5.2)
Количество деталей -го вида, обработанных всеми станками по плану 
равно 
. Поскольку в один полный комплект входит 
деталей -го вида, то из этих деталей можно было бы получить 
комплектов. Подразумевается, что это количество округляется до целого в меньшую сторону. В один полный комплект входят детали разных видов, поэтому общее число комплектов равно
. (5.3)
По условию это число должно быть максимальным. Тогда получим задачу максимизации целевой функции (5.3) при условии, что неизвестные удовлетворяют системе ограничений (5.1)-(5.2).
Математическая модель (5.1)-(5.3) представляет собой задачу выпуклого программирования. Действительно, поскольку система ограничений состоит из линейных неравенств, то допустимая область задачи является выпуклой. Целевая функция (5.3) представляет собой минимум из линейных функций. Нетрудно доказать, что если функции 
, 
, …, 
– линейны, то функция 
является вогнутой. Это утверждение рекомендуется доказать самостоятельно, исходя из определения вогнутой функции нескольких переменных. В случае функций одной переменной указанное утверждение можно пояснить геометрически. На рисунке 5.1 представлены графики трех линейных функций (прямые линии) и минимум этих функций (жирная ломаная линия). Очевидно, что эта последняя функция вогнута.
Рисунок 5.1 - Иллюстрация вогнутой функции
Тем самым задача (5.1)-(5.3) есть задача максимизации вогнутой функции 
на выпуклой допустимой области, и, следовательно, математическая модель относится к выпуклому программированию.
5.3 Пример выполнения работы
На двух станках могут обрабатываться детали трех видов. В течение рабочего дня на первом станке может быть обработано 30 деталей первого вида, или 30 деталей второго вида, или 42 детали третьего вида. На втором станке в течение рабочего дня может быть обработано 18 деталей первого вида, или 50 деталей второго вида, или 150 деталей третьего вида.
Пусть 2 детали первого вида, 5 деталей второго вида и 3 детали третьего вида составляют один полный комплект. Определить оптимальный план работы станков, то есть указать, какую часть рабочего дня каждый станок должен обрабатывать детали каждого вида с тем, чтобы число комплектов деталей было наибольшим.
Перечисленные данные запишем в таблицу 5.2.
Таблица 5.2 - Данные
| Станки | Детали | ||
| I | |||
| II | |||
| Комплектность | 2: 5: 3 |
Составим математическую модель станковой задачи. Пусть – часть рабочего дня, в течение которой на -м станке обрабатываются детали -го вида, 
, 
. Тогда план работы станков можно представить таблицей
| XХ = | Станки | Детали | |
|
|
|
| 
|
| 
| 
| 
|
Обозначим через число комплектов деталей, которое будет получено в соответствии с этим планом.
Поскольку рабочий день принят за единицу, то имеем систему ограничений на время работы каждого станка
. (5.4)
Условия не отрицательности неизвестных:
, , . (5.5)
Чтобы составить целевую функцию, найдем количество деталей каждого вида, обработанных двумя станками по плану :
– количество деталей первого вида,
– количество деталей второго вида,
– количество деталей третьего вида.
Так как один комплект состоит из 2 деталей первого вида, 5 деталей второго вида и 3 деталей третьего вида, то общее число комплектов деталей выражается функцией
. (5.6)
Таким образом, математической моделью станковой задачи является задача максимизации целевой функции (5.6) при условиях (5.4)-(5.5).
Рассмотрим два плана обработки деталей. По плану
| X1 = | Станки | Детали | |
|
| 
| 
| 
|
|
| 
| 
| 
|
число комплектов деталей составляет
.
Так как число комплектов должно быть целым, то считаем, что 
.
Второй (оптимальный) план получим с помощью процедуры «Поиск решения» табличного процессора Excel. Математическая модель станковой задачи может быть сведена к задаче линейного программирования. Действительно, из определения целевой функции (4.12) следует, что
, 
, 
. (5.7)
При этом число
– целое. (5.8)
Поэтому, если включить в число неизвестных, то получим математическую модель в виде задачи максимизации функции 
при ограничениях (5.4), (5.5), (5.7), (5.8). Эта модель относится к линейному частично целочисленному программированию. Решение задачи выполним в Excel. В ячейки серого цвета, как показано в таблице 5.3, поместим неизменяемую информацию. В блок ячеек B3: D5 поместим исходные данные задачи, а именно, число обработанных деталей каждым станком в течение рабочего дня и комплектность деталей. Блок ячеек B8: D9 и ячейку F12 предусмотрим для значений оптимального плана работы станков 
и значения 
. Эти ячейки оставляем пустыми. В ячейки E8: E9 поместим формулы для записи левых частей системы (5.4), а именно,
= СУММ(B8: D8)
и
= СУММ(B9: D9).
В ячейки G8: G9 поместим 1 – правые части системы (5.4). В блок ячеек B12: D12 поместим выражения для левых частей неравенств (5.7). Для этого в ячейку B12 запишем формулу
= СУММПРОИЗВ(B3: B4; B8: B9) / B5
и протянем ее на ячейки C12, D12. Наконец, в ячейку G12 поместим «короткую» формулу для целевой функции
= F12.
Таблица 5.3 – Составление таблицы в Excel
| A | B | C | D | E | F | G | |||
| Количество обработанных деталей вида | |||||||||
| Станки | |||||||||
| Комплект-ность | |||||||||
| Время обработки деталей | Левая часть | Знак | Правая часть | ||||||
| 0,666667 | 0,333333 | <= | |||||||
| 0,8 | 0,2 | <= | |||||||
| Число комплектов | Знак | Z | ЦФ max | ||||||
| >= | |||||||||
После заполнения таблица 5.3 следует обратиться к процедуре «Поиск решения» и заполнить появившееся окно информацией, указанной на рисунке 5.2.
Рисунок 5.2 - Обращение к процедуре «Поиск решения» в задаче о комплектном выпуске продукции
Результатом решения задачи в Excel служит оптимальный план обработки деталей, полученный в таблице 5.3.
| Xmax = | Станки | Детали | |
|
| 0,67 | 0,33 | 
|
|
|
| 0,8 | 0,2 |
Для этого плана число полных комплектов деталей равно 
. На рисунке 5.3 помещена диаграмма, которая для каждого станка показывает часть рабочего дня, в течение которой согласно оптимальному плану он должен быть занят обработкой деталей.
Рисунок 5.3 - Линейчатая диаграмма с накоплением На диаграмме каждому станку соответствует прямоугольник длины 1 (рабочий день) с разбивкой на доли времени, отведенного на обработку деталей трех видов.
5.4 Техническое обеспечение
5.4.1 Компьютеры и выход в сеть интернета.
5.5 Содержание отчета
5.5. Отчет должен содержать следующие пункты:
· задание на работу с конкретными исходными данными студента приведены в приложении 5,
· математическую модель задачи в виде максиминной задачи,
· произвольный план работы станков, число полных комплектов деталей для этого плана,
· преобразование математической модели к задаче линейного программирования с частично целочисленными переменными,
· оптимальный план работы станков, максимальное число полных комплектов,
· диаграмму, отражающую оптимальный план работы станков,
выводы по работе.