Читайте данную работу прямо на сайте или скачайте

Модифицированный симплекс-метод с мультипликативным представлением матриц

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту по Системному анализу

Тема: Решение задач линейного программирования большой размерности

Выполнил студент гр. Э-282:

Богдановский А. А.

Проверил преподаватель:

Тихненко Е. В.

Дата:

УФ 1996 г.

СОДЕРЖАНИЕ

TOC \o "1-3" \f GOTOBUTTON _Toc347013713а а1 %1\:1\:0\:\." Kolesnikov 20081025T2321">[А. А.1]  В соответствии с общей постановкой задачи, возможностями студента, доступной литературой и другими факторами, студентом была конкретизирована и сформулирована следующая задача:

      Умодифицированный симплекс-метод с мультипликативным представлением обратной матрицы;

     

     

     

[А. А.2]  Решаемая задача линейного программирования представлена в канонической форме и имеет следующий вид:

min F = cx, при Ax = b, x ³ 0,

где c - вектор коэффициентов целевой функции (c₁,c₂,...,c_n);

A - матрица ограничений размера m´n ранга m, может быть представлена также как вектора [P₁, P₂, ..., P_n];

b - m-вектор правой части ограничений (b₁,b₂,...,b_m).

Таким образом, поставленная задача имеет n - переменных и m - ограничений.

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

[А. А.3] Интерфейс пользователя

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

6.2.           

Программа SASIMPL понимает только определенные файлы с постановкой задач. Рассмотрим один из них:

; *** Начало файла с данными о задаче ***

; Примера иза Ю. П. Зайченко, С. А. Шумилова

; "Исследование операций" N1.46

n = 8 ; количество переменных

m = 4 ; количество ограничений

F = -3 -1 0 1 0 0 1 ; целевая функция минимизации

LIMITS: ; задание ограничений

1 2 -1 1 = 5

2 4 0 0 1 = 16

3 1 0 0 0 -1 1 = 6

1 3 0 0 0 0 0 1 = 9

;*** Конец файла ***

Символ ';' является символом-коментария.

Создавая файлы такого формата, обратите внимание на то, что целевая функция Fа должн задаваться для минимизации (преобразование максимизирующейа к минимизирующейа функции производится путем множения ее коэффициентов на -1). Кроме того, в ограничениях должны стоять только (!) равенства, то есть должны же быть введены свободные и искусственные переменные.

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

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

1.   

2.   

3.   

4.   

5.   

6.   

7.   

TC "

---

PAGE \# "'Стр: '#'
'"а  [А. А.1] Тихненко считает, что обращение к себе как к третьему лицу - плохой тон...

PAGE \# "'Стр: '#'
'"а  [А. А.2] Оказывается каноническая форма постановки линейной задачи не обуславливает наличие начального опорного плана (единичного базиса) - это в принципе самая главная ошибка курсовика (то есть у меня требовалась постановка задачи не только в каноническом виде, но и чтобы присутствовал единичный базис...)

PAGE \# "'Стр: '#'
'"а  [А. А.3] Тихненко не понравилось в интерфейсе слишком!! много разных цветов (я это тоже осознал - цветов в программе, как на попугае...). Еще, естественно, не понравилось то, что задаваь задачу надо вне программы и то, что надо вручную делать единичный базис...