Определение количества и вида тракторных и автомобильных глушителей, которые следует изготовить предприятию, чтобы прибыль была максимальной. Решение задачи линейного программирования графическим и симплекс-методом, с помощью табличного редактора Excel.
Краткое сожержание материала:

Размещено на

Размещено на

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ -

УЧЕБНО-НАУЧНО-ПРОИЗВОДСТВЕНЫЙ КОМПЛЕКС»

ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ

имени Н.Н. Поликарпова

ФАКУЛЬТЕТ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

Кафедра: «Вычислительной техники и информационных технологий»

Составление оптимального плана производства тракторных и автомобильных глушителей математическими методами

Студент Яловик Ярослав Леонидович

Специальность 230105 «Программное обеспечение вычислительной техники и автоматизированных систем».

Преподаватель Кирюхина Елена Николаевна

Орел,2012

Содержание

• Введение
• 1. Постановка задачи
• 2. Основные теоретические сведения
• 3. Построение математической модели
• 4. Решение задачи симплекс-методом
• 5. Решение задачи графическим методом
• 6. Решение задачи в EXCEL
• Заключение
• Список литературы

Введение

Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции. Казалось бы, что для исследования линейной функции многих переменных на условный экстремум достаточно применить хорошо разработанные методы математического анализа, однако невозможность их использования можно довольно просто проиллюстрировать.

С помощью различных методов можно решать все виды задач.

Для решения задач линейного программирования потребовалось создание специальных методов. Особенно широкое распространение линейное программирование получило в экономике, так как исследование зависимостей между величинами, встречающимися во многих экономических задачах, приводит к линейной функции с линейными ограничениями, наложенными на неизвестные.

Цель данного курсового проекта является рассмотрение задачи линейного программирования, решения ее графическим и симплекс методом, и с помощью табличного редактора Excel, решение задачи осуществляется симплекс-методом.

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

Для изготовления тракторных(А) и автомобильных(В) глушителей используется токарное, сварочное и фрезерное оборудование. Затраты времени на обработку одного изделия для каждого из оборудования указаны в таблице1. В ней же указан общий фонд рабочего времени каждого из типов используемого оборудования, а также прибыль от реализации одного изделия каждого вида.

Название оборудования	Затраты времени на обработку изделия	Общий фонд рабочего времени
	A	B
Фрезерное	3	1	75
Токарное	1	1	30
Сварочное	1	4	84
Прибыль	3	4

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

2. Основные теоретические сведения

Алгоритм симплекс-метода:

1) Определить число и состав базисных и свободных переменных.

2) Выразить базисные переменные через свободные переменные.

3) Выразить целевую функцию через свободные переменные.

4) Построить начальную симплекс-таблицу.

5) Проверить решение на оптимальность: если в F-строке (кроме С0) все Сj0, то получено оптимальное решение: X=(B1,...,Bm,0,...,0), F=C0. Если же существует Cj<0, то решение можно улучшить, но предварительно надо проверить факт существования решения.

6) Проверить существование решения: рассмотрим все столбцы, у которых Сj<0, если существует хотя бы один столбец, у которого все коэффициенты Ai,j<0, то задача решения не имеет, т.к. множество допустимых решений D не ограничено и целевая функция неограниченно возрастает. Если таких столбцов нет, то переходим к следующему этапу.

7) Выбрать свободную переменную, которую надо ввести в базис (выбор разрешающего столбца): это столбец, с минимальным значением Сj (пусть это k-й столбец)

8) Выбрать базисную переменную, которую надо вывести из базиса (выбор разрешающей строки): рассмотрим k-й столбец и все его элементы, которые больше нуля, т.е. Ai,k>0; для всех этих элементов находим отношение Bi/Ai,k и выбираем строку, которая соответствует минимальному значению этого отношения (пусть это i-я строка); соответствующая i-я переменная Xi выводится из базиса; при нескольких одинаковых отношениях берем любую строку; элемент Ai,k называется разрешающим элементом.

9) Пересчитать симплекс-таблицу: составляем новую симплекс-таблицу заменив в составе базисных переменных Xi на Xk; заполняем сначала новую k-ю строку, записывая в нее элементы старой i-ой строки, поделенные на разрешающий элемент; после заполнения k-ой строки заполняем оставшиеся строки; для этого k-ю строку умножаем последовательно на такие числа, чтобы после сложения ее с каждой строкой старой таблицы в k-ом столбце получить везде ноль (кроме единицы в k-ой строке).

10) После заполнения новой симплекс-таблицы алгоритм возвращается к 5-му пункту.

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

Пусть X₁ - первый вид продукции, a X₂ - второй вид продукции. Получаем следующие уравнения:

3Х₁ + Х₂ ? 75;

Х₁ + Х₂ ? 30;

Х₁ + 4Х₂ ? 84;

Целевая функция имеет вид:

Z(X) = 3X₁ + 4X₂ > max

Математическая модель задачи:

Z(X) = 3X₁ + 4X₂ > max

3X₁ + X₂ ? 75

X₁ + X₂ ? 30

X₁ + 4X₂ ? 84

X₁, X₂ ? 0

4. Решение задачи симплекс-методом

Приведение задачи к каноническому виду:

Каноническая задача линейного программирования отличается от других задач тем, что ее системой (ограничений является система уравнений, а не неравенств, и все переменные не отрицательные. При необходимости перехода от неравенства к уравнению вводят дополнительные переменные:

3Х₁ + Х₂ ? 75 3Х₁ + Х₂ +Х₃=75

Х₁ + Х₂ ? 30 => Х₁ + Х₂ + Х₄= 30

Х₁ + 4Х₂ ? 84 Х₁ + 4Х₂ + Х₅ = 84

Х₁,Х₂ ? 0 Х₁,Х₂,Х₃,Х₄,Х₅ ? 0

Если система ограничений содержит знак «<», то к левой части неравенства добавляется дополнительная переменная со знаком «+». Если

знак.« > », то добавляется переменная со знаком «-».

Дополнительные переменные вводят в целевую функцию с коэффициентом, равным нулю X₁,X₂,X₃,X₄

Система ограничений этой задачи является системой уравнений, разрешенной относительно переменных X₃,X₄,X₅

Пусть имеется задача линейного программирования в канонической форме:

Z(X) = 3X₁ + 4X₂ > max

3Х₁ + Х₂ +Х₃=75

Х₁ + Х₂ + Х₄= 30

Х₁ + 4Х₂ + Х₅ = 84

Х₁,Х₂,Х₃,Х₄,Х₅ ? 0

Система ограничений этой задачи является системой уравнений, разрешенной относительно переменных X₃, X₄, X₅. Получаем:

X₃ = 75 - (3X₁ - X₂₎;