ПРИЛОЖЕНИЕ 1 Примеры задач линейного программирования:
Пример 1. Для изготовления трех видов изделий А, В и С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия для каждого из типов оборудования указаны в табл. 1. В ней же указан общий фонд рабочего времени каждого из типов используемого оборудования, а также прибыль от реализации одного изделия каждого вида.
Таблица 1
Тип
оборудования
|
Затраты времени
(станко-часы)
на обработку одного изделия
каждого вида
|
Общий фонд рабочего времени оборудования (часы)
|
|
А
|
В
|
С
|
Фрезерное
|
2
|
4
|
5
|
120
|
Токарное
|
1
|
8
|
6
|
280
|
Сварочное
|
7
|
4
|
5
|
240
|
Шлифовальное
|
4
|
6
|
7
|
360
|
Прибыль (руб.)
|
10
|
14
|
12
|
|
Требуется определить, сколько изделий и какого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной. Составить математическую модель задачи.
Решение. Предположим, что будет изготовлено x1 единиц изделий вида А, единиц – вида В и единиц – вида С. Тогда для производства такого количества изделий потребуется затратить станко-часов фрезерного оборудования. Так как общий фонд рабочего времени станков данного типа не может превышать 120, то должно выполняться неравенство
Аналогичные рассуждения относительно возможного использования токарного, сварочного и шлифовального оборудования приведут к следующим неравенствам:
При этом так как количество изготовляемых изделий не может быть отрицательным, то
(1)
Далее, если будет изготовлено x1 единиц изделий вида А, единиц изделий вида В и единиц изделий вида С, то прибыль от их реализации составит
Таким образом, приходим к следующей математической задаче: дана система
(2)
четырех линейных неравенств с тремя неизвестными и линейная функция относительно этих же переменных
. (3)
Требуется среди всех неотрицательных решений системы неравенств (2) найти такое, при котором функция (3) принимает максимальное значение. Как это сделать, будет показано в дальнейшем. Линейная функция (3), максимум которой требуется определить, вместе с системой неравенств (2) и условием неотрицательности переменных (1) образуют математическую модельисходной задачи.
Так как функция (3) линейная, а система (2) содержит только линейные неравенства, то задача (1) - (3) является задачей линейного программирования.
Задача о выпуске продукции
Фирма выпускает два вида древесно-стружечных плит - обычные и улучшенные. При этом производится две основные операции - прессование и отделка. Требуется указать, какое количество плит каждого типа можно изготовить в течение месяца так, чтобы обеспечить максимальную прибыль при следующих ограничениях на ресурсы (материал, время, затраты):
Затраты
|
Партия из 100 плит
|
Имеющиеся ресурсы на месяц
|
обычных
|
улучшенных
|
Материал (фунты)
Время на прессование (часы)
Время на отделку (часы)
Средства (деньги)
|
20
4
4
30
|
40
6
4
50
|
4000
900
600
6000
|
Прибыль
|
80
|
100
|
max
|
Перейдем к построению математической модели поставленной задачи. Введем следующие обозначения. Пусть
Х - количество партий в 100 плит обычного вида, изготавливаемых в течение месяца;
у - количество партий в 100 плит улучшенного качества, изготавливаемых в течение месяца.
Тогда ожидаемую прибыль можно записать так:
Требуется найти такие значения х и у, подчиненные условиям
для которых
Для того, чтобы найти в первой четверти плоскости хОу множество точек, координаты (х, у) которых удовлетворяют указанным выше неравенствам, необходимо сначала построить прямые (по точкам их пересечения с координатными осями)
а затем, используя точку начала отсчета О(0, 0), определить соответствующие полуплоскости. Пересечением полученных полуплоскостей будет четырехугольник ОВМЕ.
Наша целевая функция достигает наибольшего значения в одной из вершин четырехугольника.
Нам необходимо найти координаты точкиМ- точки пересечения прямых EFи АВ, для этого надо решить систему уравнений
Вычислить значения z в точках В(0, 100), Е(150, 0), М(100, 50):
Из полученных значений выберем наибольшее и получим ответ:
Транспортная задача
Важный тип задач линейного программирования представляет задача о перевозках. Называется она так потому, что цель этой задачи заключается в минимизации полной стоимости перевозок известного количества товаров со складов к потребителю.
Сбалансированная задача - задача о перевозках, в которой общий объем товаров, готовых к отправлению, в точности равен объему товаров, который готовы принять в пунктах назначения.
Пример 1. Рассмотрим транспортную задачу, заданную таблицей
|
В
|
Наличие
|
1
|
2
|
А
|
1
2
|
1
2
|
2
1
|
20
10
|
Запрос
|
16
|
14
|
30
|
Решение. Пусть - искомое число единиц товара, пересылаемого из пункта в пунк . Тогда данные таблицы можно представить в следующем виде:
при условии, что
Положим и выразим через t остальные переменные:
из первого уравнения: ,
из второго уравнения: ,
из третьего уравнения:
Тогда
Из того, что все не отрицательны, получаем, что переменная t должна удовлетворять одновременно следующим четырем неравенствам:
Тем самым, мы получили условие .
Не трудно заметить, что при t = 16.
Ответ:
|
В
|
Наличие
|
1
|
2
|
3
|
А
|
1
|
8
|
5
|
6
|
120
|
2
|
4
|
9
|
7
|
180
|
Запрос
|
70
|
140
|
90
|
300
|
Пример 2. Компания имеет два товарных склада и трех оптовых покупателей. Известно, что общий объем запасов на складах составляет 300 тыс. единиц продукции и совпадает с общим объемом заказов покупателей.
Обозначим через количество товара, поставляемого со склада покупателю .
Тогда соответствующая транспортная задача может быть сформулирована следующим образом.
Минимизировать общую стоимость перевозок:
при условии, что
Получаем задачу линейного программирования, в которой основные ограничения вследствие того, что транспортная задача сбалансирована, является равенствами.
Положим и выразим через u и v остальные переменные. Имеем
Учитывая, что все перевозки должны получить неотрицательные значения, мы приходим к задаче
которую можно решить графическим методом.
Выписанные неравенства определяют на плоскости (u, v) пятиугольник с вершинами (30, 0), (70, 0), (70, 50), (0, 120), (0, 30).
Ответ:
|