Почти что каждый из нас когда-то учился (или еще учится) в ВУЗ_е, и практически везде лабораторные работы по темам, смежным с программированием пишут на Pascal. Ну, с какой-то стороны, конечно, правильно - теория изучается на теоретическом языке программирования, но все же нужно нужно двигаться вперед и стараться изучать те языки, которые действительно могут пригодиться в будущем...
И так, предлагаю решить одну из задач линейного программирования (ЛП) - максимизировать (минимизировать) функцию табличным симплекс методом.
А так как я позиционирую сею страничку как блог web-разработчика и верстальщика предлагаю реализовать табличный симплекс метод на JavaScript с применением jQuery.
Вдаваться в теорию, пожалуй, не буду, кому интересно рекомендую почитать здесь:
http://www.uchimatchast.ru/teory/tabl_simplex.php
Комментарии лучше не отделять от кода, поэтому сразу приведу код:
/**
* Решение задачи линейного программирования
* Табличный Симплекс метод
*
* Made by Tod
* http://tj-s.ru/
*/
$(document).ready(function(){
// Задаем глобальную переменную
max_x = 2;
// Счтаем максимальное количество Иксов
$('#ogranichenie_block .ogranichenie').each(function(){
var input_num = $(this).find('input').length -1;
if (input_num>max_x)
max_x = input_num;
})
// Показываем ограничения
//(сделано для плавного появления новых ограничений)
$('.ogranichenie').show();
})
// Показываем или скрываем пример
$('#info a.example').live('click', function(){
if ($('#info .left').is(':hidden')){
$(this).text('Скрыть пример ^');
$('#info .left').slideDown(200);
}else{
$('#info .left').slideUp(200);
$(this).text('Показать пример Ў');
}
return false;
})
// Добавляем Х
$('a.add_x').live('click', function(){
// Ограничили количество Иксов до 7, иначе они не помещаются в строчку и смотрятся некрасиво
if ($(this).parents('.virazhenie').find('input').length < 7){ // Ограничение можно снять или изменить
if ($(this).parents('.uravnenie').length){
var count_x = $(this).parents('.virazhenie').find('input').length +1;
if (count_x > max_x)
max_x = count_x;
}else{
var count_x = $(this).parents('.virazhenie').find('input').length;
if (count_x > max_x)
max_x = count_x;
}
$('.virazhenie').children('.left_side').append('+<input type="text" value="0" />X'+count_x);
}
return false;
})
// Добавляем ограничение
$('.ogranichenie_add a').live('click', function(){
var html_inputs = '<input type="text" value="0" />X1';
for (var q = 2; q<=max_x;q++)
html_inputs += '+<input type="text" value="0" />X'+q;
var html_code = '<div class="ogranichenie virazhenie"><span class="left_side">'+html_inputs+'</span><span class="right_side"><a class="add_x" href="#">+</a><select><option value="1">?</option><option value="-1">?</option></select><input type="text" value="0" /></span></div>';
$('#ogranichenie_block').append(html_code);
$('#ogranichenie_block .ogranichenie:hidden').slideDown(200);
return false;
})
// Начмнаем считать
$('.submit a').live('click', function(){
$('#result').html(' '); // Очищаем поле результатов
var matrix = new Array();
// var count_ogr = $('#ogranichenie_block .ogranichenie').length;
matrix = new Array();
var i = 0;
/*################## ШАГ 0 ##################*/
// Перебираем все ограничения
$('#ogranichenie_block .ogranichenie').each(function(){
matrix[i] = new Array();
for (var j = 0; j < max_x + 1; j++) {
if ($(this).find('input').eq(j).length && $(this).find('input').eq(j).val() ){
var inp_val = $(this).find('input').eq(j).val() * $(this).find('select').val();
}else{
var inp_val = 0;
}
matrix[i][j] = inp_val; // Матрица исходных значений
}
i++;
})
// Массив индексов по горизонтале
horisont_x = new Array();
for (i=0; i< max_x + 1; i++){
horisont_x[i] = i;
}
// Массив индексов по вертикале
vertical_x = new Array();
for (i=0; i< $('#ogranichenie_block .ogranichenie').length; i++){
vertical_x[i] = i + max_x;
}
// Матрица свободных членов
var free = new Array();
for (var k=0; k < matrix.length; k++){
free[k] = matrix[k][max_x];
}
free[matrix.length] = 0;
// Последняя строка сама функция
Fun = new Array();
for (var j = 0; j < matrix[0].length; j++) {
if ($('.uravnenie .left_side').find('input').eq(j).length){
var inp_val = $('.uravnenie .left_side').find('input').eq(j).val() * $('.uravnenie select').val();
}else{
var inp_val = 0;
}
Fun[j] = inp_val; // Матрица исходных значений
}
// Добавим ее в основную матрицу
matrix.push(Fun);
// Есть ли отрицательные элементы в матрице свободных членов ?
if (minelm(free) < 0){
iteration = 0; // счетчик итераций, для защиты от зависаний
step1(); // Переходим к шагу 1
}
// Есть ли отрицательные элементы в коэфициентах функции (последняя строчка) ?
if (minelm(matrix[matrix.length-1], false, true) < 0){
iteration = 0; // счетчик итераций, для защиты от зависаний
step2(); // Переходим к шагу 2
}
print_table(matrix); // Отображаем итоговую таблицу
results(); // Отображаем результаты в понятном виде
/*################## ШАГ1 ##################*/
function step1(){
iteration++;
// находим ведущую строку
var min_k_num = minelm(free, true, true);
// находим ведущий столбец
var min_k1 = minelm(free)
if (minelm(matrix[min_k_num]) < 0){
var min_k1_num = minelm(matrix[min_k_num], true, true);
}else{
alert('Условия задачи несовместны и решений у нее нет');
return false;
}
// Печатаем таблицу и выделяем на ней ведущие строку и столбец
print_table(matrix, min_k_num, min_k1_num);
// Обновляем индексы элементов по горизонтале и вертикале
tmp = horisont_x[min_k1_num];
horisont_x[min_k1_num] = vertical_x[min_k_num];
vertical_x[min_k_num] = tmp;
// Замена
update_matrix(min_k_num, min_k1_num);
// матрица свободных членов
for (var k=0; k < matrix.length; k++){
free[k] = matrix[k][max_x];
}
if (minelm(free, false, true) < 0 && iteration < 10) // нужно ли еще разок пройти второй шаг ?
if (confirm("продолжаем Шаг 1_"+iteration+" ?")) // Да здравсвует рекурсия, но спросим (чтобы комп не завис)
step1();
}
/*################## ШАГ2 ##################*/
function step2(){
iteration++;
// находим ведущий столбец
var min_col_num = minelm(matrix[matrix.length-1], true, true);
// находим ведущую строку
var cols_count = matrix[0].length -1;
var min_row_num = 999;
// эмпирический коэфициент, тк мы не знаем, положително ли нулевое отношение
var min_row = 9999;
var tmp = 0;
for (i = 0; i< matrix.length-1; i++){
tmp = free[i]/matrix[i][min_col_num];
if (tmp < min_row && tmp>=0){
min_row_num = i;
min_row = tmp;
}
}
min_k1_num = min_col_num;
min_k_num = min_row_num;
// Печатаем таблицу и выделяем на ней ведущие строку и столбец
print_table(matrix, min_k_num, min_k1_num);
// Обновляем индексы элементов по горизонтале и вертикале
tmp = horisont_x[min_k1_num];
horisont_x[min_k1_num] = vertical_x[min_k_num];
vertical_x[min_k_num] = tmp;
// Если мы не нашли ведущую строку (999 - это наш эмпирический коэфициент)
if (min_row_num == 999){
alert('функция в области допустимых решений задачи не ограничена');
return false;
}
// Замена
update_matrix(min_k_num, min_k1_num);
// матрица свободных членов
for (var k=0; k < matrix.length; k++){
free[k] = matrix[k][max_x];
}
// нужно ли еще разок пройти второй шаг ?
if (minelm(matrix[matrix.length-1], false, true) < 0 && iteration < 10)
// Да здравсвует рекурсия, но спросим, чтобы комп не завис
if (confirm("продолжаем Шаг 2_"+iteration+" ?"))
step2();
}
// Функция замены (обновления матрицы)
function update_matrix(min_k_num, min_k1_num){
var matrix1 = new Array();
for (i = 0; i< matrix.length; i++){
matrix1[i] = new Array()
for (j = 0; j< matrix[0].length; j++){
if (i == min_k_num && j ==min_k1_num){
matrix1[i][j] = 1/matrix[i][j];
}else{
if (i == min_k_num){
matrix1[i][j] = matrix[i][j] * 1/matrix[min_k_num][min_k1_num];
}else{
if (j == min_k1_num){
matrix1[i][j] = -matrix[i][j] * 1/matrix[min_k_num][min_k1_num];
}else{
matrix1[i][j] = matrix[i][j] - matrix[i][min_k1_num]*matrix[min_k_num][j]/matrix[min_k_num][min_k1_num];
}
}
}
matrix1[i][j] = Math.round(matrix1[i][j]*1000)/1000;
}
}
matrix = matrix1;
return false;
}
// Выводим результаты в понятном виде
function results(){
var nulls = '';
// Иксы, равные нулю
for (i = 0; i< horisont_x.length-1;i++){
if (horisont_x[i] nulls +=('X'+(horisont_x[i]+1)+'=');
}
nulls +='0
';
var vars ='';
// Иксы, отличные от нуля
for (i = 0; i< vertical_x.length;i++){
if (vertical_x[i] vars += 'X'+(vertical_x[i]+1)+'='+matrix[i][max_x]+'
';
}
var main_result = '';
// Минимум(максимум) функции
if ($('.uravnenie select').val() > 0)
main_result = 'min F ='+matrix[matrix.length-1][max_x]*(-1);
else
main_result = 'max F ='+matrix[matrix.length-1][max_x];
$('#result').append(nulls+vars+'
'+main_result);
}
return false;
})
// Вывод таблицы.
function print_table(arr, row, col){
var max_i = arr.length;
var max_j = arr[0].length;
var html_table = '';
var html_head = '';
// заголовки
for (var j = 0; j < max_j-1; j++) {
html_head +='X'+(horisont_x[j]+1)+''
}
html_head +='Своб.члены'
html_head =''+html_head+'';
// Элементы
for (var i = 0; i < max_i; i++) {
html_table +='';
if (!(i == max_i-1)){
html_table +='X'+(vertical_x[i]+1)+'';
}else{
html_table +='F';
}
for (var j = 0; j < max_j; j++) {
html_table +=''+arr[i][j]+''
}
html_table +='';
}
$('#result').append(''+html_head+html_table+'');
// Выделяем колонку, если указана
if (col !== undefined)
$('table:last tr').each(function(){
$(this).children('td').eq(col).addClass('selected');
})
// Выделяем строку, если указана
if (row !== undefined)
$('table:last tr').eq(row+1).addClass('selected');
}
// Поиск минимального элемента
function minelm(v, dispnum, not_last){
var m= v[0];
var num= 0;
var len=0;
// если not_last, то последний элемент не учитываем в массиве
if (not_last){
len = v.length-2;
}else{
len = v.length-1;
}
for (var i=1; i <= len; i++){
if (v[i] < m ){
m= v[i];
num = i
}
}
// Выводим номер минимального
if (dispnum){
return num
}else{ // или значение
return m
}
}
// Made by Tod
// http://tj-s.ru/