Методы оптимизации в экономике, страница 3

Площадь каждого из участков соответственно равна 600, 180„220 га. С учетом наличия семян этими куль- 5. Три предприятия данного экономического района могут производить некоторую продукцию в количествах соответственно 180, 350 и 20 единиц. Эта продукция должна быть поставлена пяти потребителям в количествах, соответственно равных 110, 90, 120, 80 и 150. Затраты, связанные с производством и доставкой единицы продукции„задаются матрицей турами Следует засеять Соответственно 290„ 180, 10 и 420 га. Урожай- НОСТЬ КажДОЙ Ич КОЛЬТЪО ЕЛЯ КажДОГО ИЗ уЧаСТКОВ РаЗЛИЧНа И ЗаДаЕТСЯ матриц ей 40 45 50 ,30 28 22 '18 22 14 25 18 15 4 3 21 5 3 2 б 7 б~ 2 3 4 1 5 3 б 4 2 7 8 5 найти такое распределение выпуска колбасных изделий между завода- ми, при котором себестоимость изготовляемой гродукции будет мини- мальной.

1. 19знецоа Ю.И., К»зюоое В.И., Волои1енка Л.В, Математическое программирование. -М.: Высшан и:хола, 19во. 2. А лич И.Л. Математическое программирование в примерах и задачах. -М.: Вых» сйаи школа, 1986. . Голанинейн Е.Г., Юдин Ю.В. Задачи линейного программировании транспортного типа. -М.: Наука, 1969. Определить, сколько гектаров каждой культуры на каждом из участков следует засеять так, чтобы общий сбор зерна был максимальным. 8. Мясокомбинат имеет в своем составе четыре завода, на каждом из которых может изготовляться три вида колбасных изделий.

Мощности каждого из заводов соответственно равны 320, 280, 270 и 350 тонн в сутки. ЕжеДневные потребности в колбасных Изделиях кажДОго виДа также известны и соответственно равны 450, 370 и 400 тонн. Зная себеСтоимОсть 1 т кажДОго вида колбасных изделий на каждом заводе, которые Определя1отся матрицей Рассмотрим задачу лннеиного программирования, состоящую Б оп- тимизации целевой функции л ~=ХС х -~шах ,=1 при условиях, что неизвестные х > О, у = 1,п . удовлетворяют линейной системе уравнений Ха; х =Ь;,1=1,т.

(3.3) у=1 Потребуем дополнительно, чтобы неизвестные х, у = 1 п принимали только целочисленные значения, т.е. х = 0,1,2,...,у = 1,п Задача в такой постановке называется задачей целочисленного программирования. Допустим теперь, что, не принимая во внимание условие (3.4) цело- численности неизвестных, мы решили задачу линейного программирования (3.1) — (3.3) и получили ее оптимальное решение х *.

Может случиться, что все компоненты решения х окажутся целыми числами. Тогда, очевидно, что решение х будет оптимальным и для задачи линейного целочисленного программирования (3.1) — (3.3). Если же среди компонент решения встретятся дробные числа, то естественно предположить, что, заменив дробные компоненты ближайшими целыми числами, взятыми с недостатком или с избытком, мы получим оптимальное или близкое к оптимальному решение целочисленной задачи. В действительности такое округление может привести к решению со значением целевой функции, достаточно сильно отличающимся от оптимального, или вообще вывести за пределы области допустимых решений. Достаточно общим методом решения задач целочисленного программирования является метод Гомори (Ц.

3.2. Метод Гоморн Нахождение решения задачи ц лочис пенного программирования начинают с определения симплексным методом оптимального решения задачи (3.1) — (3.2) без учета целочисленности перемен1жх После того как это решение найден~, просматривают его компоненты. Если среди компонент нет дробных чисел, то найденное решение является оптимальным для задачи целочисленного программирования.

Если же в оптимальном решении задачи (3.1) — (3.3) переменная х принимает У дробное значение, то к системе уравнений (3.3) добавляют неравенство Ху(а;~)х. ~ я(Ь~ ) ! и находят решение задачи (3.1) — (3.3), (3.5). В неравенстве (3.5) а,*" и Ь,' — преобразованные исходные величины а ~~ и Ь;, значения которых взяты из последней симплекс- таблицы, полученной в ходе решения задачи линейного программирования без учета целочисленности, а я(а,';) и 8(Ь,') — дробные части чисел. Под дробной частью числа а понимается наименьшее неотрицательное число я (а ) такое, что разность между а и я (а ) есть целое, Если в оптимальном решении задачи (3,1) — (3.3) дробные значения принимают несколько переменных, то дополнительное неравенство (3.5) определяется наибольшей дробной частью.

Если в найденном решении задачи (З.Ц вЂ” (З.З), (3.5) переменные принимают дробные значении, то снова добавляют одно дополнительное ограничение и процесс вычислений повторяют. Проводя конечное число итераций, либо получают оптимальное решение задачи целочисленного программирования (3.1) — (3.3), либо устанавливают ее неразрешимость. Если требование целочисленности (3.4) относится лишь к некоторым переменным, то решение также находят последовательным решением задач, каждая из которых получается из предыдущей с помощью введения дополнительного ограничения.

В этом случае такое ограничение имеет вид Х у; х. ~д(Ь;), где у; определяется из следующих соотношений: 20 а»'. при а, ~ О; д»Ь ~ 1а* ) приа, сО; 1- я(Ь~) ния> я(а» ) при я(а» ) ~ й~Ь» ); к(Ь»') 1 1 — к(а»»)) пРи к(а»») > Ю(Ь»') 1 — я(Ь,') Алгоритм решения задачи методом Гомори . 1, Находят симплекс-методом решение задачи (3.1) — (3.3) без учета требования целочисленности. 2. Составляют дополнительное ограничение для переменной, которая в оптимальном решении задачи (3.1) — (3.3) имеет максимальную дробную часть, а в оптимальном решении задачи (3.1) — (3.4) должна бить целочисленной.

3. Находят решение (3,1) — (3.3), (3.5). Если оптимальное решение еще не удовлетворяет требованию целочисленностн, составляют дополнительное ограничение и продолжают итерационный процесс до получения оптимального решения (3.1) — (3.4» или установления ее неразрешимости. П р и м е р. Методом Гомори найти решение задачи, состоящей в определении максимального значения функции У х1+ х2 при условиях 1 2х1+ 2х2 ~ 6 —; х» + Зх2 ~ 4; 3 ' х», Х2 а О, х», х2 — целые Решение. Перейдем к ограничениям-равенствам и запишем исходную задачу в виде»' = -х» — 4х 2 --> шш при условиях 2х1 + 2х2 + х з = 1Й, х 1 + Зх.2 + х 4 = 4; х. ~ О;,» -');4; 3.3.

Ьзоделн задач целочисленного программирования 1. Имеется и различных самолетов, которые требуется распределить между и авиалиниями. Известно, что на 1-й авиалинии 1' — й самолет будет приносить доход С . Требуется так распределить самолеты, чтобы максимизировать суммарный доход. Положим 1, если 1 — й самолет направлен на у — ю авиалинию; Х 0 в противном случае . л а л шахХ ХС; х~~, Хх~ 1, у =1,п; 1-~ у-~ ' 1-~ Хх~~=1, 1 1,п;х; «=~0,1~,1-1,и,~=1,п 1'-! Ограничения этой задачи отражают требования, что каждый самолет назначается только на одну авиалинию. 2. Пусть имеется достаточно большое количество труб заданной длины 1 3 из .

Трубы следует распилить на заготовки двух видов: длинои 1~ ~ 1,2м и 1~ = 0,9 и, причем заготовок каждого вида должно быть получено не менее ш и п штук соответственно. Каждая труба может быть распилена на указанные заготовки несколькими способа'ми. Требуется найти число труб, распиливаемых каждым способом, с $ тем, чтобы необходимое количество заготовок каждого вида было получено из наименьшего количества труб. Очевидно, что распилить можно только тремя способамн. Пусть х ~, х з, х з — число труб, распиливаемых первым, вторым и третьим способами. Очевидно, х ~ „х з,х з — целые неотрицательные числа. Количество заготовок длиной 1 ~ и 1з, полученных при использовании всех трех способов раскроя, составит соответственно 2х ~ + хз шт., 2хз + Зхз шт., а общее количество распиленных труб составит х 1 + х 2 + х з п|т.

Таким образом, задача заключается в минимизации целевой Функции ~ = х, + х2 + х з при услови~х, что неизвестные х > О, у' = 1, 3 удовлетворяют системе неравенств: 2х1+ х2 > 50; 2х2 + Зхз > 81 и, кроме того, целочисленны, т.е. х = 0,1,2,...,/ = 1,3 3.4. Варианты заданий 1. В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено Я и площади. На приобретение оборудования предприятие может израсходовать А руб. При этом оно может купить оборудование двух видов.

Комплект оборудования первого вида стоит А1 руб., а второго А2 руб. Приобретение одного комплекта оборудования первого вида позволяет увеличить выпуск продукции в смену на Ь 1 ед., а одного комплекта оборудования второго вида — на Ь 2 ед . Зная, что для установки одного комплекта оборудования первого вида требуется 51 м площади, а оборудования второго вида— 2 52 м площади, определить такой набор дополнительного оборудова- 2 ния, который дает возможность максимально увеличить выпуск продукции. Исходные данные: Ф= 1~,А=10000,А,= 1000,А2=3000,Ь,= 2,Ь,= 4,~,=2,~;-1; б)5 = 8, А = 20000, А 1 —— 2000, А 2 — — 4000 ~ Ь 1 — 1, Ь 2 — — 3 ~ 5 1= 3 ~ ~Б 2- 2 2. Для выполнения работ могут быть использованы п механизмов. Производительность 1-го механизма, 1 = 1, п, при выполнении у-й работы, у = 1,п, равна С; .