Разработка программы

 
СОДЕРЖАНИЕ

ВВЕДЕНИЕ……………………………………….………………...……….…….......4

1 ОБЩАЯ ЧАСТЬ.………..……………………………………………………..........6

1.1 Постановка задач.……...……………………..…………………………….…..…6

1.2 Цели разработки.………………………………………..…………………….…..6

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

1.4 Описание математического метода……………………………….……………..9

2 СПЕЦИАЛЬНАЯ ЧАСТЬ………………………….……..……………………….11

2.1 Расчет математической модели.………………....………………………..........11

2.2 Описание программы ..…………....……………...……………………………..20

2.2.1 О программе .…………………………………………………………………..21

2.2.2 Алгоритм работы программы………………………...…….………………...21

2.2.3 Входные данные ………………………………………………………………25

2.2.4 Выходные данные……………………………………………………………..25

2.3 Тестирование программы……………………………………………………….25

2.4 Руководство пользователю……………………………………………………...27

ЗАКЛЮЧЕНИЕ………………………………………………………...……………28

ЛИТЕРАТУРА……………………………………………………………….......…..29

ПРИЛОЖЕНИЕ А…………………………………………………………..……….30

ПРИЛОЖЕНИЕ Б…………………………………………………………..………..32

 
ВВЕДЕНИЕ

     В 50-70-е годы XX века стало очевидно, что человечество вступает в новую эпоху, дорогу к которой проложило бурное развитие техники и, в первую очередь, компьютеров, и НТР в целом. Развитие компьютерных технологий позволило обществу подойти к глобальной проблеме информатизации, связанной с быстро возрастающими интеграционными процессами, проникающими во все сферы нашей деятельности: науку, культуру, образование, производство, управление и т. д.

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

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

 
вычислительной техники, а также разнообразных средств  информационного взаимодействия и  обмена.

     История развития информатизации началась в  США с 60-х годов XX века. Затем данное понятие рассматривалось рядом стран, таких как Япония в 70-х годах и с конца 70-х годов странами Западной Европы. Универсальным техническим средством обработки любой информации является компьютер, который играет роль усилителя интеллектуальных возможностей человека и общества в целом. Появление и развитие компьютеров - это необходимая составляющая процесса информатизации общества и образования.

 
1 ОБЩАЯ ЧАСТЬ

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

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

 
Таблица 1

 
 
 
     1.2 Цели разработки

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

        1. Понять математические закономерности конкретного объекта, его структуру, основные свойства и законы развития.

        2. Научиться управлять  объектом или процессом при  заданных целях и

критериях.

        3. Прогнозировать  прямые и косвенные последствия  реализации данной математической модели.

При достижении данных целей программа должна удовлетворять  требованиям:

        1. Быть понятной  пользователю.

        2. Обладать наглядным  графическим интерфейсом.

        3. Быстро и корректно  выполнять расчеты.

        4. Реализовывать данный математический метод оптимальным образом.

        5. Легко переноситься  на различные технологические  платформы.

        6. Обеспечить обработку  некорректно введенных данных.

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

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

     1. Ограничения вида  «£»- ресурсные ограничения. Справа находится то, что мы используем на производстве, слева – то, что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0».

     2. Ограничения вида «=». Часто бывает что, несмотря на то, что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания

единичного  базиса - Yi. В систему ограничений они входят с коэффициентом

«1», а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Zmin - «+M», при Zmax - «-M»).

     3. Ограничения вида «³» - плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл - перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0». А искусственные переменные (Y) как в предыдущем случае.

Алгоритм  симплекс метода (первая симплекс таблица)

Пусть система приведена к каноническому виду:

Все hi должны быть больше либо равны нулю, где i=1,2...m. Для дальнейших рассуждений вычислений будем пользоваться первой симплекс таблицей.

Таблица 2

 
Продолжение таблицы 2

 
Первый столбец - базисные переменные.

Седьмой столбец - свободные члены (hi³0).

Вторая строка - служит для того, чтобы ответить на вопрос: «оптимально решение или нет».

Cm - коэффициенты при целевой функции.

Xm - сами переменные, входящие в целевую функцию и в систему ограничений.

Основное  поле симплекс метода - система коэффициентов  из уравнения.

Для первой итерации Z0= å ci*hi.

D1, D2, D3,..., Dm - оценки они рассчитываются по формуле:

     D j = å c_iq_ij-c_j.

Индексная строка позволяет нам судить об оптимальности  плана:

        1. При отыскании Zmin в индексной строке должны быть отрицательные и нулевые оценки.

        2. При отыскании Zmax в индексной строке должны быть нулевые и положительные оценки.

 
 
     1.4 Описание математического метода

     Переход к составлению второй симплекс-таблицы:

 
      Для этого отыскиваем ключевой (главный) столбец и ключевую (главную) строку. Ключевым столбцом является тот, в котором находится наибольший положительный элемент индексной строки при отыскании Zmin или наименьший отрицательный элемент при отыскании Zmax.

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

Переход к итерациям:

        1. Выводится базис  ключевой строки, уступая место  переменной из ключевого столбца  со своим коэффициентом.

        2. Заполняется строка  вновь введенного базиса путем  деления соответствующих элементов  выделенной строки предыдущей итерации на разрешающий элемент.

        3. Если в главной  строке содержится нулевой элемент,  то столбец, в котором находиться  этот элемент переноситься в  последующую итерацию без изменения.

        4. Если в главном  столбце имеется нулевой элемент,  то строка, в которой он находиться переноситься без изменения в последующую итерацию.

        5. Остальные элементы  переносятся по формуле:

Новая строка = текущая строка – (ее коэффициент  в ключевом столбце*на новую ведущую строку).

 
      2 СПЕЦИАЛЬНАЯ ЧАСТЬ

     2.1 Расчет математической модели

     Для расчета математической модели «разработка приложения, реализующего симплексный метод решения задач линейного программирования» сделаны три варианта решения задач.

Первый  вариант:

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

 
Таблица 3

 
        1) Определим переменные: x_a–количество изделий А; x_b–количество изделий B.

        2) Целевая функция:

 
        3) Ограничения: 

Задача  линейного программирования имеет  вид:

При условиях:

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

Условие:

Составим  первую симплекс таблицу:

Таблица 4

 
Составим  вторую симплекс-таблицу:

Таблица 5

 
Zстр. = (-6  -3  0  0  0  0/0) – (-6)*(1    0  0  0  / );

X₁ = (2  5  1  0  0  0/59) – 2*(1    0  0  0  / );

X₂ = (3  8  0  1  0  0/38) – 3*(1    0  0  0  / );

X₃ = (4  6  0  0  1  0/58) – 4*(1    0  0  0  / );

Ответ: Z = 70 при x_a= , x_b=0.

Второй  вариант решения:

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

 
Таблица 6

 
        1) Определим переменные: x_a – количество изделий А; x_b – количество изделий B.

        2) Целевая функция:

        3) Ограничения: 

Задача  линейного программирования имеет  вид:

При условиях:

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

Условие:

Составим  первую симплекс таблицу:

Таблица 7

 
Продолжение таблицы 7