Факультет информационных технологий утверждаю

Задача №2. Решить задачу симплекс-методом. Для производства двух видов изделий - изделий А и изделий В - предприятие использует три вида сырья. Нормы расхода сырья каждого вида на изготовление единицы продукции приведены в таблице. В ней же указана прибыль от реализации одного изделия каждого вида и общее количество сырья данного вида, которое может быть использовано предприятием. Учитывая, что изделия А и В могут производиться в любых соотношениях (спрос обеспечен), требуется составить такой план их выпуска, при котором прибыль предприятия от реализации всех изделий максимальна. Таблица 2.1. Вид сырья Нормы расхода сырья (кг) на одно изделие Общее количество сырья (кг) А В 1 12 6 300 2 4 6 180 3 4 12 240 Прибыль от реализации одного изделия (руб.) 30 40 Решение. Данные, представленные в таблице 1 удобно представить в виде Задачу можно решить симплекс-методом ЗЛП. Для этого сформулируем задачу и запишем условие в каноническом виде. 1. Из анализа условия задачи следует, что целевая функция ЗЛП имеет вид Q = 30x1 + 40x2  max (1) при ограничениях: (2) 2. Приводим ЗЛП к каноническому виду, вводя по числу неравенств неотрицательные переменные x5 , x6 и x7 со знаком «+», так как все неравенства системы (1) : Q = 30x1 + 40x2 + 0x3 + 0x4 + 0x5  max (3) при ограничениях: (4) Для нахождения начального опорного плана нужно найти общее решение системы ограничений, но такое, чтобы все свободные члены (4) i были неотрицательными. Второе уравнение имеет предпочтительный вид, в то время как остальные уравнения его не имеют. Для нахождения допустимого общего решения системы ограничений применим метод Жордана. Удобно это делать, записав систему ограничений в виде симплекс-таблицы. Для нахождения общего решения методом Жордана необходимо на каждом шаге выбирать разрешающий элемент. Чтобы соблюсти при этом условие неотрицательности свободных членов, для каждого положительного коэффициента aij рассчитываем . При этом, если коэффициент aij £ 0, то qij не вычисляем, а в соответствующей клетке таблицы ставим прочерк. Затем произвольно выбираем разрешающую строку (кроме строки, соответствующей уравнению в предпочтительном виде), а разрешающим столбцом выбираем тот, в котором в разрешающей строке находится наименьшее в этом столбце значение qij. 3. За базисные (основные) переменные принимаем x5 ; x6 ; x7 , исходные переменные – за свободные переменные, причем x1 = 0; x2 = 0; x3 = 0; x4 = 0. Выражая через свободные переменные (5) и подставляя значения x1= 0; x2 = 0; x3 = 0 в систему (5) получим x3 =300; x4 =180; x5 =240. Таким образом, первый опорный план имеет вид: , а функция . 4. Для проверки оптимальности начального опорного плана составляем симплекс-таблицу 2.2. Симплекс-таблица 2.2 Базис cj 30 40 0 0 0 j*=2 xi i ci bi ai1 ai2 ai3 ai4 ai5 x3 3 0 300 12 6 1 0 0 322 50 x4 4 0 180 4 6 0 1 0 195 30 x5 5 0 240 4 12 0 0 1 262 20 j 0=0 – 30 – 40 0 0 0 779 Для базисных неизвестных величины j = 0. Поэтому подсчитываем 0 = Q и 1,2,3,4,5. : , Q (Х1)= 0 = 300 0 + 180 0 + 240  0 = 0; 1 = 012 + 0  4 + 0  4 – 30 = – 30 ; 2 = 06 + 0  6 + 0  12 – 40 = – 40 ; 3 = 01 + 0  0 + 0  0 – 0 = 0; 4 = 00 + 0  1 + 0  0 – 0 = 0. 5 = 00 + 0  0 + 0  1 – 0 = 0. Поскольку в индексной строке j имеются отрицательные числа 1=–30, 2 = – 40, то начальный опорный план не является оптимальным. 5. Находим направляющий столбец и направляющую строку. Направляющему столбцу соответствует максимальный по модулю отрицательный элемент индексной строки . Следовательно, переменную следует перевести из свободных в базисные. Направляющей строке соответствует минимальное значение : . Следовательно, переменную следует перевести из базисных в свободные. Разрешающим является элемент . Направляющие строка и столбец обозначены в симплекс-таблице 2.1 стрелками. 6. Для определения нового опорного плана формируем симплекс-таблицу 2.3. На место переменной в столбце «Базис, » ставим переменную , в разрешающую строку в столбце «Базис, » записываем значение коэффициента целевой функции при переменной , остальные элементы строки получаются делением элементов строки на разрешающий элемент . В симплекс-таблице 2.3 элемент , а остальные элементы разрешающего столбца полагаем равными 0. Оставшиеся элементы строк вычисляем по правилу прямоугольника . Симплекс-таблица 2.3 Базис cj 30 40 0 0 0 j*=1 xi i ci bi ai1 ai2 ai3 ai4 ai5 x3 3 180 10 0 1 0 -0,5 190,5 18 x4 4 60 2 0 0 1 -0,5 62,5 30 x2 2 40 20 0,3 1 0 0 0,08 63,38 60 j 0=800 – 26,(7) 0 0 0 3,(3) 316,38

Похожие:

	Факультет информационных технологий утверждаю Рабочая программа предназначена для бакалавров кафедр Информатики и математики и Информационных технологий как очной, так и заочной...		«московский психолого-социальный университет» факультет информационных технологий утверждаю Рабочая программа предназначена для бакалавров кафедр Информатики и математики и Информационных технологий очной и заочной формы...
	Факультет информационный технологий утверждаю Рабочая программа предназначена для бакалавров кафедр Информатики и математики и Информационных технологий очной и заочной формы...		Факультет информационных технологий утверждаю Ефимов Павел Павлович, кандидат педагогических наук, кафедра "Информационных технологий", для студентов 4,5-го курсов, обучающихся...
	Факультет информационных технологий утверждаю Составитель Рабочей программы заманская валентина викторовна – доктор филологических наук, профессор кафедры Социально-гуманитарных...		Факультет «Информационных систем и инновационных технологий в управлении» «утверждаю» ...
	«утверждаю» «утверждаю» Начальник гуит фтс россии Разработка стратегии и программы подготовки кадров в области информационных технологий		Применение информационных технологий в системе образования Понятие информационных технологий. Роль средств новых информационных технологий в образовании 10
	Российской Федерации Самарский государственный архитектурно-строительный... Системный анализ – новая, находящаяся в стадии формирования наука о закономерностях развития сложных естественных и искусственных...		Фгбоу впо «ргутиС» Факультет сервисных технологий Кафедра технологий... Рабочая программа рассмотрена и одобрена на заседании кафедры Технологий в сервисе и туризме
	Вероника Игоревна Использование информационных технологий в гуманитарных... Мвц межвузовский центр новых информационных технологий в гуманитарном образовании		Применение технологий olap и Data Mining для поддержки принятия стратегических решений в вузе Дагестанский государственный университет, факультет информатики и информационных технологий, Махачкала, Россия
	Ноу впо институт государственного управления, права и инновационных... Введение. Алгоритм. Программа. Язык программирования Паскаль. Техника безопасности		Российской Федерации Самарский государственный архитектурно-строительный... «Информационные системы», по специальности 23201 «Информационные системы и технологии», ут­вер­ж­ден­ным Министерством образования...
	Факультет информационных технологий Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования		Применение информационных технологий на уроках английского языка... Возможности использования информационно-коммуникативных технологий в обучении английскому языку 17