Математические методы

 

Получаем новую симплекс-таблицу:

Таблица 8 – Симплекс-таблица, полученная после вычислений

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x4	82/3	1/9	8/9	0	1	-1/3	-1/9	0	1/3	1/9
x3	211/3	-4/9	24/9	1	0	-2/3	-5/9	0	2/3	5/9
x7	1091/3	18/9	111/9	0	0	-32/3	-18/9	1	32/3	18/9
F(X3)	771/3	-24/9	74/9	0	0	-22/3	-15/9	0	22/3+M	15/9+M

 

Итерация №3.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем  столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

и из них выберем наименьшее:

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (1⁸/₉) и находится на пересечении ведущего столбца и ведущей строки.

Таблица 9 – Симплекс таблица  с обозначенными ведущими строкой  и столбцом

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x4	82/3	1/9	8/9	0	1	-1/3	-1/9	0	1/3	1/9	78
x3	211/3	-4/9	24/9	1	0	-2/3	-5/9	0	2/3	5/9	-
x7	1091/3	18/9	111/9	0	0	-32/3	-18/9	1	32/3	18/9	5715/17
F(X4)	771/3	-24/9	74/9	0	0	-22/3	-15/9	0	22/3+M	15/9+M	0

 

Получаем новую симплекс-таблицу:

Таблица 10 – Симплекс-таблица, полученная после вычислений

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x4	24/17	0	4/17	0	1	-2/17	0	-1/17	2/17	0
x3	471/17	0	51/17	1	0	-19/17	-1	4/17	19/17	1
x1	5715/17	1	515/17	0	0	-116/17	-1	9/17	116/17	1
F(X4)	21814/17	0	2114/17	0	0	-77/17	-4	15/17	77/17+M	4+M

 

Таблица 11 - Окончательный вариант симплекс-таблицы

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x4	24/17	0	4/17	0	1	-2/17	0	-1/17	2/17	0
x3	471/17	0	51/17	1	0	-19/17	-1	4/17	19/17	1
x1	5715/17	1	515/17	0	0	-116/17	-1	9/17	116/17	1
F(X5)	21814/17	0	2114/17	0	0	-77/17	-4	15/17	77/17+M	4+M

 

x₄ = 2⁴/₁₇

x₃ = 47¹/₁₇

x₁ = 57¹⁵/₁₇

F(X) = 4•2⁴/₁₇ + 2•47¹/₁₇ + 2•57¹⁵/₁₇ = 218¹⁴/₁₇

 

2.2 Решение задачи линейного программирования с помощью электронных таблиц

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

Общая задача линейного программирования (ЗЛП) состоит в нахождении экстремального значения (максимума или минимума) линейной функции.

Для решения подобных задач  в MS EXCEL предназначена команда Поиск  решения из меню Сервис.

Таблица 12 – Решенная задача линейного программирования с помощью  электронных таблиц

	x1	x2	x3	x4		B
	52	0	100	14
F(x)	2	1	2	4	0	=>	360
1	1	2	-1	5	<=	22	22
2	-2	2	2	-6	<=	12	12
3	-2	2	0	7	<=	-6	-6

 

2.3 Решение задачи линейного программирования с помощью программы

Программа была написана языке  программирования C++. Выполняет все необходимые операции и вычисления, и выдает готовое верное решение.

  

Рисунок 1 – Программа  решения задач линейного программирования без введенных  нами исходных данных.

 

Рисунок 2 - Программа решения  задач линейного программирования с введенными нами исходными данными.

 

Рисунок 3 – Результат  работы программы.

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

 

Заключение

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

 

Список литературы

1.Ашманов С.А., Линейное  программирование. М.: Наука 2005.

2.Кузнецов А.В., Холод Н.И., Математическое программирование. Мн.: Высшая школа 2006

3.Кузнецов А.В., Холод Н.И., Костевич Л.С., Руководство к решению  задач по математическому программированию. Мн.: 2004

4.Кузнецов А.В., Холод Н.И., Новикова Т.И. сборник задач  по математическому программированию. Мн.: Высшая школа 2007

5.Кузнецов А.В., Холод Н.И., Сокович В.А.., Высшая математика. Математическое программирование. Мн.: Высшая школа 2005

 

Приложение. Код программы

Листинг 1. user_data.h

#ifndef _USER_DATA_H_

#define _USER_DATA_H_

class user_data {

public:

void get_data_from_user();

void user_data_is_valid();

protected:

double *function;

double *fm;

double **system;

int *sign;

int num_v;

int num_l;

bool way; };

#endif /* _USER_DATA_H_ */

 

Листинг 2. user_data.cpp

#include <iostream>

#include <string>

#include <cstdlib>

#include "user_data.h"

using std::cout;

using std::cin;

using std::endl;

using std::string;

void error(int err_no) {

switch(err_no) {

case 0:

cout << "\nВы ввели некорректное значение.\n" << endl;

break;

case 1:

cout << "\nВы не можете  задать менее двух ограничений.\n" << endl;

break;

case 2:

cout << "\nВы не можете  задать больше 500 ограничений.\n" << endl;

break;

case 3:

cout << "\nВы не можете  задать менее двух переменных.\n" << endl;

break;

case 4:

cout << "\nВы не можете  задать более 500 уравнений.\n" << endl;

break; } }

void user_data::get_data_from_user() {

string num_limits, num_vars, s_var, fr_m, sn, func, w;

int i, j;

bool validator = false;

do {

cout << "Введите количество  ограничений в системе: ";

getline(cin, num_limits);

if (atoi(num_limits.c_str()) < 2)

error(1);

else if (atoi(num_limits.c_str()) > 500)

error(2);

else

validator = true;

} while (!validator);

num_l = atoi(num_limits.c_str());

validator = false;