Решение задачи линейного программирования
.pdfВ этой же таблице указаны запасы ресурсов, которые могут быть использованы в течение рабочего дня, величины прибыли (в условных единицах) от выпуска одного изделия каждого вида, а также заданы пределы объемов изготовления каждого вида продукции.
Требуется определить объемы производства продукции мебельной фабрики в течение рабочего дня, гарантирующие ей максимальную прибыль.
Пусть x1 – количество изготовленных столов, x2 – количество изготовленных шкафов, x3 – количество изготовленных диван-кроватей, x4 – количество изготовленных
кресел-кроватей и x5 – количество изготовленных тахт. Требуется определить объемы производства продукции мебельной фабрикой в течение рабочего дня, гарантирующие ей максимальную прибыль E .
E = 8x1 +10x2 +16x3 +13x6 +17x5 → max . |
(8.3.1) |
При этом должны быть выполнены следующие ограничения: по трудозатратам (в чел.-часах):
4x1 +8x2 +12x3 +9x4 +10x5 ≤ 3690 , |
(8.3.2) |
по затрачиваемой древесине (в м3):
0.4x1 +0.6x2 +0.3x3 +0.2x4 +0.3x5 ≤ 432 , |
(8.3.3) |
по затрачиваемой ткани (в м):
8x1 +10x2 +16x3 +13x4 +17x5 ≤ 2400 , |
(8.3.4) |
по предельному объему выпуска (в шт.):
x1 ≤ 480 , x2 |
≤80 , x3 ≤180 , |
x4 |
≤120 , |
x5 ≤100 , |
(8.3.5) |
а также ограничения на неотрицательность и целочисленность: |
|
||||
x1 ≥ 0 , |
x2 ≥ 0 , x3 ≥ 0 , |
x4 |
≥ 0 , x5 |
≥ 0 , |
(8.3.6) |
|
32 |
|
|
|
tbicr |
x1 , x2 , x3 , x4 x5 , - целые числа. |
(8.3.7) |
Решим задачу с помощью MS Excel. Максимальная прибыль E = 6650 достигается при производстве 479 столов, 86 кресел-кроватей и 100 тахт, при этом шкафы и диванкровати не производятся.
33 |
tbicr |
Заключение
При решении оптимизационной задачи было найдено три решения, с одинаковыми значениями целевой функции (Таблица 6.1, Приложение А). Решение №1 является лучшим (Приложение А – Таблица А.1), поскольку в нем обеспечивается наибольшая средняя занятость квалифицированных и неквалифицированных рабочих и выполняется максимальный выпуск автомобилей.
При этом решении выпускается 366 автомобилей «Шторм» и 684 автомобиля «Торнадо». Используется 99.938% квалифицированного и 95.85% неквалифицированного труда. Также используются 99% средств на выпуск автомобилей. Производится максимальное (1050 ) количество автомобилей, то есть предприятие реализует все производственные мощности.
На предприятии не используется 1660 часов неквалифицированного труда, что соответствует незанятости примерно 40 ( 41.5 ) неквалифицированных рабочих. При заданных ограничениях их можно уволить. Альтернативным вариантом служит повышение количества выпускаемых автомобилей (Модифицированная задача №1, Приложение Б – Таблица Б.1), где при увеличении выпуска на 35 автомобилей ( 3.333%), не только будет выполняться большая производственная мощность и осуществляться полная занятость рабочих, но и повысится прибыль, получаемая предприятием.
Если занятость рабочих на предприятии должна составлять приблизительно 90% (Модифицированная задача №2, Приложение Б – Таблица Б.2), то для сохранения производственных мощностей и соответственно прибыли, необходимо будет нанять дополнительно 90 квалифицированных и 70 неквалифицированных рабочих, что не значительно скажется на изменившейся прибыли, но повысит количество рабочих мест, то есть возрастет занятость населения.
34 |
tbicr |
Список используемых источников
Смородинский С.С. Оптимизация решений на основе методов и моделей математического программирования: Учебное пособие по курсу «Системный анализ и исследование операций» для студентов специальностей «Автоматизированные системы обработки информации» дневной и дистанционной форм обучения/ Смородинский С.С.,
Батин Н.В. – Мн.: БГУИР, 2003. – 136 с.: ил. ISBN 985-444-521-6.
Смородинский С.С. Системный анализ и исследование операций. Сборник заданий и методические указания по курсовому проектированию/ Смородинский С.С., Батин Н.В.
– Мн.: БГУИР, 2006. ISBN 985-488-051-4
Таха Х.А. Введение в исследование операций. 6-е издание.: пер с англ. – М.: Издательский дом «Вильямс», 2001. – 912 с.: ил. – Парал. тит. англ. ISBN 5-8459-0180-4 (рус.)
Эддоус М. Методы принятия решений/ Эддоус М., Стэнсфилд Р.: пер. с англ. под ред. член-корр. РАН Елисеевой И.И. – М.: Аудит, ЮНИТИ, 1997. - 590 с. ISBN 0-85121- 832-6 (англ.) ISBN 5-85177-027-9 (русск.)
Орлов А.И. Основы теории принятия решений. Учебное пособие – Москва, 2002.
Электронная версия. Режим доступа http://www.aup.ru/books/m156.
Севернев А.М. «Дипломное проектирование: Методическое пособие для студентов специальности I-53 01 02 «Автоматизированные системы обработки информации» всех форм обучения»/ Севернев А.М., Герман О.В. – Мн.: БГУИР, 2006. – 80 c.: ил. ISBN 985- 444-929-7
Использование пакетов прикладных программ для решения оптимизационных задач. Режим доступа: http://csi.ucoz.ru/Pakety.htm. – Заголовок с экрана.
35 |
tbicr |
Приложение А
Рабочие листы MS Excel с результатами решения задачи оптимизации на основе базовой аналитической модели
|
Шторм |
Торнадо |
|
|
|
|
|
|
количество автомобилей |
366 |
|
684 |
|
|
|
|
|
|
|
|
|
|
затрачено |
максимусм |
остаток |
% использования |
квалифицированный труд |
50 |
|
20 |
≤ |
31980 |
32000 |
20 |
99,938% |
неквалифицированный труд |
30 |
|
40 |
≤ |
38340 |
40000 |
1660 |
95,850% |
затраты на выпуск |
1500 |
|
500 |
≤ |
891000 |
900000 |
9000 |
99,000% |
вывоз с завода |
1 |
|
1 |
≤ |
1050 |
1050 |
0 |
100,000% |
|
|
|
|
|
|
|
|
|
прибыль |
1000 |
|
500 |
→ |
708000 |
max |
|
|
|
|
Рисунок А.1 – Решение №1 |
|
|
||||
|
|
|
|
|
|
|
||
|
Шторм |
Торнадо |
|
|
|
|
|
|
количество автомобилей |
367 |
|
682 |
|
|
|
|
|
|
|
|
|
|
затрачено |
максимусм |
остаток |
% использования |
квалифицированный труд |
50 |
|
20 |
≤ |
31990 |
32000 |
10 |
99,969% |
неквалифицированный труд |
30 |
|
40 |
≤ |
38290 |
40000 |
1710 |
95,725% |
затраты на выпуск |
1500 |
|
500 |
≤ |
891500 |
900000 |
8500 |
99,056% |
вывоз с завода |
1 |
|
1 |
≤ |
1049 |
1050 |
1 |
99,905% |
|
|
|
|
|
|
|
|
|
прибыль |
1000 |
|
500 |
→ |
708000 |
max |
|
|
|
|
Рисунок А.1 – Решение №2 |
|
|
||||
|
|
|
|
|
|
|
||
|
Шторм |
Торнадо |
|
|
|
|
|
|
количество автомобилей |
368 |
|
680 |
|
|
|
|
|
|
|
|
|
|
затрачено |
максимусм |
остаток |
% использования |
квалифицированный труд |
50 |
|
20 |
≤ |
32000 |
32000 |
0 |
100,000% |
неквалифицированный труд |
30 |
|
40 |
≤ |
38240 |
40000 |
1760 |
95,600% |
затраты на выпуск |
1500 |
|
500 |
≤ |
892000 |
900000 |
8000 |
99,111% |
вывоз с завода |
1 |
|
1 |
≤ |
1048 |
1050 |
2 |
99,810% |
|
|
|
|
|
|
|
|
|
прибыль |
1000 |
|
500 |
→ |
708000 |
max |
|
|
Рисунок А.1 – Решение №3
36 |
tbicr |
Приложение Б
Рабочие листы MS Excel с результатами решения задач оптимизации на основе модифицированных аналитических моделей
|
Шторм |
Торнадо |
|
|
|
|
|
количество автомобилей |
343 |
742 |
|
|
|
|
|
|
|
|
|
затрачено |
максимусм |
остаток |
% использования |
квалифицированный труд |
50 |
20 |
≤ |
31990 |
32000 |
10 |
99,969% |
неквалифицированный труд |
30 |
40 |
≤ |
39970 |
40000 |
30 |
99,925% |
затраты на выпуск |
1500 |
500 |
≤ |
885500 |
900000 |
14500 |
98,389% |
вывоз с завода |
1 |
1 |
≤ |
1085 |
1085 |
0 |
100,000% |
|
|
|
|
|
|
|
|
прибыль |
1000 |
500 |
→ |
714000 |
max |
|
|
Рисунок Б.2 – Решение задачи по обеспечению полной занятости |
|||||||
|
|
|
|
|
|
|
|
|
Шторм |
Торнадо |
|
|
|
|
|
количество автомобилей |
375 |
675 |
|
|
|
|
|
|
|
|
|
затрачено |
максимусм |
остаток |
% использования |
квалифицированный труд |
50 |
20 |
≤ |
32250 |
35600 |
3350 |
90,590% |
неквалифицированный труд |
30 |
40 |
≤ |
38250 |
42800 |
4550 |
89,369% |
затраты на выпуск |
1500 |
500 |
≤ |
900000 |
900000 |
0 |
100,000% |
вывоз с завода |
1 |
1 |
≤ |
1050 |
1050 |
0 |
100,000% |
|
|
|
|
|
|
|
|
прибыль |
1000 |
500 |
→ |
712500 |
max |
|
|
Рисунок Б.1 – Решение задачи по обеспечению частичной занятости
37 |
tbicr |
Приложение В
Рабочие листы MS Excel с результатами решения примера №1 задач оптимизации (задача о выборе оборудования)
|
Станок 1 |
Станок 2 |
|
|
|
Количество |
2 |
5 |
|
|
|
|
|
|
|
расход |
ограничение |
Средства |
5000 |
2000 |
≤ |
20000 |
20000 |
Площадь |
8 |
4 |
≤ |
36 |
38 |
Производство |
|
|
→ |
|
max |
7 |
3 |
29 |
Рисунок В – Решение задачи №1
38 |
tbicr |
Приложение Г
Рабочие листы MS Excel с результатами решения примера №2 задач оптимизации (задача о производстве изделий)
|
Изделие 1 |
Изделие 2 |
Изделие 3 |
|
|
|
Количесто изделий |
12 |
16 |
0 |
|
|
|
|
|
|
|
|
затрачено |
оганичение |
Необходмое время |
3 |
4 |
5 |
≤ |
100 |
100 |
Необходимое сырье |
4 |
3 |
6 |
≤ |
96 |
100 |
|
0 |
0 |
1 |
= |
0 |
0 |
Прибыль |
|
|
|
→ |
|
max |
25 |
30 |
45 |
780 |
|||
Рисунок В.1 – решение задачи №2 при условии x3 = 0 |
|
|||||
|
Изделие 1 |
Изделие 2 |
Изделие 3 |
|
|
|
Количесто изделий |
0 |
11 |
11 |
|
|
|
Необходмое время |
|
|
|
≤ |
затрачено |
ограничение |
3 |
4 |
5 |
99 |
100 |
||
Необходимое сырье |
4 |
3 |
6 |
≤ |
99 |
100 |
|
0 |
0 |
1 |
≥ |
11 |
5 |
Прибыль |
|
|
|
→ |
|
max |
25 |
30 |
45 |
825 |
Рисунок В.2 – решение задачи №2 при условии x3 ≥ 5
39 |
tbicr |
Приложение Д
Рабочие листы MS Excel с результатами решения примера №3 задач оптимизации (задача об объемах производства мебельной фабрики)
|
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
|
Количество |
479 |
0 |
0 |
86 |
100 |
|
|
|
Предельный объем |
480 |
80 |
180 |
120 |
100 |
|
|
|
Трудозатраты |
|
|
|
|
|
≤ |
|
3690 |
4 |
8 |
12 |
9 |
10 |
3690 |
|||
Древесина |
0,4 |
0,6 |
0,3 |
0,2 |
0,3 |
≤ |
238,8 |
432 |
Ткань |
0 |
0 |
6 |
4 |
5 |
≤ |
844 |
2400 |
Прибыль |
|
|
|
|
|
→ |
|
max |
8 |
10 |
16 |
13 |
17 |
6650 |
Рисунок Д – Решение задачи №3
40 |
tbicr |