Симплексный метод решения задач ЗЛП

Для производства двух видов изделий А и Б используется три типа технологического оборудования. На производство единицы изделия А оборудование первого типа используется а1=4 часов, оборудование второго типа а2=8 часов, а оборудование третьего типа а3=9 часов. На производство единицы изделия Б оборудование первого типа используется б1=7 часов, оборудование второго типа б2=3 часов, а оборудование третьего типа б3=5 часов. 

На изготовление этих изделий оборудование первого типа может работать не более чем t1=49 часов, оборудование второго типа не более чем t2=51 часов, оборудование третьего типа не более чем t3=45 часов.

 Прибыль  от реализации единицы готового  изделия А составляет АЛЬФА=6 рублей, а изделия Б – БЕТТА=5 рублей.

 Составить  план производства изделий А  и Б, обеспечивающий максимальную  прибыль от их реализации.

Решение: Составим математическую модель задачи.

Пусть план производства продукции (x1, x2), то есть производится x1 единиц продукции А и x2 единиц продукции В, по смыслу задачи x1 x2, ≥ 0. Тогда целевая функция – прибыль от продажи такого количества изделий, составляет F =6x1 + 5x2 → max, ее нужно максимизировать.

 Составим ограничения, связанные с ограниченным количеством ресурсов.

При плане производства (х1, х2) используется 4х1+7х2 часов работы оборудования первого типа, всего доступно 49 часов работы, поэтому 4х1+7х2≤ 49.

При плане производства (х1, х2) используется 8х1+3х2 часов работы оборудования второго типа, всего доступно 51 часов работы, поэтому 8х1+3х2≤ 51.

При плане производства (х1, х2) используется 9х1+5х2 часов работы оборудования третьего типа, всего доступно 45 часов работы, поэтому 9х1+5х2≤ 45.

Пришли к задаче линейного программирования:

F=6x1+5x2 → max,

4х1+7х2 ≤ 49,

8х1+3х2≤ 51,

9х1+5х2≤ 45,

                                                    х1,х2≥0.

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

F=6x1+5x2 → max,

4х1+7х2 +x3 = 49,

8х1+3х2 +x4= 51,

9х1+5х2 +x5= 45,

х1,х2,х3,х4,х5 ≥ 0.

Базис для этой задачи - столбцы {x3, x4, x5}. Записываем основную задачу (таблица 1):

Таблица 1 – Основная задача

Ограничения	Значение	x1	x2	x3	x4	x5
x3	49	4	7	1	0	0
x4	51	8	3	0	1	0
x5	45	9	5	0	0	1
Цел.функция	0	-6	-5	0	0	0

Оценки (-6;-5), наименьшая оценка в столбце х1, вводим его в базис. Выбираем столбец для вывода, находя min {49/4; 51/8; 45/9} = 45/9 = 5. Выводим из базиса х5.

Новый базис {x3, x4, x1}. Пересчитываем элементы столбца базисных значений и значение целевой функции, и обращенный базис (как по методу Жордана-Гаусса, используя выбранный разрешающий элемент).

Таблица 2 – Первая итерация

Базис	Значение	Обращение			aij
x3	49	1	0	0	4
x4	51	0	1	0	8
x1	45	0	0	1	9
Цел.функция	0	0	0	0	-6

Делим третью строку на 9, вычитаем из первой третью, умноженную на 4; вычитаем из второй третью, умноженную на 8; прибавляем к последней третью, умноженную на 6.

Таблица 3 – Вторая итерация

Базис	Значение	Обращение			aij
x3	29	1	0	-4/9
x4	11	0	1	-8/9
x1	5	0	0	1/9
Цел.функция	30	0	0	2/3

Находим новые симплекс-множители в последней строке (0 0 2/3). Вычисляем оценки для следующего шага:

4    7

                                         (0 0 2/3)   8    3      - (6  5) =  (0  -5/3).

9    5

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

                                                   1   0   -4/9     7       43/9

                           a2’ = B-1a2   =  0   1   -8/9     3   =   -13/9

                                                   0   0    1/9    5         5/9     .

Вносим этот столбец в таблицу (Таблица 3). Выбираем переменную для вывода, находя min{29/43/9;-;5/5/9} = 261/43. Выводим из базиса  х3.

Таблица 3 – Третья итерация

Базис	Значение	Обращение			aij
x3	29	1	0	-4/9	43/9
x4	11	0	1	-8/9	-13/9
x1	5	0	0	1/9	5/9
Цел.функция	30	0	0	2/3	-5/3

Новый базис {x2, x4, x1}. Пересчитываем элементы столбца базисных значений и значение целевой функции, и обращенный базис:

Таблица 4 – Итоговая таблица

Базис	Значение	Обращение			aij
х2	261/43	9/43	0	-4/43
x4	850/43	13/43	1	-44/43
x1	70/43	-5/43	0	7/43
Цел.функция	1725/43	15/43	0	22/43

Находим новые симплекс-множители (15/43 0 22/43). Вычисляем оценки:

4  7

  (15/43 0 22/43) 8   3    - (6  5) = (0 0).

9  5

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

х1 = 70/43(1,63),

  х2 = 261/43(6,07),

     F = 1725/43(40,12).

 

3 Реализация программного продукта

3.1 Описание  среды разработки и системные  требования

Требования к аппаратуре и программному обеспечению.

Аппаратные требования:

Необходимый объем ОЗУ 64 Мб и графическим адаптером, поддерживающим режим 800х600 и выше, глубина цвета 32 бит. Необходимое место на жестком диске 28 Кб. Клавиатура, мышь.

Программные требования:

Операционная система: Windows2000 и выше.

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

Так же необходимо выбрать среду разработки, в которой будет реализовываться программный продукт. Для данной методики было решено использовать Microsoft Visual Studio, с пакетом объектно-ориентированного программирования С++, т.к. данный язык имеет высокое быстродействие, широкую функциональность, поддержку графического программирования, что необходимо по задумке для воплощения идеи автора программы, а так же простой, понятный, "дружественный" интерфейс.

Требования к пользовательскому интерфейсам:

• программа должна работать в графическом режиме;
• в программе должны использоваться кнопки для решения;
• программа должна содержать поля для ввода данных;
• программа должна выводить на экран решения .

3.2 Руководство пользователя

Порядок работы с программой:

• Запускаем программу Simplex_GUI.exe;
• Задаем размерность матрицы (рисунок 2);

Рисунок 2 – Размерность матрицы

• Кликаем по кнопке задать;
• Далее заполняем появившиеся поля, в виде матрицы, которая в принципе является нашей симплекс таблицей (рисунок 3);

Рисунок 3 – Заполненная матрица

• Кликаем кнопку вычислить;
• После недолгих расчетов появляется окошко с результатами расчетов, значение x4 мы в расчет не берем, поскольку это дополнительная переменная, необходимая для расчетов(рисунок 4).

Рисунок 4 - Решение

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

В первой главе данной курсовой работы были раскрыты теоретические основы линейного программирования, было установлено, что целью линейного программирования является решение задач оптимизации, то есть поиск такого решения, при котором мы получим максимальную выгоду, с минимальными убытками. Так же был разобран модифицированный симплекс-метод. Модифицированному симплекс метод, так же как и обычный может решать практически все задачи оптимизации, но кроме того, как мы выяснили имеет ряд преимуществ, такие как: скорость, точность и меньший объем требуемой памяти ЭВМ.

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

В третьей главе, на основе модифицированного симплекс метода, мы создали программный продукт и проверили точность его решения на задаче, поставленной во второй главе. Программа была написана в среде Microsoft Visual Studio, на языке C++ на основе и универсального симплекс-метода решения задач линейного программирования.

 

Список используемых источников

Учебники и учебные пособия

1. Акулич И.Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 2009. — 319 с. — ISBN 5-06-002663-9
2. Астафьев Н.Н., “Противоположные задачи линейного программирования как инструментарий моделирования”, Автомат. и телемех., 2012, № 2, 5–10.
3. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. — М.: Наука, 2010. — 446 с.
4. Берюхова Т.Н.Банк производственных задач в расчетах на ЭВМ: учебное пособие. – Тюмень.: ТюмИИ, 2011. – 124с.
5. Давыдов Э.Г. Исследование операций. — М.: Высшая школа, 2009. — 382 с.
6. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. — М.: Наука, 2010. — 348 с.
7. Карманов В.Г. Математическое программирование: учебное пособие для студентов вузов. – М.: Физматлит, 2009. – 264с.
8. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. — Минск.: Вышейшая школа, 2006. — 286 с.
9. Лунгу К.К. Линейное программирование. Руководство к решению задач. – М.: ФИЗМАТЛИТ, 2009.
10. Орлов А.И. Теория принятия решений. Учебное пособие. - М.: Издательство "Март", 2006.
11. Пашутин С. A. Оптимизация издержек и технология формирования оптимального ассортимента. // Управление персоналом. – 2007. - №5. – с.20-24.
12. Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2011. — С. 1296.