Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лабораторна робота 2
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Математичні методи дослідження операцій
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра автоматизованих систем управління
/
Лабораторна робота №3-4
з дисципліни “Математичні методи дослідження операцій”
на тему
«Симплекс метод »
Мета роботи: вивчення симплекс методу для знаходження розв’язку задач лінійного програмування .
План
Короткі теоретичні відомості.
Постановка задачі
Симплекс метод розв’язаний за допомогою симплекс таблиць Жордана Гауса
Симплекс метод розв’язаний за допомогою симлекс таблиць з додаванням змінних.
Розв’язання за допомогою пакету програм SimplexWin
Розв’язання за допомогою власної програми.
Хід роботи
1. Короткі теоретичні відомості
Симплекс метод - універсальний метод для вирішення лінійної системи рівнянь або нерівностей і лінійного функціоналу.
Для приведення системи обмежень нерівностей до канонічного виду, необхідно в системі обмежень виділити одиничний базис.
I. Обмеження виду «» - ресурсні обмеження. Справа знаходиться те що ми використовуємо на виробництві, ліворуч - те що отримуємо. При таких обмеженнях вводять додаткові змінні з коефіцієнтом «+1», що утворюють одиничний базис. У цільову функцію ці змінні увійдуть з коефіцієнтом «0».
II. Обмеження виду «=». Часто буває, що незважаючи на те що обмеження мають вигляд рівності, одиничний базис не виділяється або важко виділяється. В цьому випадку вводяться штучні змінні для створення одиничного базису - Yi. В систему обмежень вони входять з коефіцієнтом «1», а в цільову функцію з коефіцієнтом «M», що прагнуть до нескінченності (при Fmin - «+ M», при Fmax - «-M»).
III. Обмеження виду «» - планові обмеження. Додаткові змінні (X), що несуть певний економічний зміст - перевитрата ресурсів або перевиконання плану, перевиробництво, додаються з коефіцієнтом «-1», в цільову функцію - з коефіцієнтом «0». А штучні змінні (Y) як у попередньому випадку.
Алгоритм симплекс методу
Нехай система приведена до канонічного виду.
X1+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1
X2+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1 (1)
X3+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1
……………………………………………………………….
Xm+ qm,m+1 Xm+1 + …. + qm,m+n Xm+n =hm
У ній m базисних змінних, k вільних змінних. m + k = n - всього змінних.
Fmin = C1X1 + C2X2 + C3X3 + .... + CnXn
Всі hi повинні бути більше або дорівнюють нулю, де i = 1,2 ... m. На першому кроці в якості допустимого рішення приймаємо всі Xj = 0 (j = m +1, m +2, ..., m + k). При цьому всі базисні змінні Xi = Hi.
Для подальших міркувань обчислень будемо користуватися першою симплекс таблицею.
Таблица 1 –Перша симплес таблиця .
C
Б
H
C1
C2
…
Cm
Cm+1
…
Cm+k
X1
X2
…
Xm
Xm+1
…
Xm+k
C1
C2
C3
:
:
Cm
X1
X2
X3
:
:
Xm
h1
h2
h3
:
:
hm
1
0
0
:
:
0
0
1
0
:
:
0
:
:
:
:
:
:
0
0
0
:
:
0
q1,m+1
q2,m+1
q3,m+1
:
:
qm,m+1
:
:
:
:
:
:
q1,m+k
q2,m+k
q3,m+k
:
:
qm,m+k
F=
F0
…
m
m+1
…
m+k
Перший стовпчик-коефіцієнти в цільової функції при базисних змінних.
Другий стовпчик - базисні змінні.
Третій стовпчик - вільні члени (hi0).
Самий верхній рядок - коефіцієнти при цільовій функції.
Другий верхній рядок - змінні, що входять в цільову функцію і в систему обмежень.
Основне поле симплекс методу - система коефіцієнтів з рівняння.
Останній рядок - служить для того, щоб відповісти на питання: «оптимальний план чи ні».
2. Постановка задачі
Розв’язати задачу лінійного програмування симплекс методом (номер завдання відповідає двом останнім цифрам залікової книжки студента, крім цифр 00 – які відповідають завданню під номером100)
Варіант 48
F(x1,x2) = 3x1 + 6x2 max ;
x1 + x2 8,
3x1 + 7x2 21,
x1 + 2x2 6,
0x1 7, 0x2 7.
2.1 Розв’язання без використання пакетів програм.
Cимплекс метод розв’язаний за допомогою сиплекс таблиць
Жордана -Гауса.
Для того щоб показати , що я освоїв даний матеріал зміню напрям цільової функції на min . Оскільки в даній лабораторній роботі розглядається і сиплекс метод двійної задачі то в наступному методі буде показано значення цільової функції при max.
З попередньої лабораторної роботи відомо що
F(0,8)=48->max
F (0,3)=18-> min
Приведемо систему обмежень до системи нерівностей сенсу ≤, помноживши відповідні рядки на (-1).
Визначимо мінімальне значення цільової функції F (X) = 3x1 + 6x2 при наступних умовах-обмеженнях.
x1 + x2 8,
3x1 + 7x2 21,
x1 + 2x2 6,
Для побудови першого опорного плану систему нерівностей приведемо систему рівнянь до рівностей шляхом введення додаткових змінних (перехід до канонічної форми).
В 1-й нерівності типу ()вводимо базисну змінну x3. В 2-й нерівності типу
() вводимо базисну змінну x4. У 3-й нерівності типу () вводимо базисну змінну x5.
1x1 + 1x2 + 1x3 + 0x4 + 0x5 = 8
-3x1-7x2 + 0x3 + 1x4 + 0x5 = -21
-1x1-2x2 + 0x3 + 0x4 + 1x5 = -6
Матриця коефіцієнтів A=a(ij) цієї системи рівнянь має вигляд :
Базисні змінні це змінні, які входять тільки в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь щодо базисних змінних:
x3, x4, x5,
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,8,-21,-6)
Базисне рішення називається допустимим, якщо воно невід’ємне.
Базис
B
x1
x2
x3
x4
x5
x3
8
1
1
1
0
0
x4
-21
-3
-7
0
1
0
x5
-6
-1
-2
0
0
1
F(X0)
0
-3
-6
0
0
0
1. Перевірка критерію оптимальності.
План 0 в симплексного таблиці є псевдопланом, тому визначаємо провідний рядок і стовпець.
2. Визначення нової вільної змінної.
Серед негативних значень базисних змінних вибираємо найбільший по модулю.
Провідним буде 2-ий рядок, а змінну x4 слід вивести із базису.
3. Визначення нової базисної змінної.
Мінімальне значення θ відповідає 2-му стовпцю, тобто змінну x2 необхідно ввести в базис.
На перетині провідного рядка і стовпця знаходиться дозволяючий елемент (ДЕ), який дорівнює (-7).
Базис
B
x1
x2
x3
x4
x5
x3
8
1
1
1
0
0
x4
-21
-3
-7
0
1
0
x5
-6
-1
-2
0
0
1
F(X)
0
-3
-6
0
0
0
Θ(дельта)
0
-3 : (-3) = 1
-6 : (-7) = 6/7
-
-
-
4. Перерахунок симплекс таблиці
Виконуємо перетворення симплексного таблиці методом Жордана-Гаусса.
Базис
B
x1
x2
x3
x4
x5
x3
5
4/7
0
1
1/7
0
x2
3
3/7
1
0
-1/7
0
x5
0
-1/7
0
0
-2/7
1
F(X0)
18
-3/7
0
0
-6/7
0
Показую розрахунок кожного елемента у вигляді таблиці:
B
x 1
x 2
x 3
x 4
x 5
8-(-21 • 1):-7
1-(-3 • 1):-7
1-(-7 • 1):-7
1-(0 • 1):-7
0-(1 • 1):-7
0-(0 • 1):-7
-21 : -7
-3 : -7
-7 : -7
0 : -7
1 : -7
0 : -7
-6-(-21 • -2):-7
-1-(-3 • -2):-7
-2-(-7 • -2):-7
0-(0 • -2):-7
0-(1 • -2):-7
1-(0 • -2):-7
0-(-21 • -6):-7
-3-(-3 • -6):-7
-6-(-7 • -6):-7
0-(0 • -6):-7
0-(1 • -6):-7
0-(0 • -6):-7
У базисному стовпці всі елементи позитивні.
Переходимо до основного алгоритму симплекс-методу.
1. Перевірка критерію оптимальності.
Серед значень індексного рядка немає позитивних елементів(тих що задовольняють умову). Тому ця таблиця визначає оптимальний план задачі.
Остаточний варіант симплекс-таблиці:
Базис
B
x1
x2
x3
x4
x5
x3
5
4/7
0
1
1/7
0
x2
3
3/7
1
0
-1/7
0
x5
0
-1/7
0
0
-2/7
1
F(X1)
18
-3/7
0
0
-6/7
0
Оптимальний план при F=3X1+6X2->min
x3 = 5
x2 = 3
x5 = 0
F(X) = 6•3 = 18
Отже значення з лабораторною роботою №1 співпали.
Перевірка даного методу в Exel подана нижче у розділі №3 (малюнок 1-2)
Cимплекс метод розв’язаний за допомогою сиплекс таблиць
З додаванням додаткових змінних .
Умова
F(x1,x2) = 3x1 + 6x2 max ;
x1 + x2 8,
3x1 + 7x2 21,
x1 + 2x2 6,
0x1 7, 0x2 7.
Тут розглядається варіант зі снаходженням оптимального плану для max.
Для побудови першого опорного плану систему нерівностей приведемо до системи рівностей шляхом введення додаткових змінних (перехід до канонічної формі).
В 1-й нерівності типу (≤) вводимо базисну змінну x3. В 2-й нерівності типу (≥) вводимо базисну змінну x4 зі знаком мінус. У 3-й нерівності типу (≥) вводимо базисну змінну x5 зі знаком мінус.
1x1 + 1x2 + 1x3 + 0x4 + 0x5 = 8
3x1 + 7x2 + 0x3-1x4 + 0x5 = 21
1x1 + 2x2 + 0x3 + 0x4-1x5 = 6
Введемо штучні змінні x: в 2-e рівність вводимо змінну x6; в 3-у рівність вводимо змінну x7;
1x1 + 1x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 = 8
3x1 + 7x2 + 0x3-1x4 + 0x5 + 1x6 + 0x7 = 21
1x1 + 2x2 + 0x3 + 0x4-1x5 + 0x6 + 1x7 = 6
Для постановки задачі на максимум цільову функцію запишемо так:
F (X) = 3x1 +6 x2 - Mx6 - Mx7 → max
За використання штучних змінних, що вводяться у цільову функцію, накладається так званий штраф величиною М, дуже велике позитивне число, яке зазвичай не задається.
Отриманий базис називається штучним, а метод рішення називається методом штучного базису.
Причому штучні змінні не мають відношення до змісту поставленого завдання, однак вони дозволяють побудувати стартову точку, а процес оптимізації змушує ці змінні приймати нульові значення та забезпечити допустимість оптимального рішення.
З рівнянь виражаємо штучні змінні:
x6 = 21-3x1-7x2+x4
x7 = 6-x1-2x2+x5
які підставимо в цільову функцію:
F(X) = 3x1 + 6x2 - M(21-3x1-7x2+x4) - M(6-x1-2x2+x5) → max
або
F(X) = (3+4M)x1+(6+9M)x2+(-1M)x4+(-1M)x5+(-27M) → max
Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд:
1
1
1
0
0
0
0
3
7
0
-1
0
1
0
1
2
0
0
-1
0
1
Базисні перемінні це змінні, які входять тільки в одне рівняння системи обмежень і при цьому з одиничним коефіцієнтом.
Вирішимо систему рівнянь щодо базисних змінних:
x3, x6, x7,
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,8,0,0,21,6)
Базисне рішення називається допустимим, якщо воно невід’ємне.
Базис
B
x1
x2
x3
x4
x5
x6
x7
x3
8
1
1
1
0
0
0
0
x6
21
3
7
0
-1
0
1
0
x7
6
1
2
0
0
-1
0
1
F(X0)
-27M
-3-4M
-6-9M
0
1M
1M
0
0
Переходимо до основного алгоритму симплекс-методу.
Ітерація № 1.
Крок1
Базис
БП
x 1
x 2
x 3
x 4
x 5
X6
x7
x3
8
1
1
1
0
0
0
0
X6
21
3
7
0
-1
0
1
0
X7
6
1
2
0
0
-1
0
1
F(x)
-27M
-4M-3
-9M-6
0
M
M
0
0
Перерахунок симплекс-таблиці.
Формуємо наступну частину симплексного таблиці.
Замість змінної x до таблиці 1 увійде змінна x2.
Рядок, відповідної змінної x2 в плані(таблиці) 2, отриманої в результаті поділу всіх елементів рядка x6 таблиці 1 на дозвільний (той який стоїть на перетині рядків) елемент ДЕ = 7
На місці дозвільного елемента в таблиці(плані) 1 отримуємо 1.
В інших клітинах стовпця x2 плану 1 записуємо нулі.
Таким чином, у новому плані 1 заповнюю рядок x2 і стовпець x2.
Всі інші елементи нового плану 1, включаючи елементи індексного рядка, визначаються за правилом прямокутника.
Для цього вибираємо зі старого плану(таблиці 1 ) чотири числа, які розташовані у вершинах прямокутника і завжди включають дозвільний елемент ДЕ.
Зроблю розрахунок кожного елемента у вигляді таблиці:
Крок 2
Базис
B
x 1
x 2
x 3
x 4
x 5
x6
X7
x3
5
4/7
0
1
1/7
0
-1/7
0
x2
3
3/7
1
0
-1/7
0
1/7
0
X7
0
1/7
0
0
2/7
-1
-2/7
1
F(X)
18
-1/7M-3/7
0
0
-2/7M-6/7
M
9/7M+6/7
0
Отримуємо нову симплекс-таблицю:
Крок 3
Базис
B
x 1
x 2
x 3
x 4
x 5
X6
x7
x3
5
1/2
0
1
0
1/2
0
-1/2
x2
3
1/2
1
0
0
-1/2
0
1/2
x4
0
1/2
0
0
1
-7/2
-1
7/2
F(X)
18
0
0
0
0
-3
M
M+3
Перерахунок симплекс-таблиці.
Крок 4
Базис
B
x 1
x 2
x 3
x 4
x 5
X6
X7
x5
10
1
0
2
0
1
0
-1
x2
8
1
1
1
0
0
0
0
x4
35
4
0
7
1
0
-1
0
F(X3)
48
3
0
6
0
0
M
M
Отже отримали нову симплекс-таблицю:
Базис
B
x1
x2
x3
x4
x5
x6
x7
x5
10
1
0
2
0
1
0
-1
x2
8
1
1
1
0
0
0
0
x4
35
4
0
7
1
0
-1
0
F(X3)
48
3
0
6
0
0
1M
1M
Оптимальний план запишемо так:
x5 = 10
x2 = 8
x4 = 35
F(X) = 6•8 = 48
3. Розв’язання з допомогою пакету програм SimplexWin
Cимплекс метод з додаванням змінних , розв’язаний за допомогою сиплекс таблиць .
Ввід даних :
/
Крок 1
/
Крок 2
/
Крок 3
/
Крок 4
/
Результат:
/
4. Розв’язання за допомогою власної програми.
Програма написана мовою С++
Для правильного вирішення система лінійних обмежень повинна бути приведена до канонічного виду.
При запуску програми потрібно ввести кількість рівнянь обмежень (rows) і найбільший індекс змінної (cols).
Після цього потрібно послідовно ввести коефіцієнти рівнянь (xi) та їх праві частини (b), а також коефіцієнти цільової функції. Якщо який-небудь коефіцієнт відсутній, слід ввести нуль.
Для виведення результату потрібно натиснути пробіл.
Якщо для вирішення завдання були введені додаткові перемінні або штучні базиси, то їх потрібно виключити з підсумкового відповіді.
Лістинг програми main.cpp
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <fstream>
#include <sstream>
#include <string>
#include "user_data.h"
#include "simplex.h"
using std::cout;
using std::endl;
void simplex::init()
{
int i, j;
func = 0;
sv = new double *[num_l];
for (i = 0; i < num_l; i++)
sv[i] = new double [num_v * 2];
for (i = 0; i < num_l; i++) {
for (j = 0; j < num_v; j++)
sv[i][j] = system[i][j];
for (; j < num_v * 2; j++)
if (i + num_v == j)
if (way)
sv[i][j] = 1;
else
sv[i][j] = -1;
else
sv[i][j] = 0;
}
istr = new double [num_v * 2];
bv = new double *[num_l];
for (i = 0; i < num_l; i++) {
bv[i] = new double [2];
bv[i][0] = i + num_v;
bv[i][1] = fm[i];
}
for (i = 0; i < num_v * 2; i++)
if (i < num_v)
istr[i] = function[i] * -1;
else
istr[i] = 0;
i_lcol = 0;
for (i = 0; i < num_v * 2 - 1; i++) {
if (istr[i] < 0)
if (fabs(istr[i + 1]) > fabs(istr[i]))
i_lcol = i + 1;
}
th = new double [num_l];
for (i = 0; i < num_l; i++)
th[i] = bv[i][1] / sv[i][i_lcol];
i_lrow = 0;
for (i = 0; i < num_l - 1; i++)
if (th[i] > th[i + 1])
i_lrow = i + 1;
alm = sv[i_lrow][i_lcol];
print_result_to_file(0);
}
bool simplex::plane_is_valid()
{
int i;
bool result = true;
if (way)
for (i = 0; i < num_v * 2; i++)
if (istr[i] < 0) {
result = false;
break;
}
if (!way)
for (i = 0; i < num_v * 2; i++)
if (istr[i] >= 0) {
result = false;
break;
}
return result;
}
bool simplex::function_is_undefined()
{
int i;
for (i = 0; i < num_l; i++)
if (th[i] < 0) {
return false;
}
return true;
}
void simplex::gen_plane()
{
int i, j, it_num = 0;
double A, B;
while (!plane_is_valid() && function_is_undefined()) {
A = bv[i_lrow][1];
B = istr[i_lcol];
func -= A * B / alm;
double *tmp_bv = new double [num_l];
bv [i_lrow][0] = i_lcol;
A = bv[i_lrow][1];
for (i = 0; i < num_l; i++) {
B = sv[i][i_lcol];
tmp_bv[i] = bv[i_lrow][1];
if (i != i_lrow)
tmp_bv[i] = bv[i][1] - A * B / alm;
else
tmp_bv[i] /= alm;
}
for (i = 0; i < num_l; i++)
bv[i][1] = tmp_bv[i];
double *tmp_istr = istr;
B = istr[i_lcol];
for (i = 0; i < num_v * 2; i++) {
A = sv[i_lrow][i];
tmp_istr[i] = istr[i] - A * B / alm;
}
istr = tmp_istr;
double **tmp_sv = new double *[num_l];
for (i = 0; i < num_l; i++)
tmp_sv[i] = new double [num_v * 2];
for (i = 0; i < num_l; i++)
for (j = 0; j < num_v * 2; j++) {
tmp_sv[i][j] = sv[i][j];
A = sv[i_lrow][j];
B = sv[i][i_lcol];
if (i == i_lrow)
tmp_sv[i][j] /= alm;
else
tmp_sv[i][j] = sv[i][j] - A * B / alm;
}
sv = tmp_sv;
i_lcol = 0;
for (i = 0; i < num_l; i++)
th[i] = bv[i][1] / sv[i][i_lcol];
i_lrow = 0;
for (i = 0; i < num_l -1; i++)
if (th[i] > th[i + 1])
i_lrow = i + 1;
alm = sv[i_lrow][i_lcol];
it_num++;
print_result_to_file(it_num);
}
if (!function_is_undefined())
cout << "zZilova funkzija ne obmeshena , dana zadasha nemaje rishenn" << endl;
else {
cout << "f(x) = " << func << "" << endl;
for (i = 0; i < num_l; i++) {
cout << "x" << bv[i][0] + 1 << " = " << bv[i][1] << endl;
}
cout << "Resultati zapisani u table.txt" << endl;
}
}
void simplex::print_result_to_file(int it_num)
{
int i, j;
if (!it_num) {
table << "Задана цільова функція:" << endl;
std::stringstream f_x;
f_x << "f(x) = ";
for (i = 0; i < num_v; i++) {
if (!i)
f_x << function[i] << "x" << i + 1 << " ";
else {
if (function[i] < 0)
f_x << "- " << fabs(function[i]) << "x" << i + 1 << " ";
if (function[i] > 0)
f_x << "+ " << function[i] << "x" << i + 1 << " ";
}
}
std::string minmax;
if (way)
minmax = "max";
else
minmax = "min";
f_x << "=> " << minmax << "" << endl;
table << f_x.str();
table << "І система рівнянь :" << endl;
std::stringstream math_sys;
std::string math_sign;
for (i = 0; i < num_l; i++) {
for (j = 0; j < num_v; j++) {
if (!j)
math_sys << system[i][j] << "x" << j + 1 << " ";
else
if (system[i][j] == 1)
if (!j)
math_sys << "x" << j + 1 << " ";
else
math_sys << "+ x" << j + 1 << " ";
else
if (system[i][j] == -1)
if (!j)
math_sys << "-x" << j + 1 << " ";
else
math_sys << "- x" << j + 1 << " ";
else {
if (system[i][j] < 0)
math_sys << "- " << fabs(system[i][j])<< "x" << j + 1 << " ";
else
math_sys << "+ " << system[i][j] << "x" << i + 1 << " ";
if (!sign[i])
math_sign = "<=";
if (sign[i] == 1)
math_sign = "=";
if (sign[i] == 2)
math_sign = ">=";
}
}
math_sys << math_sign << " " << fm[i];
math_sys << endl;
}
std::string min_or_max;
if (way)
min_or_max = "максимум";
else
min_or_max = "мінімум";
table << math_sys.str() << endl;
table << "Вирішимо дану задачу на " << min_or_max << " методом симплексних таблиц.Побудуємо перший опорний план (таблицю):" << endl;
}
for (i = 0; i < num_l; i++) {
table << "x" << bv[i][0] + 1 << " " << bv[i][1] << " ";
for (j = 0; j < num_v * 2; j++)
table << sv[i][j] << " ";
if (!plane_is_valid())
table << th[i];
table << "" << endl;
}
table << "f(x) " << func << " ";
for (i = 0; i < num_v * 2;
27.12.2013 02:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора