Оптимізація економічних задач

Складання математичної моделі задачі. Побудова симплексної таблиці. Розв’язок задачі лінійного програмування симплексним методом. Рішення двоїстої задачі та складання матриці. Знаходження графічним методом екстремумів функцій, визначеній нерівностями.
Краткое сожержание материала:

Размещено на

Завдання 1

Цех випускає вали і втулки. На виробництво одного вала робочий витрачає 3 год., однієї втулки - 2 год. Від реалізації одного вала підприємство одержує прибуток 80 грн., а від реалізації однієї втулки - 60 грн. Цех має випустити не менше 100 валів і не менше 200 втулок. Скільки валів і скільки втулок має випустити цех, щоб одержати найбільший прибуток, якщо фонд робочого часу робітників становить 900 людино-годин?

Ресурс	Вироби	Фонд робочого часу
	Вали	Втулки
Робітник, год. од.	3	2	900
Вартість, грн. од.	80	60

Розв'язок

Складаємо математичну модель задачі. Позначимо через х1 кількість валів, що виготовляє підприємство за деяким планом, а через х2 кількість втулок. Тоді прибуток, отриманий підприємством від реалізації цих виробів, складає

? = 80х1+60х2.

Витрати ресурсів на виготовлення такої кількості виробів складають відповідно:

CI =3х1+2х2,

Оскільки запаси ресурсів обмежені, то повинні виконуватись нерівності:

3х1+2х2?900

Окрім того, валів потрібно виготовити не менше 100 штук, а втулок - 200 шт., тобто повинні виконуватись ще нерівності: х1? 100, х2? 200.

Таким чином, приходимо до математичної моделі:

Знайти х1, х2 такі, що функція ? = 80х1+60х2 досягає максимуму при системі обмежень:

Розв'язуємо задачу лінійного програмування симплексним методом.

Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних. Оскільки маємо змішані умови-обмеження, то введемо штучні змінні x.

3x1 + 2x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 = 900

1x1 + 0x2 + 0x3-1x4 + 0x5 + 1x6 + 0x7 = 100

0x1 + 1x2 + 0x3 + 0x4-1x5 + 0x6 + 1x7 = 200

Для постановки задачі на максимум цільову функцію запишемо так:

F(X) = 80 x1 +60 x2 - M x6 - M x7 => max

Отриманий базис називається штучним, а метод рішення називається методом штучного базису.

Причому штучні змінні не мають стосунку до змісту поставленого завдання, проте вони дозволяють побудувати початкову точку, а процес оптимізації змушує ці змінні приймати нульові значення і забезпечити допустимість оптимального рішення.

З метою формулювання задачі для вирішення її в табличній формі скористаємося виразами з системи рівнянь для штучних змінних:

x6 = 100-x1 +x4

x7 = 200-x2 +x5

які підставимо в цільову функцію:

F(X) = 80x1 + 60x2 - M(100-x1 +x4 ) - M(200-x2 +x5 ) => max

або

F(X) = (80+1M)x1 +(60+1M)x2 +(-1M)x4 +(-1M)x5 +(-300M) => max

Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:

3	2	1	0	0	0	0
1	0	0	-1	0	1	0
0	1	0	0	-1	0	1

Базисні змінні це змінні, які входять лише в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.

Вирішимо систему рівнянь відносно базисних змінних:

x3 , x6 , x7

Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:

X1 = (0,0,900,0,0,100,200)

Оскільки завдання вирішується на максимум, то ведучий стовпець вибираємо по максимальному негативному кількістю та індексного рядку. Всі перетворення проводимо до тих пір, поки не вийдуть в індексному рядку позитивні елементи.

Складаємо симплекс-таблицю:

План	Базис	В	x1	x2	x3	x4	x5	x6	x7	min
1	x3	900	3	2	1	0	0	0	0	300
	x6	100	1	0	0	-1	0	1	0	100
	x7	200	0	1	0	0	-1	0	1	0
Індексний рядок	F(X1)	-30000000	-100080	0	-100060	0	100000	0	0	0

Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.

План	Базис	В	x1	x2	x3	x4	x5	x6	x7	min
2	x3	600	0	2	2	0	3	-3	0	300
	x1	100	1	0	0	0	-1	1	0	0
	x7	200	0	1	1	0	0	0	1	200
Індексний рядок	F(X2)	-19992000	0	0	-100060	0	-80	100080	0	0

Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.

План

Базис ... Другие файлы: Оптимізація соціально-економічних трансформацій національної економіки до сучасних глобалізацій Оптимізація грузоперевезень за допомогою транспортної задачі Загальна характеристика методів оптимізації для рішення економічних задач. Аналіз виконання плану перевезень в Донецькому АТП. Використання мереженого... Інформатика для економістів Підручник написаний згідно з останніми освітньо-кваліфікаційними вимогами та програмами підготовки бакалаврів економічних спеціальностей. Він є початк... Розв'язання економічних задач в Excel Розв'язання економічних задач з інформаційного менеджменту за допомогою програми Excel. Створення таблиці "Фірма" з інформацією про працівників фірми.... Класифікація, розрахунок та оптимізація вертикально-гвинтового транспортера Різновиди виконання технічної системи гвинтового транспортера. Оптимізація параметру швидкості переміщення вантажу за критерієм параметру зовнішнього...