Решение задачи использованием Симплекс-таблиц

ИРКУТСКИЙ Государственный ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНИЧЕСКИЙ Институт

Заочно-вечерний

наименование факультета

Кафедра вычислительной техники

наименование кафедры

Контрольная работа по дисциплине _______Исследование операций_______

наименование учебной дисциплины

Разработал студент ЭВМбз-12-1 ____________ О.В. Самсонюк

шифр группы подпись И.О. Фамилия

Управляющий ___________ О.С. Бучнев

подпись И.О. Фамилия

Иркутск 2016 г.


Постановка задачки

Задачка 11

Мебельная фабрика выпускает два вида изделий: шкафы и тумбочки, расходуя для их производства ресурсы 4 типов Решение задачи использованием Симплекс-таблиц: ДСП, фанеру, стекло, крепежные изделия. Нормы расхода ресурсов на одно изделие каждого типа и дневные припасы, которыми располагает фабрика, приведены в табл.1.

Виды ресурсов Объем ресурсов Нормы расхода на одно изделие
Шкафы Тумбочки
ДСП
Фанера
Стекло
Крепежные изделия

Найти лучшую программку выпуска из условия максимума прибыли, если прибыль от реализации Решение задачи использованием Симплекс-таблиц 1-го шкафа 2 у.е., а тумбочки 3 у.е.

Построение математической модели

2x1+ 3x2 →max

ОДЗ:

1) x1 + 2x2≤18
2) 2x1 + x2≤21
3) x1 + x2≤22

4) x1 + x2≤23 – не используем потому что, 3)ОДЗ лежит снутри области 4)


Решение задачки графическим способом

Построим графики согласно ОДЗ

X1,X2≥0

Сейчас выделим область, удовлетворяющую всем ограничениям (ABCD):

и построим нашу Решение задачи использованием Симплекс-таблиц функцию, приравняв её к 0:
2x1+ 3x2 =0

Будем двигать эту прямую параллельным образом до последнего касания обозначенной области.

Потому что точка C получена в итоге скрещения прямых(1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
x1+2x2=18
2x1+x2=21
Решив систему уравнений, получим: x1 = 8, x2 = 5

Сейчас найдем максимум:
2*8+3*5=31


Решение задачки симплекс способом

Вводим базовые Решение задачи использованием Симплекс-таблиц переменные:

2x1+ 3x2+0s1+0s2+0s3=А0

ОДЗ:

1) x1 + 2x2+s1≤18
2) 2x1 + x2+s2≤21
3) x1 + x2+s3≤22

А0=0+2x1+ 3x2

S1=18-x1-2x2

S2 = 21-2x1-x2
S3 = 22-x1-x2

В выражении А0 находятся положительные коэффициенты

Выберем новейшую базовую переменную Х2 (max коэффициент)

Определим новейшую свободную переменную

Min (18/2, 21/1, 22/1)=9 (S1)

X2= 9*-0,5x Решение задачи использованием Симплекс-таблиц1*-0,5S1

Новенькая система уравнений:

А0=0+2x1+ 3(9*-0,5x1*-0,5S1)

S2 = 21-2x1-(9*-0,5x1*-0,5S1)
S3 = 22-x1-(9*-0,5x1*-0,5S1)

А0=27+0,5x1-1,5S1

X2= 9-0,5x1-0,5S1

S2 = 12-1,5x1+0,5S1
S3 = 13-0,5x1+0,5S1

В выражении А0 находятся положительные коэффициенты

Выберем новейшую базовую переменную Х1 (max коэффициент)

Определим новейшую свободную переменную

Min (9/0,5, 12/1,5, 13/0,5)=8 (S2)

Х1=8+1/3S1-2/3S2

Новенькая Решение задачи использованием Симплекс-таблиц система уравнений:

А0=27+0,5(8+1/3S1-2/3S2)-1,5S1

X2= 9-0,5(8+1/3S1-2/3S2)-0,5S1

Х1=8+1/3S1-2/3S2

S3 = 13-0,5(8+1/3S1-2/3S2)+0,5S1

А0=31-4/3S1-1/3S2

X2= 5-2/3S1+1/3S2

Х1=8+1/3S1-2/3S2

S3 = 9+1/3S1+1/3S2

В выражении А0 отсутствуют положительные коэффициенты

Небазисные элементы S приравняем к 0:

А0=31

X2= 5

Х1=8

Max=31


Решение задачки внедрением Симплекс-таблиц

Вводим Решение задачи использованием Симплекс-таблиц базовые переменные:

2x1+ 3x2+0s1+0s2+0s3→max

ОДЗ:

1) x1 + 2x2+s1≤18
2) 2x1 + x2+s2≤21
3) x1 + x2+s3≤22

Построим таблицу:

Ci
Bx A0 X1 X2 S1 S2 S3
S1
S2
S3
-2 -3

в индексной строке находятся отрицательные коэффициенты.

Итерация №1

В качестве ведущего выберем столбец, соответственный переменной x2, потому что это меньшее чисто Решение задачи использованием Симплекс-таблиц в индексной строке.

Выбор ведущей строчки:

Min (18/2, 21/1, 22/1)=9 (1-ая строчка)

Построим таблицу2:

Строчка X2= ведущая строчка /разрешающий элемент(2)

НЭ = СЭ - (А*В)/РЭ

НЭ-новый элемент

СЭ-старый элемент

РЭ-разрещающий элемент

A-элемент ведущей строчки в этом столбце

B-элемент ведущего столбца в этой строке

Ci
Bx A0 X1 X2 S1 S2 S3
X2 1/2 1/2
S2 3/2 1/2
S Решение задачи использованием Симплекс-таблиц3 1/2 1/2
-1/2 3/2

в индексной строке находятся отрицательныq коэффициент.

Итерация №2

Ведущий столбец – Х1

Ведущая строчка – min(18,8,26,)=8 S2

Построим таблицу3:

Ci
Bx A0 X1 X2 S1 S2 S3
X2 2/3 -1/3
X1 1/3 3/2
S3 -1/3 -1/3
4/3 1/3

В индексной строке все коэффициенты положительные

X1=8

X2=5

Max=31


reshenie-zadachi-v-ms-excel.html
reshenie-zadanij-po-teme-stepeni-korni-chast-1.html
reshenie-zasedaniya-kafedri.html