Исходные данные

Задача об использовании ресурсов (задача планирования про­изводства). Для изготовления двух видов про/{укции Р и Р, использ) — Ют четыре вида ресурсов 5,, S}, S’ и Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы иро,,|укции, при­ведены в табл. 6.2 (цифры условные).

Таблица 6 2 Вид ресурса Занас ресурса Число единиц ресурсов, затрачиваемых на изготовление единицы продукции Л 18 1 3 16 2 1 I 5 — 1 21 3 —

Прибыль, получаемая от единицы продукции /’ и Р — соответ­ственно 2 и 3 руб

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

РешениеI Составим экономико-математическую модель задачи. Обозначим, — ч исло единиц продукции соответ с гвенно Р, и Р, запланированных к производству. Для их изготовления (см табл. 6.2) потребуется (1 ■ t + 3 • л^) единиц ресурса S,, (2 ■ х1 + 1 • *2) единиц ресур­са S2, (1 • xj единиц рес урса (3 • х ) единиц ресурса Я Так как по­требление ресурсов S , J S, и S не должно превышать их запасы ( со­ответственно 18,16,5 и 21), то связь между потреблением ресурсов и их запасами выразится системой неравенств.

Х, + < 18, 2х, + х, < 16,

Х, < 5, (6.35)

Зх, <21

1 lo смыслу задачи

Xj > О, Х9>0- (б.%)

Суммарная прибыль F состав i# 2х руб. о г реализации продукции Г и Зхч руб. — от реализации проду кции Рг т. е.

Ш= 2х, Зх,. " (6.37)

Итак, экономико-математическая модель задачи, найти такой план выпуска продукции Х — (хг xv), удовлетворяющий системе (6.35) и условию (6.361), при котором функция (6 37) принимает максималь­ное значение

Задачу легко обобщить на случай выпуска пвидов продукции с ис­пользованием твидов ресурсов.

Обозначим х (7 = 1- 2, …, т) — число единиц продукции /■’, заплани­рованной к производству; /> (г= 1, 2, … , гщ — запас ресурса S; а. — число единиц ресу рса Л„ затрачиваемого па единицу продукции Р: с — Прибыль от реализации единицы продукции Р..

(6 38)

1огда экономико-математическая модель задачи об использо­вании ресурсов в общей постановке примет вид Naurtiu такой План Х= (х , л, …, Xj выпуска продукции, удовлетворяющий системе

Ciuxi + <7г>х„ +… + <, д.,,х + я22х2 — I-., +а2пхп <Ь2,

+ат9% + — + Ахп <Ь,

Ml 1 те. J. vm и ш

И условию

Х,>0, х2 >0, х„>0, (6 39)

При котором функция

F = б, х, + с2х2 +… + спхп —» max (6 40)

Притшаегк максимальное значение,.

Задача об использовании мощностей (задача о загрузке обору­дования) Предприятию задай план производства продукции по вре­мени и номенклатуре, требуется за время Т выпустить п, п, …, пк единиц продукции Pr Р, …, Рк. Продукция произнодится на станках , S„ ., Sm. Для каждого станка известны производительное! ь а. и зат­раты / на изго товление нродук ции Г на станке р. в единицу времени.

Необходимо составить такой чъхапработы станков (т е. так распреде­лить выпуск продукции между станками), чтобы затраты па производство всей продукции были минимальны ми.

Составим экономико-математическую модель задачи. Обозначим х — время, в течение которого станок 5 будет занят изготовлением продукции P. (i= 1, 2,…, M,J= 1, 2,…, K).

(6.41)

Так как время работы каждого станка ограничено и не превышает Т, то справедливы неравенства

J ~f~ Xj 2 "Н • ■	. + xlk<T,
	. + ,
■"•ml + XM2 +	.. + Xmk<r.

Для реализации плана выпуска по номенклатуре необходимо, что­бы выполнялись следу ющие равенства:

^11*11 + й[21*21 +—"’"ато1;х:т1 = П1» А12Х2 + а2$>Х22 + • + AM2XM‘A ~ П2′

……………………………………… (6.42)

Кроме того, х >0(г= 1,2,…, 1,2,…,&). (6.43)

Затраты на производство всей продукции выразятся функцией

F = bnxu + bV2x]2 + … + Ьпкх1пк. (6.44)

Экономико-математическая модель задачи об использовании мощ­ностей примет вид: найти такое решение Х= (xJJt X.V …, хтк), удовлет­воряющее системам (6.41) и (6.42) и условию (6.43), при котором фун­кция (6.44) принимает максимальное значение.

Транспортная задача. Важным частным случаем задачи линейно­го программирования является так называемая транспортная зада­ча, которая заключается в следующем.

Имеются три поставщика и четыре потребителя. Мощность по­ставщиков и спросы потребителей, а также затраты на перевозку еди­ницы груза для каждой пары «поставщик — потребитель» сведены в таблицу поставок (табл. 6.3).

В левом верхнем углу произвольной выделенной полужирными границами (г,^)-клетки (г — номер строки, j— номер столбца) стоит так называемый коэффициент затрат — затраты на перевозку едини­цы груза от г-го поставщика к J-му потребителю, например, в левом верхнем углу клетки (1,4) стоит число 3, следовательно, перевозка единицы груза от 1-го поставщика к 4-му потребителю обойдется в 3 условные денежные единицы и т. д.

Таблица 6,3 Поставщики Мощно* ть постаыцихов Потребители и их спрос 1 2 3 4 20 110 40 110 1 ЬО 1 2 5 3 9 120 1 Б 6 2 3 100 Б 3 7 Хо 4

Задача ставится следующим образом Наити объемы перевозок для каждой пары «поставщик — потребитель» так, чтобы-

1) Могшности всех поставщиков были реачизован ы;

2) Спросы всех потребителей были удовлетворены;

3) Суммарные затраты на перевозку были минимальны.

Решение. Построим экономико-математическую модель данной за­дачи. Искомый объем перевозки от мч> поставщика к/му Hoi ребите — лю обозначим через х и назовем поставкой клетки (I,J). Например, х, — искомый объем перевозки от 1-го поставщика ко 2 му потребите­лю или поставка клетки (1, 2) и т. д. Заданные мощности поставщи­ков и спросы потребителей накладывают ограничения на значения неизвестных х… Например, объем груза, забираемого ог 1-го постав — шика. должен быть равен мощности этого поставщика — 60 едини­цам, т. е. хи + хр + xXi k х,4 = 60 (уравнение баланса по первой строке). Таким образом, чтобы мощность каждого из поставщиков была реа­лизована, необходимо составить уравнения баланса для каждой стро ки таблицы поставок:

Л-j j "t" X] ij Ч* Х^ I" Xj^ —60,

* *21 + ^ + + *24 ~ ^20, ^ _ ^ j "Ь Хц2 ^34 ~ Ю0»

Исходные данные

Аналогично, чтобы спрос каждого из потребителей был удовлет­ворен, подобные уравнения балансасоставлясм для каждого столбца таблицы поставок:

I X^j Hh 20,

"Ь ~ 1.10,

*is + + хзз = 40, (6.46)

X,4 +x,4 =110.

Очевидно, что объем перевозимого груза не может быть отрица­тельным, поэ тому следует дополнительно предположить, что

Х.> О (г= 1, 2, 3;_/ = 1, 2, 3, 4). (6.47)

Суммарные затраты F на перевозку выражаются через коэффи циенты затрат и поставки следующим образом:

1" J нн "Ь Зх^ *f* X * нь (Зэс^ н™ +

+3х,, + 7хм+4хм. …. (64g)

Теперь можно дать математ ическую формулировку задачи (без обращения к ее содержательному экономическому смыслу). На мно­жестве неотрицательных решений системы ограничений (6.45) и (6.46) Найти такое решение Х= (лгп, …………………………… хчч, хм), при котором линейная функ­ция (6.48) принимает минимальное значение.

Особенности экономико-математической модели транспорт­ной задачи:

Система ограничений есть система уравнений (т. е. транспортная за­дача задана в канонической форме);

Коэффициенты при перемен ных системы ограничений равны единице или нулю;

Каждая переменная входит в систему ограничений два раза: один раз — в систему (6.45) и один раз — в систему (6.46).

Для математической формулировки транспортной задачи в общей постановке обозначим через с коэффициенты затрат, через Л/. — мощности поставщиков, через N. — мощности потребителей, где г= = 1, 2,…, т:1, 2,…,п; т — число поставщиков, п— число потребите­лей Тогда система ограничении примет вид

И

5>,7=Л/. г = 1,2,…, т, (6.49)

7=»

7=1,2, …, п. (6.50)

I=i

Система (6.49) включает уравнения баланса по строкам, а (истема (6.50) — по столбцам таблицы поставок. Линенная функция в данном случае

П т

Р-И X VV — (6.51)

7=1**1

Математическая формулировка транспортной задачи в общей постановке будет следующей: на множестве неотрицалге. гьных (допус­тимых) решении системы ограничений (G 49), (6.50) Nauniи такоерегие ние X = (.г J, х"12, …, х, …, *тп), ‘при котором значение линеи и о а функции (6.51) минимФхьно.

Произвольное допустимое решение Х= (х ,, …, х^ …, j п) систе мы ограничений (6.49), (6.50) назовем распределением поставок. Такое Решение задает заполнение таблицы поставок, поэтому в дальнейшем значение произвольной переменной х и содержимое соответствую щей клетки таблицы поставок будуг отождествляться.

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

Тп п

ZMi^t&j. „ (6.52)

I=l j=1

Такие транспортные задачи называю гея закрытыми (транспортная задача имеет закрытую модель). В противном случае транспортная за­дача называется открытой (открытая модель транспортной задачи).

СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ УПАКОВОЧНОГО ПРОИЗВОДСТВА

Использование специализированных САПР в допечатной стадии производства упаковки

Важным этапом произволе тва упаковки является доиечатный про­цесс. Качество готовой упаковки в значительной степени определя­ется допечатной стадией — дизайном. Можно утверждать, что конку­рентоспособность производителя полиграфической продукции оп­ределяется уровнем дизайна, который не в последнюю очередь зави­сит от программ ных с редств. Ксли вспомнить эволюцию систем допечатной подготовки, то можно отметить следующие закономерности Вначале применялись закрытые системы […]

Симплексный метод

Геометрическая интерпретация симплексного метода. В т еории линейного программирования рассмотрены основные теоремы ли­нейного программирования, из которых следует, что если задача ли­нейного программирования имеет оптимальное решение, то оно со­ответствует хотя бы одной угловой точке многогранника решений и совпадает по крайней мере с одним из допустимых базисных реше­ний системы ограничений. Там же указан путь решения любой зада­чи […]

Математическое обеспечение подсистем машинной графики и геометрического моделирования

Изучение математического аппарата, лежащего в основе машин­ной графики и проектирования геометрии упаковки, начнем с рассмот­рения способов вывода и преобразования точек и линий. Эти спосо­бы наряду с соответствующими алгоритмами рисования используют­ся для изображения объектов или визуализации графической инфор­мации. Возможность проводить преобразования точек и линий явля­ется фундаментом машинной графики. Нарисованный объект может быть представлен в нужном масштабе, […]