19809

Геометричне розв’язання задачі лінійного програмування

Доклад

Информатика, кибернетика и программирование

Kак известно общая задача линейного программирования со стоит в поиске значений переменных удовлетворяющих некоторым линейным ограничениям и обеспечивающих наибольшее наимень шее значение заданной линейной функции. Например требование: максимизировать Lx1...

Украинкский

2013-07-17

16.74 KB

2 чел.

Kак известно, общая задача линейного программирования со-

стоит в поиске значений переменных, удовлетворяющих некоторым

линейным ограничениям и обеспечивающих наибольшее (наимень-

шее) значение заданной линейной функции. Например, требование:

максимизировать

L(x1, x2, x3) = 2x1 + x2 + 4x3

при условиях

x1 +2x2 + 3x3 12,

x1 0, x2 0, x3 0

означает пожелание не только отыскать значения неких величин x1,

x2 и x3, удовлетворяющих вышеприведенным четырем условиям, но и

среди них найти такие, что функция L(x1, x2, x3) принимает самое

большое значение.

В роли неизвестных величин могут выступать, например, объе-

мы выпуска продукции (обуви, приборов ночного видения или мик-

роскопов), распределение денежных средств на ликвидацию ветхого

жилья и строительство медицинских учреждений, тираж поэм М. Ю.

Лермонтова и «заговоров от сглаза»; ограничения связаны с расходом

материалов, наличием льгот на отдельные виды изданий, рыночной

конъюнктурой или личными предпочтениями, а целевая функция L(Х)

может определять прибыль от произведенной продукции или объем

неосвоенных средств.

Количество неизвестных величин, фигурирующих в постановке

задачи, называют ее размерностью. Набор их значений, удовлетво-

ряющих условиям задачи, называют планом (примером может слу-

жить программа производства – набор значений показателей, удовле-

творяющий ограничениям по сырьевым, социальным и прочим фак-

торам).

Может обнаружиться, что задача неразрешима – не существует

ни одного плана (ограничения противоречат друг другу). Может быть

единственный план или много (множество) планов, среди которых

надо найти наилучший (оптимальный), дающий максимум прибыли

2

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

затрат (жалоб населения, отходов при деревообработке и др.).

Размерность реальных задач, как правило, велика (от десятков

до нескольких сотен). Здесь мы намерены на примере двумерных за-

дач дать читателю наглядное, графическое представление о существе

решаемых линейных программ (полагая, что всякий человек способен

рисовать на плоском листе бумаги и воспринимать конструкции ок-

ружающего нас трехмерного пространства). Наличие такого пред-

ставления может помочь и при обобщении выводов на задачи

бóльшей размерности.

Естественно, что для решения задачи желательно сначала полу-

чить представление о множестве планов (допустимых решениях) и

лишь затем из этого множества выбрать наилучший (с точки зрения

поставленной цели).

Обратимся к знаниям, полученным еще в школьные годы. Из-

вестно, что уравнение αX + βY = γ на плоскости (X,Y) изображает

прямую линию (2x + 3y = 7, y = 0 или x – 2y = 0) и для ее построе-

ния достаточно взять пару подходящих точек. Неравенства же

αX + βY ≤ γ или αX + βY ≥ γ определяют полуплоскости, ограни-

ченные прямой αX + βY = γ.

Поскольку система ограничений двумерной задачи линейного

программирования определяет множество точек плоскости, лежащих

или на прямых линиях, или в полуплоскостях, ограниченных такими

линиями, то множество планов может быть представлено точкой, ча-

стью прямой линии, фигурой, напоминающей выпуклый многоуголь-

ник, но никак не эллипсом, полумесяцем или другим криволинейным

объектом.


 

А также другие работы, которые могут Вас заинтересовать

80698. Налог на пользователей автомобильных дорог 76 KB
  Объект налогообложения Объектом налогообложения является выручка полученная от реализации продукции работ услуг и сумма разницы между продажной и покупной ценами товаров реализованных в результате заготовительной снабженческосбытовой и торговой деятельности. По плательщикам налога осуществляющим реализацию товаров продукции работ услуги по ценам не выше фактической себестоимости для целей налогообложения применяются рыночные цены на аналогичные товары продукцию работы услуги сложившиеся на момент реализации но...
80699. Налог на реализацию горюче-смазочных материалов 56.5 KB
  Плательщики налога Плательщиками налога на реализацию горюче смазочных материалов автобензин дизельное топливо масла дизельные масла для карбюраторных двигателей масла для карбюраторных и дизельных двигателей сжатый и сжиженный газ используемый в качестве моторного топлива являются юридические лица предприятия учреждения организации объединения далее организации граждане осуществляющие предпринимательскую деятельность без образования юридического лица далее предприниматели реализующие указанные материалы....
80700. The problem of linguistic meaning. Types of linguistic meaning. Main approaches to the definition of meaning 37.66 KB
  Semasiology (or semantics ) is a branch of linguistics which studies meaning. There are three main categories of definitions which may be referred to as: -analytical or referential definition of meaning - functional or contextual definition of meaning,- operational or information-oriented definition of meaning
80701. Synonymy 32.44 KB
  Synonyms are the words of the same part of speech different in their sound-form but similar in their meaning and interchangeable at least in one context. There are very few perfect synonyms. They usually differ in some aspect of their meaning — according to this they can be ideographic
80702. Antonymy (semantic opposition). Antonyms are words which express opposite or contrasting meanings 32.49 KB
  Antonyms are subdivided into. Gradable — represent the extremes of the quality. There are often adjectives that can be placed on the scale between them (hot-cold). Contradictory-complimentary — cannot exist without each other (dead-alive; leave-stay)3. Conversive — describe opposite attributes of the same situation (to buy-to sell — when one buys another sells)
80704. THE MORPHEMIC STRUCTURE OF THE WORD. TYPES OF MORPHEMES. ALLOMORPHS nd mening: they dont possessed grmmticl mening. 30.83 KB
  The morpheme is the smallest meaningful unit of form. A form in these cases a recurring discrete unit of speech. Morphemes occur in speech only as constituent parts of words, not independently, although a word may consist of single morpheme. Even a cursory examination of the morphemic structure of English words reveals that they are composed of morphemes of different types: root-morphemes and affixational morphemes. Words that consist of a root and an affix are called derived words or derivatives and are produced by the process of word building known as affixation (or derivation).
80705. MORPHEMIC LEVEL OF ANALYSYS OF WORD-STRUCTURE 33.59 KB
  There are two levels of approach to the study of word- structure: the level of morphemic analysis and the level of derivational or word-formation analysis. Principles of morphemic analysis. In most cases the morphemic structure of words is transparent enough and individual morphemes clearly stand out within the word. The segmentation of words is generally carried out according to the method of Immediate and Ultimate Constituents.
80706. Lexicology as a branch of linguistics. Parts /branches of lexicology. The connection of lexicology with other branches of linguistics 32.51 KB
  Special lexicology – the lexicology of a particular language, i.e. the study and description of its vocabulary and vocabulary units, primarily words as the main units of language.; special lexicology is based on the principles worked out and laid down by general lexicology, a general theory of vocabulary. Special lexicology employs synchronic (q.v.) and diachronic (q.v.) approaches